Хотя djb2, поскольку , представленный на стеке потока cnicutar , почти наверняка лучше, я думаю, что стоит показать и хеши K & R :
1) По-видимому, ужасный алгоритм хеширования, представленный в 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) Вероятно, довольно приличный алгоритм хеширования, представленный в K & R версии 2 (проверено мной на стр. 144 книги); NB: обязательно удалите % HASHSIZE из оператора return, если вы планируете использовать модуль sizing-to-your-array-length вне алгоритма хеширования. Кроме того, я рекомендую вам сделать возврат и тип "hashval" unsigned long вместо простого unsigned (int).
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31*hashval;
return hashval % HASHSIZE;
}
Обратите внимание, что из двух алгоритмов ясно, что одна из причин, по которой хэш 1-го издания настолько ужасен, состоит в том, что он НЕ учитывает строковый символ order , поэтому hash("ab") будет возвращать то же значение, что и hash("ba"). Это , а не , поэтому с хэшем 2-го издания, однако, который (намного лучше!) Вернет два разных значения для этих строк.
Функции хэширования GCC C ++ 11, используемые для unordered_map (шаблон хеш-таблицы) и unordered_set (шаблон хэш-набора) следующим образом.
Код:
// 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;
}