특수화 된 해시 테이블 C++

많은 항목을 세어 봐야합니다. 나는 다음과 같은 쌍의 목록 처리 해요 :특수화 된 해시 테이블 C++

A34223,34 
B23423,-23 
23423212,16

은 내가 무엇을 계획 한 것은 다음 스파 스 구조에 열쇠가 될 것입니다 32 비트 정수로 첫 번째 값 (키) 해시했다을 어디에 ' 값 '이 (모두 0에서 시작하여) 추가되고 음수가됩니다.

키가 짧고 영숫자이므로 32 비트 x86 아키텍처에서 빠른 해시 알고리즘을 생성 할 수있는 방법이 있습니까? 아니면 기존의 적합한 해시가 있습니까?

해시 디자인에 대해서는 잘 모르지만 간단한 입력으로 인해 주어진 키 길이 인 "X"에 대해 충돌이 발생하지 않는 고성능 해시가 생성되기를 기대합니다. 높은 분산을 가지므로 길이가 "X"를 초과하면 충돌을 최소화합니다.

출처

2009-06-05 Anonymous

C++을 사용하면서 가장 먼저해야 할 일은 std :: map을 사용하여 간단한 구현을 만드는 것입니다. 그것은 충분히 빠르습니까 (아마있을 것입니다)? 그렇다면 C++ 구현이 해시 테이블을 제공하는지 조사하십시오. 그렇다면 그것을 사용하여 간단한 구현을 만들고 테스트하고 시간을 정하십시오. 그것은 충분히 빠릅니다 (거의 확실합니다)?

사용자가 해시 테이블과 해시 함수를 구현 한 후에야 이러한 옵션을 사용할 수 있습니다.

출처

2009-06-05 13:36:07

감사합니다. 네가 옳아. 나는 사소한 것을 먼저 시도해야한다. 해싱 피스는 프로그램에서 별도의 기능으로 정상적으로 성능이 좋습니다. 이것은 실행 시간에 33 % 이상을 추가하지 않는 한 괜찮을 것입니다. –

충돌이 없다는 보장은 어렵습니다. 귀하의 경우에는

, 키

A34223 
B23423 
23423212

은 적은 노력으로 32 비트 정수로 변환 할 수 있습니다. 좋은 해시 함수에 대한

/** 
* "The Practice of Programming", Hash Tables, section 2.9, pg. 57 
* 
* computes hash value of string 
*/ 
DWORD 
strhash(char* str) 
{ 
    //#define MULTIPLIER 31 or 37 
    unsigned int h; 
    unsigned char* p; 

    h = 0; 
    for (p=(unsigned char*)str; *p != '\0'; p++) 
    h = 31 * h + *p; // <- FIXED MULTIPLIER 

    return h; 
}

출처

2009-06-05 13:41:56

확인 Bob Jenkin's website : 여기

그리고

문자열에서 해시를 생성하는 좋은 기능입니다. IIRC는 Perl에서 사용되는 것과 동일한 해시입니다.

출처

2009-06-05 13:45:43 florin

특수화 된 해시 테이블 C++

답변

관련 문제