정수 해시 키를 사용할 수 있는 정수 해시 함수는 무엇입니까?

정수 해시 키를 사용할 수 있는 정수 해시 함수는 무엇입니까?

정수 해시 키를 사용할 수 있는 정수 해시 함수는 무엇입니까?

나는 다음 알고리즘이 매우 좋은 통계 분포를 제공한다는 것을 알았다.각 입력 비트는 약 50% 확률로 각 출력 비트에 영향을 줍니다.충돌은 없습니다(각 입력 결과 서로 다른 출력이 됩니다).CPU에 내장 정수 곱셈 단위가 없는 경우를 제외하고 알고리즘은 고속입니다. 코드(C를 전제로 함)int의 경우(Java)를 바꿉니다)>>>>>unsigned

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

매직넘버는 특별한 멀티스레드 테스트프로그램을 사용하여 계산되었으며, 이 프로그램은 눈사태 효과(단일 입력 비트가 변경되었을 때 변화하는 출력 비트 수, 평균 16비트여야 함), 출력 비트 변경의 독립성(출력 비트는 서로 의존하지 않아야 함) 및 확률을 계산합니다.입력 비트가 변경되면 각 출력 비트가 변경됩니다.계산된 값은 Murmur Hash가 사용하는32비트 파이널라이저보다 우수하며 AES를 사용할 때와 거의 같은 수준(완전하지는 않음)입니다.약간의 장점은 동일한 상수가 두 번 사용된다는 것입니다(지난 번에 테스트했을 때는 약간 빨라졌지만, 아직 그런지는 확실하지 않습니다).

) 할 수 .0x45d9f3b0x119de1f3(곱셈 역):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

64비트 숫자의 경우, 가장 빠르지 않을 수도 있지만 다음을 사용하는 것이 좋습니다.이것은 블로그 기사 Better Bit Mixing(믹스 13)에 근거한 것으로 보이는 splitmix64에 근거하고 있습니다.

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

Java를 합니다.long, 더하다L 「」를 치환한다.>>>>>unsigned로 하는 이 더

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

업데이트: 해시함수 통합관리 프로젝트도 볼 수 있습니다.이 프로젝트에는 다른 (아마도 더 나은) 상수가 나열되어 있습니다.

고속 및 양호한 해시 함수는 다음과 같이 품질이 낮은 고속 순열로 구성할 수 있습니다.

• 고르지 않은 정수를 가진 곱셈
• 바이너리 회전
• 시프트

난수 생성을 위해 PCG에서 시연된 것과 같이 우수한 품질의 해싱 함수를 생성합니다.

이는 실제로 rrxmrxmsx_0 및 murmur hash가 의도적이든 무의식적이든 사용되고 있는 레시피이기도 합니다.

저는 개인적으로

uint64_t xorshift(const uint64_t& n,int i){
  return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
  uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
  uint64_t c = 17316035218449499591ull;// random uneven integer constant; 
  return c*xorshift(p*xorshift(n,32),32);
}

충분히 좋을 것 같아.

적절한 해시함수는

1. 가능한 한 정보를 느슨하게 하지 않고 충돌을 최소한으로 억제하기 위해 생동감 있는
2. 가능한 한 균등하게 캐스케이드합니다. 즉, 각 입력 비트는 0.5의 0.5로 모든 출력 비트를 플립해야 합니다.

먼저 아이덴티티 함수를 살펴보겠습니다.1을 만족하지만 2는 만족하지 않습니다.

입력 비트 n은 100%(빨간색)의 상관관계를 갖는 출력 비트n을 결정하므로 파란색으로 표시되므로 완전한 빨간색 선을 얻을 수 있습니다.

xorshift(n,32)는 1행 반을 산출하므로 그다지 좋지 않습니다.두 번째 어플리케이션에서는 반전할 수 있기 때문에 여전히 만족스러운 1.

부호 없는 정수("Knuth의 곱셈 방식")를 사용하는 곱셈이 훨씬 우수하며, 0.5의 확률로 더 많은 출력 비트를 녹색으로 플립합니다.이는 1을 만족한다. 각 고르지 않은 정수에 대해 곱셈 역수가 존재한다.

두 가지를 조합하면 다음과 같은 출력이 나오지만, 여전히 만족스러운 1. 두 가지 생체 함수의 구성이 또 다른 생체 함수를 생성하기 때문이다.

곱셈과 xorsshift를 두 번째로 적용하면 다음과 같은 결과가 나옵니다.

또는 GHASH와 같은 Galois 필드 곱셈을 사용할 수 있습니다. GHASH는 최신 CPU에서 상당히 빨라지고 한 번에 우수한 품질을 제공합니다.

   uint64_t const inline gfmul(const uint64_t& i,const uint64_t& j){           
     __m128i I{};I[0]^=i;                                                          
     __m128i J{};J[0]^=j;                                                          
     __m128i M{};M[0]^=0xb000000000000000ull;                                      
     __m128i X = _mm_clmulepi64_si128(I,J,0);                                      
     __m128i A = _mm_clmulepi64_si128(X,M,0);                                      
     __m128i B = _mm_clmulepi64_si128(A,M,0);                                      
     return A[0]^A[1]^B[1]^X[0]^X[1];                                              
   }

Knuth의 승법:

hash(i)=i*2654435761 mod 2^32

해시 크기)의합니다.2^32이 예에서는 공통 요인이 없습니다.이렇게 하면 해시 함수는 모든 해시 공간을 균일하게 커버합니다.

