정수 해시 키를 허용하는 정수 해시 함수는 무엇입니까?

정수 해시 키를 허용하는 정수 해시 함수는 무엇입니까?

---

정수 해시 키를 허용하는 정수 해시 함수는 무엇입니까?

---

Knuth의 곱셈 방법 :

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

일반적으로 해시 크기 ( 2^32예제에서) 의 순서이고 공통 요인이없는 승수를 선택해야 합니다. 이렇게하면 해시 함수가 모든 해시 공간을 균일하게 처리합니다.

편집 :이 해시 함수의 가장 큰 단점은 분할 가능성을 유지한다는 것이므로 정수가 모두 2 또는 4로 나눌 수있는 경우 (흔하지 않은 경우) 해시도 마찬가지입니다. 이것은 해시 테이블의 문제입니다. 사용되는 버킷의 1/2 또는 1/4 만 사용하면됩니다.

---

다음 알고리즘이 매우 좋은 통계 분포를 제공한다는 것을 알았습니다. 각 입력 비트는 약 50 % 확률로 각 출력 비트에 영향을줍니다. 충돌이 없습니다 (각 입력이 다른 출력을 생성 함). 알고리즘은 CPU에 내장 정수 곱셈 단위가없는 경우를 제외하고는 빠릅니다. C 코드는 가정 int32 비트 (자바 대체이다 >>으로 >>>및 삭제 unsigned)

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

매직 넘버는 여러 시간 동안 실행 된 특수 멀티 스레드 테스트 프로그램 을 사용하여 계산되었으며 , 눈사태 효과 (단일 입력 비트가 변경되면 변경되는 출력 비트 수, 평균적으로 거의 16이어야 함), 독립성을 계산합니다. 출력 비트 변경 (출력 비트가 서로 의존해서는 안 됨) 및 입력 비트가 변경 될 경우 각 출력 비트가 변경 될 확률. 계산 된 값은 MurmurHash 에서 사용하는 32 비트 파이널 라이저보다 낫고 AES 를 사용할 때와 거의 비슷 합니다. 약간의 장점은 동일한 상수가 두 번 사용된다는 것입니다 (마지막으로 테스트했을 때 약간 더 빨라졌지만 여전히 사실인지 확실하지 않습니다).

당신은 당신이 대체하는 경우 (해시에서 입력 값을 얻을) 과정을 되돌릴 수 0x45d9f3b와 함께 0x119de1f3합니다 ( 역수 ) :

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 (mix 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;
}

자바, 사용을 위해 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;
}

업데이트 : 다른 (아마도 더 나은) 상수가 나열 되는 Hash Function Prospector 프로젝트 를 살펴볼 수도 있습니다.

---

데이터가 배포되는 방식에 따라 다릅니다. 간단한 카운터의 경우 가장 간단한 기능

f(i) = i

좋을 것입니다 (최적이라고 생각하지만 증명할 수는 없습니다).

---

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

---

• 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 비트 (좋은 배포) : MurmurHash

• 정수 해시 함수

---

Eternally Confuzzled의 일부 해시 알고리즘에 대한 멋진 개요가 있습니다 . 눈사태에 빠르게 도달하므로 효율적인 해시 테이블 조회에 사용할 수있는 Bob Jenkins의 한 번에 하나씩 해시를 권장합니다.

---

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

• 그것을 어디에 사용 하시겠습니까?
• 해시로 무엇을하려고합니까?
• 암호 학적으로 안전한 해시 함수가 필요합니까?

SHA-1 등과 같은 해시 함수 의 Merkle-Damgard 제품군을 살펴볼 것을 제안합니다.

---

사전에 데이터를 알지 않고는 해시 함수가 "좋다"고 말할 수 없다고 생각합니다! 그리고 당신이 그것으로 무엇을 할 것인지 모른 채.

알 수없는 데이터 크기에 대한 해시 테이블보다 더 나은 데이터 구조가 있습니다 (여기에서 해시 테이블에 대한 해싱을 수행한다고 가정합니다). 제한된 양의 메모리에 저장해야하는 "제한된"수의 요소가 있다는 것을 알 때 개인적으로 해시 테이블을 사용합니다. 해시 함수에 대해 생각하기 전에 데이터에 대한 빠른 통계 분석을 시도하고 데이터가 어떻게 배포되는지 확인합니다.

---

빠르고 좋은 해시 함수는 다음과 같이 품질이 낮은 빠른 순열로 구성 될 수 있습니다.

• 고르지 않은 정수로 곱하기
• 이진 회전
• xorshift

난수 생성을 위해 PCG 로 입증 된 것과 같이 우수한 품질의 해싱 함수를 생성합니다.

이것은 사실 rrxmrrxmsx_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 = 0x5555555555555555; // 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로 모든 출력 비트를 뒤집어 야합니다.

먼저 identity 함수를 살펴 보겠습니다. 1은 충족하지만 2는 충족하지 않습니다. :

입력 비트 n은 100 % (빨간색)의 상관 관계로 출력 비트 n을 결정하고 나머지는 없음이므로 파란색이므로 완벽한 빨간색 선을 제공합니다.

A xorshift(n,32) is not much better, yielding one and half a line. Still satisfying 1., because it is invertible with a second application.

A multiplication with an unsigned integer is much better, cascading more strongly and flipping more output bits with a probability of 0.5, which is what you want, in green. I satisfies 1. as for each uneven integer there is a multiplicative inverse.

Combining the two gives the following output, still satisfying 1. as the composition of two bijective functions yields another bijective function.

A second application of multiplication and xorshift will yield the following:

Or you can use Galois field multiplications like GHash, they have become reasonably fast on modern CPUs and have superior qualities in one step.

   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];                                              
   }

---

For random hash values, some engineers said golden ratio prime number(2654435761) is a bad choice, with my testing results, I found that it's not true; instead, 2654435761 distributes the hash values pretty good.

#define MCR_HashTableSize 2^10

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

The hash table size must be a power of two.

I have written a test program to evaluate many hash functions for integers, the results show that GRPrimeNumber is a pretty good choice.

I have tried:

1. total_data_entry_number / total_bucket_number = 2, 3, 4; where total_bucket_number = hash table size;
2. map hash value domain into bucket index domain; that is, convert hash value into bucket index by Logical And Operation with (hash_table_size - 1), as shown in Hash_UInt_GRPrimeNumber();
3. calculate the collision number of each bucket;
4. record the bucket that has not been mapped, that is, an empty bucket;
5. find out the max collision number of all buckets; that is, the longest chain length;

With my testing results, I found that Golden Ratio Prime Number always has the fewer empty buckets or zero empty bucket and the shortest collision chain length.

Some hash functions for integers are claimed to be good, but the testing results show that when the total_data_entry / total_bucket_number = 3, the longest chain length is bigger than 10(max collision number > 10), and many buckets are not mapped(empty buckets), which is very bad, compared with the result of zero empty bucket and longest chain length 3 by Golden Ratio Prime Number Hashing.

BTW, with my testing results, I found one version of shifting-xor hash functions is pretty good(It's shared by mikera).

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

---

I have been using splitmix64 (pointed in Thomas Mueller's answer) ever since I found this thread. However, I recently stumbled upon Pelle Evensen's rrxmrrxmsx_0, which yielded tremendously better statistical distribution than the original MurmurHash3 finalizer and its successors (splitmix64 and other mixes). Here is the code snippet in 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 also provides an in-depth analysis of the 64-bit mixer used in the final step of MurmurHash3 and the more recent variants.

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