C# 개체의 32 비트 해시 함수

Question

모든 클래스에서 개체의 GetHashCode() 메서드를 재정의하고 싶습니다. 이 메서드는 Int32를 반환합니다. 내가 아는 모든 암호화 해시 함수는 32 비트 정수에 맞지 않는 반환 값을가집니다. 최대한 충돌을 피하고 싶습니다. SHA와 같은 보안 해시를 잘라야합니까, 아니면 32 비트 해시를 사용해야합니까? 32 비트 해시를 사용하는 경우 가장 좋은 32 비트 해시는 무엇입니까?

Answer 1

해시 값의 너비가 짧을수록 충돌 가능성이 커집니다. Int32은 최대 4294967296 개의 서로 다른 값을 저장하므로 보안 또는 신원 확인을위한 것인지 여부에 따라 고유 한 충분한 가치를 보유할지 여부를 고려해야합니다.

GetHashCode()을 무시하려는 이유에 관심이 있습니다. 값이 32 비트에 맞아야합니까? 그렇다면 왜?

Answer 2

은 GetHashCode을 구현할 수 있습니다. SHA 해시가 잘립니다. 그러나 아마해서는 안됩니다.

GetHashCode의 목적은 객체를 hash tables에 삽입하는 것입니다. 해시 테이블의 목적은 검색을 최적화하는 것입니다. 평균적으로 해시 테이블에서 키를 찾는 데는 트리의 O (log n) 또는 정렬되지 않은 목록의 O (n)과 비교하여 O (1) 시간 만 필요합니다.

GetHashCode 메서드가 충돌을 최소화하여 해시 테이블 조회가 O (n) 시간으로 변하는 것을 방지해야합니다. 그러나 해시 테이블의 전체적인 점이 최적화되기 때문에 이들을 빠르게 수행하기를 원합니다. 해시 코드가 계산하는 데 시간이 오래 걸리는 경우 데이터를 List에 저장했을 수도 있습니다.

암호화 해시가 느립니다. 일반적으로 무단 공격을 막기 위해 이으로 설계되었습니다. 이로 인해 GetHashCode과 함께 사용하기에 부적합합니다.

어떻게 을GetHashCode을 구현해야합니까? 간단하고 자주 사용되는 접근법은 Equals 함수에서 사용되는 모든 멤버 변수를 함께 XOR하는 것입니다.

struct Complex 
{ 
    double real; 
    double imag; 

    public override int GetHashCode() 
    { 
     return real.GetHashCode()^imag.GetHashCode(); 
    } 

    // ... 
} 

또 다른 간단한 접근법은 배열과 유사한 객체에 적합하며 polynomial hash function입니다. 당신이 클래스는 해시 많은 양의 데이터가 포함 된 경우

class MyClass 
{ 
    int[] data; 

    public override int GetHashCode() 
    { 
     int result = 0; 

     foreach (int n in data) 
     { 
      result = result * 41 + n; 
     } 

     return result; 
    } 

    // ... 
} 

, 당신은 GetHashCode() 후 그냥 변수를 사용할 수 있도록, 멤버 변수에 해시 코드를 저장하고 건설 중에을 미리 계산 할 수 있습니다.

Answer 3

Eric Lippert는 GetHashCode() 메서드를 올바르게 구현하는 방법에 대해 great blog entry을 만들었습니다. GetHashCode()의 목적은 객체를 해시 테이블에 저장하는 것임을 기억해야합니다. 이를 위해이 기능을 사용하면 나중에 반복 할 수도 있고 나중에 정렬 할 수도 있습니다. 이 작업을 수행하기 위해 암호화 기능을 사용하는 경우 반복 또는 정렬 절차가 매우 느리게 실행됩니다. 암호화 기능은 데이터를 고유하게 식별하는 것이 아니라 데이터를 보호하도록 설계되었습니다. Eric Lippert의 블로그 게시물을 읽어보십시오. 도움이 될 것입니다

Answer 4

모두에게 약간의 정보. 다른 .NET 플랫폼 간의 GetHashCode()는 다릅니다. 예를 들면 : .NET 2.0의 "Hello".GetHashCode() 대 .NET 4.0의 "Hello".GetHashCode()는 다른 결과를 산출합니다. 따라서 .NET을 사용하여 HashTable 또는 Dictionaries를 즉시 사용할 수 없습니다.

사용자 고유의 해시 알기를 구현하면 여러 플랫폼에서 일관성을 유지할 수 있습니다. 그냥 알려주려고하면 Int32보다 작아지기를 원하지 않습니다. 내 충고는 Int64 (long)를 고수하는 것입니다. 이렇게하면 충돌이 적어집니다. 해시의 목표입니다.이 라이브러리는 제가 수년 전에 저술 한 라이브러리입니다. 각 해시 알 고는 플러스와 마이너스 (속도 대 최소 충돌)를가집니다. 이 특정 버전은 문자열을 입력으로 사용하지만 적절하게 수정할 수 있습니다.

static public class StringHash 
    { 
     //--------------------------------------------------------------------- 
     static public Int64 RSHash(String str) 
     { 
      const Int32 b = 378551; 
      Int32 a = 63689; 
      Int64 hash = 0; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash = hash * a + str[i]; 
       a = a * b; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 JSHash(String str) 
     { 
      Int64 hash = 1315423911; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash ^= ((hash << 5) + str[i] + (hash >> 2)); 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 ELFHash(String str) 
     { 
      Int64 hash = 0; 
      Int64 x = 0; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash = (hash << 4) + str[i]; 

       if ((x = hash & 0xF0000000L) != 0) 
       { 
        hash ^= (x >> 24); 
       } 
       hash &= ~x; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 BKDRHash(String str) 
     { 
      const Int64 seed = 131; // 31 131 1313 13131 131313 etc.. 
      Int64 hash = 0; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash = (hash * seed) + str[i]; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 SDBMHash(String str) 
     { 
      Int64 hash = 0; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash = str[i] + (hash << 6) + (hash << 16) - hash; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 DJBHash(String str) 
     { 
      Int64 hash = 5381; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash = ((hash << 5) + hash) + str[i]; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 DEKHash(String str) 
     { 
      Int64 hash = str.Length; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash = ((hash << 5)^(hash >> 27))^str[i]; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 BPHash(String str) 
     { 
      Int64 hash = 0; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash = hash << 7^str[i]; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 FNVHash(String str) 
     { 
      Int64 fnv_prime = 0x811C9DC5; 
      Int64 hash = 0; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       hash *= fnv_prime; 
       hash ^= str[i]; 
      } 

      return hash; 
     } 
     //--------------------------------------------------------------------- 
     static public Int64 APHash(String str) 
     { 
      Int64 hash = 0xAAAAAAAA; 

      for (Int32 i = 0; i < str.Length; i++) 
      { 
       if ((i & 1) == 0) 
       { 
        hash ^= ((hash << 7)^str[i] * (hash >> 3)); 
       } 
       else 
       { 
        hash ^= (~((hash << 11) + str[i]^(hash >> 5))); 
       } 
      } 

      return hash; 
     } 
    }