algorithm - 均匀分布哈希函数

Question

我需要一个哈希函数，它接受一些(例如 2 或 3 个)无符号整数作为输入，并返回一个介于 -1 和 +1 之间的浮点值。

这些返回值的集合必须均匀分布。函数的一系列输出必须看起来是随机序列，即使输入数字是连续的。而且越快越好，我经常调用它。

我希望这个问题不会太过分:S...

Answer 1

Murmurhash 是一个非常好(强)且快速的哈希函数，已经对其进行了一些严格的测试。

http://sites.google.com/site/murmurhash/

虽然它本身并不专用于整数，但可以快速调整它。如果您的单词没有按顺序排列在内存中，我有这样一个替代公式可能对您更方便:

#define MURMURHASH2A_R 24#define MURMURHASH2A_MULTIPLIER 0x5bd1e995#define MURMURHASH2A_SEED 2166136261U  // No seed suggested, so using FNV32_OFFSET_BASIS#define murmurhash2a_init(h) do { h = MURMURHASH2A_SEED; } while (0)#define murmurhash2a_update(h,word)                     \do {                                                    \  u_int mmh2ak = (word) * MURMURHASH2A_MULTIPLIER;      \  mmh2ak ^= mmh2ak >> MURMURHASH2A_R;                   \  mmh2ak *= MURMURHASH2A_MULTIPLIER;                    \  h *= MURMURHASH2A_MULTIPLIER;                         \  h ^= mmh2ak;                                          \ } while (0)#define murmurhash2a_final(h)                   \do {                                            \  h ^= h >> 13;                                 \  h *= MURMURHASH2A_MULTIPLIER;                 \  h ^= h >> 15;                                 \ } while (0)u_int hash;murmurhash2a_init(hash);murmurhash2a_update(hash,firstint);murmurhash2a_update(hash,secondint);[...]murmurhash2a_final(hash);

显然这是返回 0-2^32-1。 murmurhash 站点上有 64 位版本。将整数转换为范围内的 float 作为练习(除法)留给读者。