algorithm

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

• 고르지 않은 정수로 곱하기
• 이진 회전
• 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 = 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로 모든 출력 비트를 뒤집어 야합니다.

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

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

xorshift (n, 32)는 그다지 좋지 않으며 한 줄 반을 산출합니다. 두 번째 응용 프로그램으로 뒤집을 수 있기 때문에 여전히 1. 만족합니다.

부호없는 정수를 사용한 곱셈이 훨씬 더 낫습니다. 더 강하게 계단식으로 연결되고 더 많은 출력 비트를 녹색으로 원하는 0.5 확률로 뒤집습니다. 그것은 1을 만족합니다. 각 고르지 않은 정수에 대해 곱셈 역이 있습니다.

두 가지를 결합하면 다음과 같은 결과가 나옵니다. 두 개의 bijective 함수의 구성이 다른 bijective 함수를 생성하므로 여전히 1을 만족합니다.

곱셈과 xorshift를 두 번째로 적용하면 다음이 생성됩니다.

또는 GHash 와 같은 Galois 필드 곱셈을 사용할 수 있습니다 . 최신 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];
   }

---

답변