均匀分布的散列函数

我需要一个散列函数，它需要一些（如2或3）无符号整数作为输入，并返回-1和+1之间的浮点值。均匀分布的散列函数

这些返回值的集合必须均匀分布。即使输入数字是连续的，函数输出序列也必须是随机序列。也越快越好，我称它为很多次。

我希望这不是过分的要求：S ...

2010-09-28 Hannesh

您可以使用标准的方案，这样的任务：(a0 + Q*a1 + Q^2*a2 + Q^3*a3 + ...) % M其中M是一个非常大的素数，Q是您的首选系数。
一旦您在范围[0, M)中有足够的随机散列，将其转换为浮点数[-1, 1]就很简单。

或者你可以删除% M并允许发生整数溢出，虽然我不知道它有多安全（从“均匀分布”的角度来看）。

即使输入数字是连续的，函数中的输出序列也必须是随机序列。
为此，您可以使用ai*ai来代替ai。无论如何，这是Java中的简单实现。

double hash(int... a) { 
    int Q = 433494437; 
    int result = 0; 
    for (int n : a) { 
     result = result * Q + n * n; 
    } 
    result *= Q; 
    return (double) result/Integer.MIN_VALUE; 
}

即使连续数字，输出看起来也是随机的。您也可以使用64位整数来获得更高的精度。

来源

2010-09-28 20:29:05

这很好用，它比我想象的要简单得多！谢谢一堆。 – Hannesh 2010-09-29 16:30:18

@Nikita Rybak：由于平方会造成碰撞。实际上，每个哈希都会创建它们，但在这里您可以轻松获得它们。对于1元组序列'（-1），（0），（1）'，结果确实不是随机的。开动3或者像'（n + 12345）* n'这样的东西可以做得更好。 – maaartinus 2012-09-28 17:14:01

Murmurhash是一个非常好的（强）和快速哈希函数，它已经对它进行了一些严重的测试。

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

虽然它不是专门为整数本身，它可以快速调整，这样做。我有，如果你的话是不是sequently在内存布局可能对您更方便的这样的替代配方：

 
#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位版本。将整数转换为范围内的浮点值作为读者的练习（分区）。

来源

2010-09-29 04:46:41

均匀分布的散列函数

回答

相关问题