문자열의 해시 함수
C 언어로 해시 테이블을 작업 중이고 문자열 해시함수를 테스트하고 있어.
내가 시도한 첫 번째 기능은 아스키 코드를 추가하고 modulo를 사용하는 것이다.% 100( ) 그러나 나는 첫 번째 데이터 테스트에서 나쁜 결과를 얻었다: 130 단어에 40건의 충돌.
최종 입력 데이터는 8000개의 단어를 포함할 것이다.해시 테이블은 다음과 같이 선언된다.int table[10000]그리고 .txt 파일에 단어의 위치가 포함되어 있다.
- 해싱 문자열에 가장 적합한 알고리즘은?
- 해시 테이블의 크기를 결정하는 방법은?
나는 댄 번스타인의 좋은 결과를 얻었다.
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
djb2는 이 466k 영어 사전의 경우 317건의 충돌이 있고, DumorHash는 64비트 해시의 경우 317건의 충돌이 없고 32비트 해시의 경우 21건의 충돌이 예상된다(466k 랜덤 32비트 해시의 경우 약 25건이 예상됨).내가 추천하는 것은 가능하다면 DumorHash를 사용하는 것이다. 한 번에 몇 바이트씩 걸리기 때문에 매우 빠르다.그러나 당신의 프로젝트에 복사하여 붙여넣기 위해 간단하고 짧은 해시함수가 필요하다면 나는 한 번에 한 바이트씩 중얼거릴 것을 권하고 싶다.
uint32_t inline MurmurOAAT32 ( const char * key)
{
uint32_t h(3323198485ul);
for (;*key;++key) {
h ^= *key;
h *= 0x5bd1e995;
h ^= h >> 15;
}
return h;
}
uint64_t inline MurmurOAAT64 ( const char * key)
{
uint64_t h(525201411107845655ull);
for (;*key;++key) {
h ^= *key;
h *= 0x5bd1e9955bd1e995;
h ^= h >> 47;
}
return h;
}
해시 테이블의 최적 크기는 메모리에 여전히 적합하면서 가능한 한 크다.우리는 보통 우리가 얼마나 많은 메모리를 사용할 수 있는지 알지도 못하거나 찾고 싶기 때문에, 그리고 그것은 심지어 바뀔 수도 있기 때문에, 최적의 해시 테이블 크기는 표에 저장될 예상 요소 수의 대략 2배이다.그것보다 훨씬 더 많이 할당하면 해시 테이블이 더 빨라지지만 수익률이 급격히 감소할 때, 해시 테이블이 그것보다 더 작아지면 해시 테이블이 기하급수적으로 느려질 것이다.해시 테이블의 공간과 시간 복잡성 사이에 비선형 트레이드오프가 존재하기 때문인데, 최적의 부하율은 2-sqrt(2) = 0.58... 분명해 보인다.
첫째, 일반적으로 해시 테이블에는 암호화 해시를 사용하지 않으려는 경우.암호 표준에 의해 매우 빠른 알고리즘은 여전히 해시 테이블 표준에 의해 엄청나게 느리다.
둘째, 입력의 모든 비트가 결과에 영향을 미칠 수 있는지 확인하려고 한다.그렇게 하는 한 가지 쉬운 방법은 현재 결과를 몇 비트만큼 회전시킨 다음 현재 바이트로 현재 해시 코드를 XOR하는 것이다.끈의 끝에 도달할 때까지 반복한다.일반적으로 회전도 바이트 크기의 짝수 배수가 되는 것을 원하지 않는다.
예를 들어, 일반적인 경우 8비트 바이트라고 가정하면 다음과 같이 5비트씩 회전할 수 있다.
int hash(char const *input) {
int result = 0x55555555;
while (*input) {
result ^= *input++;
result = rol(result, 5);
}
}
편집: 또한 10000개의 슬롯이 해시 테이블 크기에 적합한 경우는 드물다는 점에 유의하십시오.일반적으로 크기(일부 유형의 해시 분해능에서 정확성을 보장하기 위해 필요함) 또는 2의 검정력(단순 비트 마스크로 값을 줄일 수 있음) 중 하나를 원하는 경우
위키피디아는 Jenkins One A Time Hash라는 멋진 문자열 해시 함수를 보여준다.그것은 또한 이 해시의 개선된 버전을 인용한다.
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
uint32_t hash, i;
for(hash = i = 0; i < len; ++i)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
djb2좋다
cnicutar에 의한 stackoverflow에 대해 제시된 바와 같이, 거의 확실히 더 낫지만, 나는 K&R 해시 또한 보여줄 가치가 있다고 생각한다.
K&R 해시들 중 하나는 형편없고, 하나는 아마 꽤 훌륭할 것이다.
- K&R 제1판(출처)에 제시된 해시 알고리즘이 명백히 형편없다.
unsigned long hash(unsigned char *str) { unsigned int hash = 0; int c; while (c = *str++) hash += c; return hash; } - 아마도 K&R 버전 2에서 제시된 꽤 괜찮은 해시 알고리즘일 것이다. (본서의 페이지 144에서 내가 검증함); NB: 반드시 제거해야 한다.
% HASHSIZE해시 알고리즘 외부에서 어레이 길이와 일치하는 계량형 크기를 지정할 계획인 경우 반환 명령문을 참조하십시오.또한, 반품과 "해시발" 타입을 만드세요.unsigned long또는 더 나은 방법:uint32_t또는uint64_t, 단순한 것 대신에unsigned(내부)unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31*hashval; return hashval % HASHSIZE; }
1판 해시가 그렇게 끔찍한 이유는 문자열 문자 순서를 고려하지 않기 때문에 두 알고리즘을 통해 명확하다는 점에 유의하십시오.hash("ab")따라서 와 같은 값을 반환할 것이다.hash("ba")그러나 제2판 해시는 그렇지 않다. 이 해시는 그 문자열들에 대해 두 개의 다른 값을 반환할 것이다.
은 GCC C++11 해싱기 입니다.std::unordered_map<>템플릿 컨테이너 해시 테이블이 우수함.
(해시 테이블 템플릿) 및 (해시 세트 템플릿)에 사용되는 GCC C++11 해싱 함수는 다음과 같이 나타난다.
- 이는 GCC가 오스틴 애플비(http://murmurhash.googlepages.com/))의 'MurmurHashUnligned2' 구현을 사용한다고 명시한 GCC C++11 해시함수가 무엇이냐는 질문에 대한 부분적인 답변이다.
- "gcc/libstdc++-v3/libsupc++/libsupc+/libs_reason.cc" 파일에서 구현을 찾았다.32비트 size_t" 반환 값(예: (2017년 8월 11일)의 경우:
코드:
// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
const size_t m = 0x5bd1e995;
size_t hash = seed ^ len;
const char* buf = static_cast<const char*>(ptr);
// Mix 4 bytes at a time into the hash.
while (len >= 4)
{
size_t k = unaligned_load(buf);
k *= m;
k ^= k >> 24;
k *= m;
hash *= m;
hash ^= k;
buf += 4;
len -= 4;
}
// Handle the last few bytes of the input array.
switch (len)
{
case 3:
hash ^= static_cast<unsigned char>(buf[2]) << 16;
[[gnu::fallthrough]];
case 2:
hash ^= static_cast<unsigned char>(buf[1]) << 8;
[[gnu::fallthrough]];
case 1:
hash ^= static_cast<unsigned char>(buf[0]);
hash *= m;
};
// Do a few final mixes of the hash.
hash ^= hash >> 13;
hash *= m;
hash ^= hash >> 15;
return hash;
}
오스틴 애플비의 MurmerHash3가 최고야!심지어 그의 gcc C++11에 비하면 개선된 것이다.std::unordered_map<>위에서 사용한 해시
이 모든 것 중 최고일 뿐만 아니라, 오스틴은 머머해쉬3를 공공 영역으로 방출했다.여기에 대한 다른 답변을 참조하십시오.C++ std에 사용되는 기본 해시함수란?:unordered_map?
참고 항목
- 시도 및 테스트할 기타 해시 테이블 알고리즘: http://www.cse.yorku.ca/~oz/message.message.messages.여기서 언급된 해시 알고리즘:
- djb2
- sdbm
- 진다(K&R 1판)
샤오닝 비안의 대답을 검증하고 싶었지만 안타깝게도 그는 코드를 올리지 않았다.그래서 나는 작은 테스트 세트를 구현했고 466K 영어 단어 목록에 각각에 대한 충돌 횟수를 보기 위해 다른 해싱 기능을 실행했다.
Hash function | Collisions | Time (words) | Time (file)
=================================================================
CRC32 | 23 (0.005%) | 112 ms | 38 ms
MurmurOAAT | 26 (0.006%) | 86 ms | 10 ms
FNV hash | 32 (0.007%) | 87 ms | 7 ms
Jenkins OAAT | 36 (0.008%) | 90 ms | 8 ms
DJB2 hash | 344 (0.074%) | 87 ms | 5 ms
K&R V2 | 356 (0.076%) | 86 ms | 5 ms
Coffin | 763 (0.164%) | 86 ms | 4 ms
x17 hash | 2242 (0.481%) | 87 ms | 7 ms
-----------------------------------------------------------------
MurmurHash3_x86_32 | 19 (0.004%) | 90 ms | 3 ms
나는 모든 단어를 개별적으로 해싱하고 모든 영어 단어의 전체 파일을 해싱하는 시간을 둘 다 포함시켰다.더 복잡한 것도 포함했고MurmurHash3_x86_32참고용으로 시험해 봤어
결론:
- 인텔 x86-64 아키텍처에서 문자열에 인기 있는 DJB2 해시함수를 사용하는 것은 거의 의미가 없다.왜냐하면 처리량은 매우 유사하지만 유사한 기능(MurmurOATH, FNV, Jenkins OATH)보다 훨씬 많은 충돌을 가지고 있기 때문이다.번스타인의 DJB2는 특히 짧은 현에서 좋지 않은 활약을 한다.충돌 예:
Liz/MHz,Bon/COM,Rey/SEX.
테스트 코드:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#define MAXLINE 2048
#define SEED 0x12345678
uint32_t DJB2_hash(const uint8_t *str)
{
uint32_t hash = 5381;
uint8_t c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
uint32_t FNV(const void* key, int len, uint32_t h)
{
// Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
h ^= 2166136261UL;
const uint8_t* data = (const uint8_t*)key;
for(int i = 0; i < len; i++)
{
h ^= data[i];
h *= 16777619;
}
return h;
}
uint32_t MurmurOAAT_32(const char* str, uint32_t h)
{
// One-byte-at-a-time hash based on Murmur's mix
// Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
for (; *str; ++str) {
h ^= *str;
h *= 0x5bd1e995;
h ^= h >> 15;
}
return h;
}
uint32_t KR_v2_hash(const char *s)
{
// Source: https://stackoverflow.com/a/45641002/5407270
uint32_t hashval = 0;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31*hashval;
return hashval;
}
uint32_t Jenkins_one_at_a_time_hash(const char *str, size_t len)
{
uint32_t hash, i;
for(hash = i = 0; i < len; ++i)
{
hash += str[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
uint32_t crc32b(const uint8_t *str) {
// Source: https://stackoverflow.com/a/21001712
unsigned int byte, crc, mask;
int i = 0, j;
crc = 0xFFFFFFFF;
while (str[i] != 0) {
byte = str[i];
crc = crc ^ byte;
for (j = 7; j >= 0; j--) {
mask = -(crc & 1);
crc = (crc >> 1) ^ (0xEDB88320 & mask);
}
i = i + 1;
}
return ~crc;
}
inline uint32_t _rotl32(uint32_t x, int32_t bits)
{
return x<<bits | x>>(32-bits); // C idiom: will be optimized to a single operation
}
uint32_t Coffin_hash(char const *input) {
// Source: https://stackoverflow.com/a/7666668/5407270
uint32_t result = 0x55555555;
while (*input) {
result ^= *input++;
result = _rotl32(result, 5);
}
return result;
}
uint32_t x17(const void * key, int len, uint32_t h)
{
// Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
const uint8_t * data = (const uint8_t*)key;
for (int i = 0; i < len; ++i)
{
h = 17 * h + (data[i] - ' ');
}
return h ^ (h >> 16);
}
uint32_t apply_hash(int hash, const char* line)
{
switch (hash) {
case 1: return crc32b((const uint8_t*)line);
case 2: return MurmurOAAT_32(line, SEED);
case 3: return FNV(line, strlen(line), SEED);
case 4: return Jenkins_one_at_a_time_hash(line, strlen(line));
case 5: return DJB2_hash((const uint8_t*)line);
case 6: return KR_v2_hash(line);
case 7: return Coffin_hash(line);
case 8: return x17(line, strlen(line), SEED);
default: break;
}
return 0;
}
int main(int argc, char* argv[])
{
// Read arguments
const int hash_choice = atoi(argv[1]);
char const* const fn = argv[2];
// Read file
FILE* f = fopen(fn, "r");
// Read file line by line, calculate hash
char line[MAXLINE];
while (fgets(line, sizeof(line), f)) {
line[strcspn(line, "\n")] = '\0'; // strip newline
uint32_t hash = apply_hash(hash_choice, line);
printf("%08x\n", hash);
}
fclose(f);
return 0;
}
P.S. 현대 해시함수의 속도와 품질에 대한 보다 포괄적인 검토는 라이니 어반(rurban)의 SMHasher 저장소에서 찾아볼 수 있다.표의 "품질 문제" 열에 주목하십시오.
C 표준 라이브러리 hcreate/hdestroy/hsearch에서 APR 및 glib에 이르기까지 C에 대한 기존 해시테이블 구현이 다수 존재하며, 사전 구축된 해시함수도 제공한다.나는 당신만의 해시태블이나 해시함수를 개발하기 보다는 그것들을 사용하는 것을 적극 추천하고 싶다. 그것들은 일반적인 사용 사례에 매우 최적화되어 있다.
그러나 데이터 집합이 정적인 경우 최상의 솔루션은 완벽한 해시를 사용하는 것일 수 있다. gperf는 주어진 데이터 집합에 대해 완벽한 해시를 생성한다.
나는 이러한 해시함수를 사용해보고 다음과 같은 결과를 얻었다.나는 약 960^3개의 항목을 가지고 있는데, 각 64바이트 길이, 64자 순서가 다른 해시 값 32비트를 가지고 있다.여기서부터 코드.
Hash function | collision rate | how many minutes to finish
==============================================================
MurmurHash3 | 6.?% | 4m15s
Jenkins One.. | 6.1% | 6m54s
Bob, 1st in link | 6.16% | 5m34s
SuperFastHash | 10% | 4m58s
bernstein | 20% | 14s only finish 1/20
one_at_a_time | 6.16% | 7m5s
crc | 6.16% | 7m56s
한 가지 이상한 점은 거의 모든 해시함수가 내 데이터에 대해 6%의 충돌률을 가지고 있다는 것이다.
첫째, 130단어의 충돌 40개가 0으로 되어있다.99나쁨? 만약 당신이 특별한 조치를 취하지 않는다면 완벽한 해싱을 기대할 수 없다.일반적인 해시함수는 대부분 무작위 생성기보다 적은 충돌을 가지지 않을 것이다.
평판이 좋은 해시함수는 DumorHash3이다.
마지막으로 해시 테이블의 크기에 관해서는, 특히 버킷이 확장 가능한지, 한 슬롯인지, 어떤 종류의 해시 테이블을 염두에 두고 있느냐에 따라 정말로 달라진다.버킷이 확장 가능한 경우 다시 한 번 선택할 수 있으며, 메모리/속도 제약 조건에 대한 평균 버킷 길이를 선택하십시오.
한 가지 좋은 결과를 가지고 사용한 것은 다음과 같다(이름이 기억나지 않아 이미 언급된 것인지는 모르겠다).
키 알파벳 [0,255]에서 각 문자마다 임의의 숫자로 테이블 T를 미리 계산한다.T[k0] xor T[k1] xor t[k1] xor를 사용하여 키 'k0 k1 k2 ... kN'을 해시하십시오.Xor T[kN]여러분은 이것이 여러분의 난수 생성기처럼 무작위적이고 계산적으로 매우 실현 가능하다는 것을 쉽게 보여줄 수 있고 만약 여러분이 많은 충돌로 매우 나쁜 상황에 부딪힌다면, 새로운 난수들을 사용하여 모든 것을 반복할 수 있다.
참조URL: https://stackoverflow.com/questions/7666509/hash-function-for-string
'programing' 카테고리의 다른 글
| 하위 구성 요소를 기반으로 계산된 속성 (0) | 2022.04.18 |
|---|---|
| Vue: v-for에서 메소드를 사용하지만 Getter가 준비되지 않음 (0) | 2022.04.18 |
| InputStream을 Java의 String으로 읽거나 변환하는 방법 (0) | 2022.04.18 |
| VueJ를 사용하여 테이블에서 행 제거s (0) | 2022.04.18 |
| 어떻게 gcc가 C의 일부 문구를 최적화하는 것을 방지할 수 있는가? (0) | 2022.04.18 |