[c] 문자열에 대한 해시 함수

비록 djb2로, cnicutar에 의해 유래에 관한 더 나은 거의 확실하다, 나는 보여주는 그것의 가치가 생각 K & R이 너무 해시 :

1) 분명히 끔찍한 해시 알고리즘, K & R 1 판 ( 출처 )

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

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

    return hash;
}

2) 아마도 K & R 버전 2에 제시된 꽤 괜찮은 해시 알고리즘 일 것이다 (책의 144 페이지에서 내가 확인 함); 주의 : % HASHSIZE해시 알고리즘 외부에서 배열 길이에 맞게 모듈러스 크기 조정을 수행 할 계획이라면 return 문에서 제거해야 합니다. 또한 unsigned long단순 unsigned(int) 대신 return 및 “hashval”유형을 사용 하는 것이 좋습니다 .

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 판 해시.

unordered_map(해시 테이블 템플릿) 및 unordered_set(해시 세트 템플릿)에 사용되는 GCC C ++ 11 해싱 함수 는 다음과 같습니다.

• 이것은 GCC 가 Austin Appleby ( http://murmurhash.googlepages.com/ ) 의 “MurmurHashUnaligned2″구현을 사용함을 나타내는 GCC C ++ 11 해시 함수 가 무엇인지 에 대한 질문에 대한 부분적인 답변 입니다.
• “gcc / libstdc ++-v3 / libsupc ++ / hash_bytes.cc”파일 ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.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;
}

---