C에 대한 최소 해시 함수?

C에 대한 최소 해시 함수?

나는 C를 고수해야 하고 C++을 사용할 수 없기 때문에 boost:hash를 사용할 수 없습니다.

그러나 토큰 문자열(5~40바이트 길이)을 대량(10K~100k)으로 해시해야 검색 속도가 빨라집니다.

MD5, SHA1 또는 긴 해시 함수는 단순한 작업에 비해 너무 무거운 것 같습니다. 암호화를 수행하지 않습니다.또한 스토리지 및 컴퓨팅 비용도 있습니다.

그러므로 나의 질문은:

1. 가장 실제적인 경우 충돌 방지를 보장하는 가장 간단한 해시 알고리즘은 무엇입니까?

2. 해시 값에 사용할 비트 수는 얼마입니까?저는 32비트 시스템을 개발하고 있습니다.Perl/Python의 해시 알고리즘도 32비트 해시를 사용합니까?아니면 64까지 뛰어야 하나요?

3. 일반적인 스크립트 언어로 해시 테이블을 구현하는 것과 관련하여: 구현이 충돌을 확인합니까? 아니면 그 부분을 완전히 피할 수 있습니까?

http://www.azillionmonkeys.com/qed/hash.html 에서 좋은 (그리고 빠른) 해시 함수와 흥미로운 읽을거리를 찾을 수 있습니다.

충돌을 확인하지 않는 유일한 방법은 완벽한 해시를 사용하는 것입니다. gperf와 같은 오래된 룩업 테이블입니다.

1. 다음은 가장 주목할 만한 알려진 해시 함수에 대한 좋은 개요입니다.

2. 32비트는 잘 작동할 것입니다.

3. 재미있는 해시 테이블을 쓰고 싶지 않다면 항상 충돌 여부를 확인해야 합니다 :)

해시 테이블 조회를 위한 일반 해시 함수입니다.암호화 목적으로 사용 안 함을 지정하지만, 암호화 목적이 없음을 지정했으므로 확인해야 합니다.

사용해 볼 해시 함수에 대한 설문 조사가 포함되어 있습니다.

만약 당신이 posix 유사한 시스템에 있고 일반 C를 고수한다면, 저는 단순히 시스템이 이미 제공하는 것을 사용할 것입니다. man 3 hcreate는 당신에게 모든 세부사항을 제공하거나 당신은 여기에서 온라인 버전을 찾을 수 있습니다. http://linux.die.net/man/3/hcreate .

긴 문자열은 Adler32를 사용하고 짧은 문자열은 Murmur2를 사용합니다.

xxhash는 매우 빠르고 쉬운 옵션입니다.간단한 코드는 다음과 같습니다.XXH32함수:

unsigned int XXH32 (const void* input, int len, unsigned int seed);

32비트 해시입니다.부터len이라int보다 큰 데이터의 경우2^31-1바이트 사용:

void*         XXH32_init   (unsigned int seed);
XXH_errorcode XXH32_update (void* state, const void* input, int len);
unsigned int  XXH32_digest (void* state);

언급URL : https://stackoverflow.com/questions/743939/a-minimal-hash-function-for-c