您使用什么哈希函数 "hacks"？

Question

哈希函数可以依赖于数据。例如（来自 this 文章）如果您的数据都是字符串，并且几乎所有字符串的长度都不同，那么简单的字符串长度可能是一个非常好的哈希函数（我知道这不是很现实）。或者例如从 0 到 1 的实数可以有一个简单的哈希函数：

value * sizeOfHashTable

如果您使用针对您的输入量身定制的散列函数，我很感兴趣？还有更多例子吗？

Answer 1

正如您正确指出的那样，散列函数取决于散列数据。设计一个好的散列函数的共同想法——满足3个条件：

函数必须易于计算。也许，最好使用不太好的散列，但要快速计算它，并在散列上节省更多时间，而不是在不平衡的桶或 table 路径上丢失。
函数在测试数据集上必须具有良好的分布（伪随机）。好主意 - 在散列函数 "snow-crash effect" 中使用，当更改输入数据中的一位时，输出值中的 ~half 位会发生变化。
对于外部输入的数据，哈希函数必须是"universal"，即抵抗尝试产生碰撞。

我最喜欢的散列函数如下。在第一次使用之前，需要用一些随机值初始化 table S_block。在每个程序中都这样做是个好主意运行.

const unsigned int S_block[256] = { ... };
#define NLF(h, c) (S_block[(unsigned char)(c + h)] ^ c)

unsigned int hash(const char *key) {
unsigned int h = 0x1F351F35;
char c;
while(c = *key++)
  h = ((h << 7) | (h >> (32 - 7))) + NLF(h, c);
h ^= h >> 16;
return h ^ (h >> 8);
}

作为实际示例，请参阅在我的程序 emcSSH. The file htable.c contains variation of this function, suitable for the double hashing 算法中使用此函数的变体。

您使用什么哈希函数 "hacks"？

What hash function "hacks" do you use?

hash

hashtable

hashmap

hashcode

data-structures