완벽한 해시 (모든 연속 된 버킷이 가득 찼음), gperf 또는 대안을 만드시겠습니까?

Question

따라서 내가 원하는 것,이 전 미리 정의 된 키가 12 개월이 배열을 찾기위한 완벽한 해시 테이블을 구축하고자한다고 가정 해 봅시다

hash("January")==0 
hash("December")==11 

내가 gperf 통해 내 월 이름을 실행하고 좋은 해시 함수를 가지고, 16 개의 버킷을 제공하는 것으로 나타납니다 (또는 범위가 16 개).

#define MIN_HASH_VALUE 3 
#define MAX_HASH_VALUE 18 
/* maximum key range = 16, duplicates = 0 */ 

생성 gperf의 코드를 찾고, 그 해시 함수의 코드는 256 크기의 테이블에서 LEN 플러스 CHAR 값 룩업 단순 반환한다. 어떻게 든 내 머리 속에서 나는 상상력이 풍부한 기능을 상상할 수 있었다 ... :)

정확하게 12 개의 버킷을 원한다면 (즉, 사용하지 않은 버킷을 건너 뛰고 싶지 않다면)? 이처럼 작은 세트의 경우 실제로는 중요하지 않지만 1000 개의 미리 정의 된 키가 있고 정확히 1000 개의 버킷을 연속으로 원할 때?

결정적인 방법을 찾을 수 있습니까?

Answer 1

내가 알고있는 gperf의 유일한 대안은 cmph : http://cmph.sourceforge.net/이지만 Jerome이 의견에서 말했듯이 16 개의 버킷을 사용하면 속도가 향상됩니다.

내가 처음에 최소한의 완벽한 해싱을 보았을 때 나는 CiteseerX에 대해 매우 흥미로운 결과를 발견했지만 그 솔루션 중 하나를 직접 코딩하려고 시도한 유혹에 저항했습니다. 나는 gperf 또는 cmph에 대한 열등한 솔루션 존중으로 끝날 것임을 알고있다. 또는 솔루션이 비슷하다고 가정하더라도, 나는 그것에 많은 시간을 투자해야 할 것이다.

Answer 2

이 질문에 대한 답변에 &이 (가) gperf으로 검색되었습니다. 나는 gperf를 시도했지만 큰 입력 파일에서 매우 느려서 적합하지 않게 보였다. 나는 cmph를 시도했다. 그러나 나는 그것에 만족하지 않았다. 런타임시 C 프로그램에로드되는 파일을 빌드해야합니다. 또한, 프로그램은 매우 허약합니다 ("segmentation fault"로 어떤 유형의 실수 입력시라도) 나는 그것을 신뢰하지 않습니다. 추가 Google 검색을 통해 this page, 이후는 mph이되었습니다. 나는 mph를 다운로드했고 그것이 매우 멋지다는 것을 알았다. 그것은 "emitc"라는 C 파일을 생성 할 수있는 옵션 프로그램을 가지고 있으며,

mph < systemdictionaryfile | emitc > output.c 

은 거의 즉시 일 (약 20 만 단어의 사전과 몇 초)과 컴파일 작업 C 파일을 만든

처럼 사용 아무 문제 없어. 내 검사는 그것이 효과가 있다는 것을 나타냅니다. 아직 해시 알고리즘의 성능을 테스트하지는 못했습니다.