4 개의 부호없는 정수에 대한 해시 함수 (C++)

Question

지금은 특정 함수의 출력으로 4 개의 부호없는 32 비트 정수를 생성하는 프로그램을 작성하고 있습니다. 이 4 개의 정수를 해쉬하고 싶기 때문에이 함수의 출력을 미래의 출력과 비교할 수 있습니다.

그래도 괜찮은 해시 함수를 작성하는 데 문제가 있습니다. 처음에이 코드를 작성했을 때, 필자는 4 개의 정수 각각을 간단히 추가하여 던졌습니다. 나는 이동 및 추가와 같은 몇 가지 다른 기술을 사용해 보았습니다. 해시를 얻지 만 품질이 떨어지며 함수가 많은 충돌을 발생시킵니다.

해시 출력은 32 비트 또는 64 비트 정수일 수 있습니다. 문제의 함수는 수십억 개의 해시를 생성하므로 여기서는 충돌이 실제 문제이며 더 큰 변수를 사용하여 가능한 한 적은 충돌이 발생하도록합니다.

아무도 내가 품질 해시 함수를 작성하는 방법을 알아낼 수 있습니까?

Answer 1

네 개의 정수를 적절한 데이터 구조에 저장하고 모두 비교하지 않는 이유는 무엇입니까? 이 경우 해싱의 이점은 스토리지가 문제가 아닌 한 내게 모호한 것으로 나타납니다.

저장소에 문제가있는 경우 분석 된 해시 함수 중 하나 인 here을 사용할 수 있습니다.

Answer 2

해시가 충돌을 생성 할 수 있으므로 이러한 충돌을 발견하기 위해 메모리에 키를 보관해야합니다. Hashmaps 및 다른 표준 데이터 구조는 내부 부기에서이를 수행합니다.

키가 너무 작기 때문에 해시가 아니라 직접 키를 사용하십시오. 이것은 더 빠르며 충돌을 방지합니다.

Answer 3

왜 해시가 필요합니까? std :: set 또는 std :: multi 세트가 이런 종류의 출력을 저장하는 데 더 적합 할 것으로 보입니다. 당신이해야 할 일은 struct에 4 개의 정수를 감싸고 간단한 비교 함수를 작성하는 것입니다.

Answer 4

CRC 또는 FNV을 사용해보세요. FNV는 빠르기 때문에 "작은"해시 값 (예 : 12 비트/24 비트/등)을 얻기 위해 비트를 폴드하는 정의 된 방법이 있습니다.

128 비트 (4 X 32 비트) 숫자로 64 비트 해시를 생성하면 다른 사람들이 제안 했으므로 원래 값을 키로 사용할 수 있기 때문에 약간의 의문이 있습니다. 세트. 원래 해시 값의 수를 나타내는 해시 비트 수를 원합니다. 예를 들어 데이터 집합에 100,000 개의 4X32 비트 값이있는 경우 64 비트 해시가 아닌 17 비트 또는 18 비트 해시 값을 원할 수 있습니다.

Answer 5

조금 지나치지 만, Boost.Hash을 고려해보십시오. 아주 간단한 코드와 좋은 값을 생성합니다.

Answer 6

나는 Vinko에 완전히 동의합니다. 모든 것을 비교해보십시오. 그래도 좋은 해싱 함수가 필요하다면, 4 개의 unsinged 정수의 분포를 분석해야합니다. 그런 다음 해시 함수를 조작하여 결과가 32 비트 해시 값의 전체 범위에 걸쳐 분산되도록해야합니다.

간단한 예제 - 대부분의 경우 각 함수의 결과가 0에서 255까지의 범위에 있다고 가정 해 봅니다. 그러면 각 함수의 하위 8 비트를 해시에 쉽게 혼합 할 수 있습니다. 대부분의 경우, 결과를 직접 찾을 수 있습니다. 때로는 (한 함수가 더 큰 결과를 반환 할 때) 충돌이 발생할 수 있습니다.

4 가지 기능의 결과가 어떻게 분배되었는지에 대한 정보없이 요약하면 좋은 해싱 기능으로 당신을 도울 수 없습니다.

Answer 7

여기서 정수 1 내지 4의 정수를 상당히 합리적인 해쉬 함수이다 : 균일하게 분산 입력에

unsigned int hash = in[0]; 
hash *= 37; 
hash += in[1]; 
hash *= 37; 
hash += in[2]; 
hash *= 37; 
hash += in[3]; 

균일하게 분산 된 출력을 제공한다. 입력의 모든 비트가 출력에 참여하며 모든 입력 비트가 모든 출력 비트에 영향을 미칠 수 있습니다. 출력을 생성하는 함수보다 속도가 빠르므로 성능에 문제가 없습니다.

다른 특성을 가진 다른 해시가 있지만, 소수로 누적 된 누적은 다른 방법으로 입증 될 때까지 좋은 시작입니다. 원한다면 추가 대신 xor로 누적 해 볼 수도 있습니다. 어느 쪽이든, 충돌을 생성하는 것은 쉽습니다 (예를 들어 {1, 0, a, b}는 모든 a, b에 대해 {0, 37, a, b}와 충돌합니다, 그래서 당신은 생각하는 소수를 고를 수 있습니다 함수의 그럴듯한 구현 버그와 관련이 없습니다. 따라서 함수에 모듈로 37 산술 연산이 많이있는 경우 대신 1000003을 사용하십시오.