편집: 이 해시 함수의 가장 큰 단점은 나눗셈이 유지된다는 것입니다. 따라서 정수가 모두 2 또는 4로 나누어지면 해시도 마찬가지입니다.이는 해시 테이블의 문제로 버킷의 1/2 또는 1/4만 사용할 수 있습니다.

데이터가 배포되는 방식에 따라 달라집니다.단순한 카운터의 경우, 가장 단순한 함수

f(i) = i

좋습니다(최적이라고 생각되지만 증명할 수 없습니다).

랜덤 해시 값에 대해 일부 엔지니어는 황금 비율 소수(2654435761)는 잘못된 선택이라고 말했습니다. 테스트 결과, 사실이 아닌 것으로 판명되었습니다.대신 2654435761은 해시 값을 상당히 잘 분배합니다.

#define MCR_HashTableSize 2^10

unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
  key = key*2654435761 & (MCR_HashTableSize - 1)
  return key;
}

해시 테이블 크기는 2의 거듭제곱이어야 합니다.

정수에 대한 많은 해시 함수를 평가하는 테스트 프로그램을 작성했는데, 그 결과 GRPrime Number가 매우 좋은 선택임을 알 수 있습니다.

시도했습니다.

1. total_data_entry_number / total_data_number = 2, 3, 4. 여기서 total_data_number = 해시 테이블 크기;
2. 해시 값 도메인을 버킷인덱스 도메인에 매핑합니다.즉, Hash_에 나타나듯이 Logical And Operation with (hash_table_size - 1)에 의해 해시 값을 버킷인덱스로 변환합니다.UInt_GRPrimeNumber();
3. 각 버킷의 충돌 횟수를 계산합니다.
4. 매핑되지 않은 버킷, 즉 빈 버킷을 기록합니다.
5. 모든 버킷의 최대 충돌 수, 즉 가장 긴 체인 길이를 확인합니다.

테스트 결과 골든비 프라임 숫자는 항상 빈 버킷 수가 적거나 빈 버킷이 0개이고 충돌 체인 길이가 가장 짧다는 것을 발견했습니다.

일부 해시 기능은 양호한 것으로 주장되지만, 전체_ 데이터_T_T_T_T_ 숫자 = 3(최대 0 3 3(최대 충돌)보다 더 큰 버킷)의 경우, 0(최대 0(최대영어황금비율 소수 해싱의 3번째.

그런데 테스트 결과, 시프트-xor 해시 함수의 한 가지 버전이 꽤 좋다는 것을 알게 되었습니다(mikera가 공유하고 있습니다.

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}

사용하고 있습니다.splitmix64(토머스 뮐러의 대답으로 가리키며) 내가 이 실마리를 찾은 이후부터.그러나 최근 우연히 Pelle Evensen의 rrxmrrxmsx_0을 발견했다.이것은 원래의 MurmurHash3 파이널라이저와 그 후속 모델보다 훨씬 더 나은 통계 분포를 산출했다.splitmix64기타 혼합물).C의 코드 스니펫은 다음과 같습니다.

#include <stdint.h>

static inline uint64_t ror64(uint64_t v, int r) {
    return (v >> r) | (v << (64 - r));
}

uint64_t rrxmrrxmsx_0(uint64_t v) {
    v ^= ror64(v, 25) ^ ror64(v, 50);
    v *= 0xA24BAED4963EE407UL;
    v ^= ror64(v, 24) ^ ror64(v, 49);
    v *= 0x9FB21C651E98DF25UL;
    return v ^ v >> 28;
}

Pelle은 또한 마지막 단계에서 사용된 64비트 믹서의 상세 분석을 제공합니다.MurmurHash3더 최근의 변종들.

이 페이지에는 일반적으로 상당한 경향이 있는 간단한 해시 함수가 나열되어 있지만, 모든 단순 해시에는 제대로 작동하지 않는 병적인 경우가 있습니다.

• 32비트 곱셈 방식(매우 빠름) "@rafal" 참조

  #define hash32(x) ((x)*2654435761)
  #define H_BITS 24 // Hashtable size
  #define H_SHIFT (32-H_BITS)
  unsigned hashtab[1<<H_BITS]  
  .... 
  unsigned slot = hash32(x) >> H_SHIFT
  

• 32비트 및 64비트(양호한 분배): Murmur Hash

• 정수 해시 함수

Everally Confuzzled에서는 해시 알고리즘의 개요를 설명합니다.눈사태에 빠르게 도달하여 효율적인 해시 테이블 검색에 사용할 수 있는 Bob Jenkins의 1회성 해시를 추천합니다.

답은 다음과 같은 많은 것에 달려 있습니다.

• 당신은 그것을 어디에 채용할 예정입니까?
• 해시로 뭘 하려는 거야?
• 암호학적으로 안전한 해시 함수가 필요합니까?

SHA-1과 같은 해시 함수의 Merkle-Damgard 패밀리를 살펴보시기 바랍니다.

해시 함수는 데이터를 사전에 파악하지 않고는 "좋다"고 말할 수 없다고 생각합니다.또, 이 함수로 무엇을 할지도 모릅니다.

데이터 크기를 알 수 없는 경우 해시 테이블보다 더 좋은 데이터 구조가 있습니다(여기서는 해시 테이블의 해시를 실행하고 있다고 가정합니다).제한된 메모리 용량에 저장해야 하는 요소가 "한정"이라는 것을 알고 있을 때 개인적으로 해시 테이블을 사용합니다.해시함수에 대해 생각하기 전에 데이터에 대한 간단한 통계 분석, 데이터의 분포 여부 등을 확인하려고 합니다.

언급URL : https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key