문자열에 대한 해시 함수

문자열에 대한 해시 함수

---

C 언어로 된 해시 테이블에서 작업 중이며 문자열에 대한 해시 함수를 테스트하고 있습니다.

내가 시도한 첫 번째 기능은 ascii 코드를 추가하고 모듈로 (% 100)를 사용하는 것이지만 첫 번째 데이터 테스트에서 좋지 않은 결과를 얻었습니다 : 130 단어에 대해 40 개의 충돌.

최종 입력 데이터에는 8 000 단어가 포함됩니다 (파일에 사전 저장 됨). 해시 테이블은 int table [10000]로 선언되며 txt 파일에서 단어의 위치를 ​​포함합니다.

첫 번째 질문은 문자열 해싱에 가장 적합한 알고리즘은 무엇입니까? 해시 테이블의 크기를 결정하는 방법은 무엇입니까?

미리 감사드립니다!

:-)

---

나는 djb2Dan Bernstein으로 좋은 결과를 얻었습니다 .

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;
}

---

첫째, 일반적으로 해시 테이블에 암호화 해시를 사용하고 싶지 않습니다 . 암호화 표준에 따라 매우 빠른 알고리즘은 해시 테이블 표준에 의해 여전히 매우 느립니다.

둘째, 입력의 모든 비트가 결과에 영향을 미칠 수 있는지 확인하려고합니다. 이를 수행하는 한 가지 쉬운 방법은 현재 결과를 일부 비트 수만큼 회전시킨 다음 현재 해시 코드를 현재 바이트와 XOR하는 것입니다. 문자열 끝에 도달 할 때까지 반복합니다. 일반적으로 회전이 바이트 크기의 배수가되는 것을 원하지 않습니다 .

예를 들어 8 비트 바이트의 일반적인 경우를 가정하면 5 비트 씩 회전 할 수 있습니다.

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

편집 : 또한 10000 개의 슬롯이 해시 테이블 크기에 적합한 선택은 거의 없습니다. 일반적으로 두 가지 중 하나를 원합니다. 크기로 소수를 원하거나 (일부 유형의 해시 해상도로 정확성을 보장하는 데 필요함) 그렇지 않으면 2의 거듭 제곱을 원합니다 (따라서 값을 올바른 범위로 줄이는 것은 간단한 방법으로 수행 할 수 있습니다. 비트 마스크).

---

C 표준 라이브러리 hcreate / hdestroy / hsearch에서 APR 및 glib 의 C에 대한 기존 해시 테이블 구현이 많이 있으며 , 이는 사전 빌드 된 해시 함수도 제공합니다. 고유 한 해시 테이블이나 해시 함수를 개발하는 것보다 사용하는 것이 좋습니다. 일반적인 사용 사례에 맞게 크게 최적화되었습니다.

그러나 데이터 세트가 정적 인 경우 가장 좋은 해결책은 완벽한 해시 를 사용하는 것입니다 . gperf 는 주어진 데이터 세트에 대해 완벽한 해시를 생성합니다.

---

Wikipedia는 Jenkins One At 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;
}

---

첫째, 0..99로 해시 된 130 개의 단어에 대해 40 개의 충돌이 나쁘나요? 특별한 조치를 취하지 않으면 완벽한 해싱을 기대할 수 없습니다. 일반적인 해시 함수는 대부분의 경우 랜덤 생성기보다 충돌이 적지 않습니다.

평판이 좋은 해시 함수는 MurmurHash3 입니다.

Finally, regarding the size of the hash table, it really depends what kind of hash table you have in mind, especially, whether buckets are extensible or one-slot. If buckets are extensible, again there is a choice: you choose the average bucket length for the memory/speed constraints that you have.

---

I have tried these hash functions and got the following result. I have about 960^3 entries, each 64 bytes long, 64 chars in different order, hash value 32bit. Codes from here.

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

One strange things is that almost all the hash functions have 6% collision rate for my data.

---

Though djb2, as presented on stackoverflow by cnicutar, is almost certainly better, I think it's worth showing the K&R hashes too:

1) Apparently a terrible hash algorithm, as presented in K&R 1st edition (source)

unsigned long hash(unsigned char *str)
{
    unsigned int hash = 0;
    int c;

    while (c = *str++)
        hash += c;

    return hash;
}

2) Probably a pretty decent hash algorithm, as presented in K&R version 2 (verified by me on pg. 144 of the book); NB: be sure to remove % HASHSIZE from the return statement if you plan on doing the modulus sizing-to-your-array-length outside the hash algorithm. Also, I recommend you make the return and "hashval" type unsigned long instead of the simple unsigned (int).

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval % HASHSIZE;
}

Note that it's clear from the two algorithms that one reason the 1st edition hash is so terrible is because it does NOT take into consideration string character order, so hash("ab") would therefore return the same value as hash("ba"). This is not so with the 2nd edition hash, however, which would (much better!) return two different values for those strings.

The GCC C++11 hashing functions used for unordered_map (a hash table template) and unordered_set (a hash set template) appear to be as follows.

• This is a partial answer to the question of what are the GCC C++11 hash functions used, stating that GCC uses an implementation of "MurmurHashUnaligned2", by Austin Appleby (http://murmurhash.googlepages.com/).
• In the file "gcc/libstdc++-v3/libsupc++/hash_bytes.cc", here (https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc), I found the implementations. Here's the one for the "32-bit size_t" return value, for example (pulled 11 Aug 2017):

Code:

// 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;
}

---

djb2 has 317 collisions for this 466k english dictionary while MurmurHash has none for 64 bit hashes, and 21 for 32 bit hashes (around 25 is to be expected for 466k random 32 bit hashes). My recommendation is using MurmurHash if available, it is very fast, because it takes in several bytes at a time. But if you need a simple and short hash function to copy and paste to your project I'd recommend using murmurs one-byte-at-a-time version:

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;
}

The optimal size of a hash table is - in short - as large as possible while still fitting into memory. Because we don't usually know or want to look up how much memory we have available, and it might even change, the optimal hash table size is roughly 2x the expected number of elements to be stored in the table. Allocating much more than that will make your hash table faster but at rapidly diminishing returns, making your hash table smaller than that will make it exponentially slower. This is because there is a non-linear trade-off between space and time complexity for hash tables, with an optimal load factor of 2-sqrt(2) = 0.58... apparently.

---

One thing I've used with good results is the following (I don't know if its mentioned already because I can't remember its name).

You precompute a table T with a random number for each character in your key's alphabet [0,255]. You hash your key 'k0 k1 k2 ... kN' by taking T[k0] xor T[k1] xor ... xor T[kN]. You can easily show that this is as random as your random number generator and its computationally very feasible and if you really run into a very bad instance with lots of collisions you can just repeat the whole thing using a fresh batch of random numbers.

참고URL : https://stackoverflow.com/questions/7666509/hash-function-for-string