均勻分佈的散列函數

我需要一個散列函數，它需要一些（如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

均勻分佈的散列函數

回答

相關問題