혼합 숫자 및 리터럴 식별자에 대한 최상의 해시 함수

Question

성능상의 이유로 문자열로 식별되는 개체 집합을 그룹으로 나눌 필요가 있습니다. 오브젝트는 하나 또는 다수 점 식별자의 일부를 분리 접두어 (정규화 된) 형태의 문자열에 의해 식별 될 수있다 :

12 
323 
12343 
2345233 
123123131 
ns1:my.label.one 
ns1:my.label.two 
ns1:my.label.three 
ns1:system.text.one 
ns2:edit.box.grey 
ns2:edit.box.black 
ns2:edit.box.mixed 

숫자 식별자는 1 내지 수백만한다. 텍스트 식별자는 같은 이름 공간 접두사 (ns1 :)와 동일한 경로 접두어 (edit.box)로 시작하는 경우가 많습니다.

이 용도로 가장 적합한 해시 함수는 무엇입니까? 객체 식별자 통계를 기반으로 버킷의 크기를 예측할 수 있다면 좋을 것입니다. 몇 가지 통계 정보를 기반으로 좋은 해시 함수를 작성하는 데 유용한 문서가 있습니까?

이러한 식별자는 수백만 개가 있지만 해시 함수에 따라 1-2,000 개 그룹으로 분할하는 것이 목적입니다.

Answer 1

두 가지 좋은 해시 함수를 모두 동일한 값 공간에 매핑 할 수 있으며 일반적으로 두 가지 해시 함수를 결합하여 새로운 문제가 발생하지 않습니다.

그래서 해쉬 함수는 다음과 같이 할 수 있습니다

if it's an integer value: 
    return int_hash(integer value) 
return string_hash(string value) 

주위에 특정 값이 N 버킷의 가능한 수를 N을 모듈로하여 정수의 응집이 아니라면, 다음 int_hash는 입력을 반환 할 수 있습니다.

문자열 해시를 선택하는 것은 새로운 문제가 아닙니다. 외설적 인 성능 요구 사항이없는 한 "djb2"(http://www.cse.yorku.ca/~oz/hash.html) 또는 유사하게 시도하십시오.

공통 접두어를 고려하여 해시 함수를 수정하는 데 많은 부분이 있다고 생각하지 않습니다. 해쉬 함수가 시작하는 것이 좋다면, 공통 접두어가 해쉬 값을 덩어리로 만들지는 않을 것입니다.

해시가 예기치 않게 성능이 좋지 않고 수천 개의 해시 값을 수천 개의 버킷에 넣으면 버킷 인구가 평균으로 분산됩니다 (몇 백만/1000) 및 분산 1/12 (수천)^2

버킷 당 평균 1500 개의 항목이 있으면 표준 편차가 약 430 정도가됩니다. 정규 분포의 95 %는 평균의 2 표준 편차 내에 있습니다 그래서 내 합계를 잘못하지 않으면 버킷의 95 %에 640-2360 항목이 포함됩니다. 적절한가요? 아니면 더 비슷한 크기의 버킷이 필요합니까?

Answer 2

sha1으로 가면서 원하는 크기로 자르면 안전 할 것입니다.

매우 효율적이지는 않지만, 아마도 해시 함수가 병목 현상이되지 않을까요?

Answer 3

CRC16은이 문자열에 사용할 수있는 합리적인 해시이고 그룹은 1-2000보다 커야합니다.

이렇게하면 해시 테이블이 약 1MB + 많은 항목을 포함하여 * 4 바이트가되어야하므로 50MB를 말하는 것이므로 모든 실제 데이터가 저장되므로 매우 작아야합니다.