哈希函數的隨機性，如SHA1

我試圖根據用戶ID生成一個隨機數的均勻分佈。也就是說，我希望每個用戶的隨機數在用戶請求隨機數的任何時間保持不變（但用戶不需要存儲該數字）。我現在的算法（在PHP）來算的分佈，對於給定的大陣用戶ID $arr的是：哈希函數的隨機性，如SHA1

$range = 100; 
$results = array_fill(0, $range, 0); 

foreach ($arr as $userID) { 
    $hash = sha1($userID,TRUE); 
    $data = unpack('L*', $hash); 
    $seed = 0; 
    foreach ($data as $integer) { 
     $seed ^= $integer; 
    } 
    srand($seed); 
    ++$results[rand(0, $range-1)]; 
}

人們希望這會產生一個近似均勻分佈。但它不！我已經檢查過，以確保$arr中的每個值都是唯一的，但列表中的一個條目總是比其他條目中的條目多得多。有沒有更好的方法來生成一個字符串的散列，它會給出一個近似均勻的分佈？顯然，SHA不能勝任這項工作。我也嘗試過MD5和簡單的crc32，所有的結果都一樣！？

我瘋了嗎？事實上，我唯一的解釋是否證實$arr中的每個條目都是唯一的？

來源

2012-08-01 Ed Marty

我不確定你要求什麼。你想爲每個用戶提供一個唯一的隨機數字嗎？爲什麼不'sha1（$ userId。$ salt）'？ – 2012-08-01 23:09:51

有一些缺失。我無法運行此代碼，看看「一個條目獲得更多的活動」是什麼意思。你還應該注意到SHA-1並不是隨機設計的，它被設計成僞隨機的，其碰撞率低於2^160的組合。我想我在某處讀到，PHP中的隨機生成器在隨後的每次調用中都會變得更「隨機」，因此在播種之後直接調用它可能不夠。與mt_rand一起去看看是否有所作爲。 – Leigh 2012-08-01 23:15:57

我不明白爲什麼你會期望隨機任何東西均勻分佈，即使設置種子。即使使用數字1-100作爲種子的for循環也不是均勻分佈的。 http://codepad.viper-7.com/LxeHhu 3個號碼出現3次，而31/100號碼出現0次。 – 2012-08-01 23:35:20

mt_rand()在所請求的範圍內應該具有非常均勻的分佈。創建用戶時，爲該用戶創建一個隨機種子，然後使用mt_rand()，然後始終使用該種子的mt_srand()。

要獲得從0到99的均勻分佈，以您的示例爲例，只需mt_rand(0,$range-1)。使用sha1，md5或其他一些散列算法做技巧不會比直接隨機給出更均勻的分佈。

來源

2012-08-01 23:39:01 MightyE

我有點困惑的要求的原因是我不存儲用戶ID。用戶只需將其ID發送到服務器，並且服務器必須始終爲該用戶返回相同的值，並且在所有用戶ID上的分佈均勻。因此，存儲任何用戶數據都不在該函數的範圍之內。 – 2012-08-01 23:45:53

所以基本上用戶給你發送種子值，對吧？如果你將它們的輸入傳遞給'mt_srand（）'，'mt_rand（）'函數將始終爲該用戶返回相同的數字。 – dimo414 2012-08-02 00:22:26

我會接受你的答案，因爲mt_rand的使用可能是一個好主意，但如果我的數據實際上是獨特的（我顯然沒有擺脫重複），我的原始算法會起作用。 – 2012-08-02 14:19:26

sha1哈希數是相當均勻分佈的。執行此操作後：

<?php 

$n = ''; 
$salt = 'this is the salt'; 

for ($i=0; $i<100000; $i++) { 
    $n .= implode('', unpack('L*', sha1($i . $salt))); 
} 

$count = count_chars($n, 1); 
$sum = array_sum($count); 

foreach ($count as $k => $v) { 
    echo chr($k)." => ".($v/$sum)."\n"; 
} 

?>

您會得到此結果。每個數字的概率：

0 => 0.083696057956298 
1 => 0.12138983759522 
2 => 0.094558704004335 
3 => 0.07301783188663 
4 => 0.092124978934097 
5 => 0.088623772577848 
6 => 0.11390989553446 
7 => 0.092570936094051 
8 => 0.12348330833868 
9 => 0.11662467707838

您可以使用sha1作爲基於用戶ID的簡單隨機數生成器。

在十六進制，分佈接近完美：

// $n .= sha1($i . $salt, false); 

0 => 0.06245515 
1 => 0.06245665 
2 => 0.06258855 
3 => 0.0624244 
4 => 0.06247255 
5 => 0.0625422 
6 => 0.0625246 
7 => 0.0624716 
8 => 0.06257355 
9 => 0.0625005 
a => 0.0625068 
b => 0.0625086 
c => 0.0624463 
d => 0.06250535 
e => 0.06250895 
f => 0.06251425

來源

2012-08-01 23:52:10

@Marty。對。你不應該使用sha1結果作爲mt_rand的種子。 Sha1本身就是一個很好的散列。 – iWantSimpleLife 2012-08-02 00:57:29

這將是有益的，如果你發佈你的結果，導致你的結論是你沒有得到適當的分配，但很可能的一個有三件事情發生在這裏：

你只是看着樣本太小，或者你錯過了解釋你的數據。正如其他人所評論的那樣，對於均勻分佈來說，沒有完全統一的輸出是完全合理的。
如果您使用mt_rand而不是rand，您會看到更好的結果。（我個人認爲這很有可能）你過度優化你的種子世代，並且失去數據/鴿子洞/否則會傷害你產生隨機數的能力。讀你的代碼，我認爲你做了以下內容：
1. 生成未知值
2. 拆分散列成多頭和位的均勻隨機哈希異或在一起
3. 設置rand的種子，併產生一個隨機數字種子
但你爲什麼要做第2步？你認爲你從中得到什麼好處？嘗試採取這一措施，只需使用從散列中提取的第一個值作爲種子，並查看這是否不會帶來更好的結果。隨機性經驗很好的規則 - 不要試圖智取誰實現的算法的人來說，它不能做:)

來源

2012-08-02 00:38:32 dimo414

至於樣本量，我希望300,000個唯一值應該足夠大。你基本上是正確的什麼即時通訊嘗試做。我從用戶那裏得到的原始值是一個很長的字符串，不能用來播放rng。所以我的第一步是將其轉換爲原始sha哈希。但是，這是一個長度爲20個字節的原始二進制字符串，仍然不能用作種子，所以我需要步驟2將其轉換爲整數。除非有更好的方法？ – 2012-08-02 11:55:22

只需將前面的字節作爲你的種子（或者甚至直接用它作爲你的唯一值），這就是很多隨機性，不需要嘗試將這些比特合併在一起。 – dimo414 2012-08-02 16:53:01

雖然這裏所有的答案都不錯，我會提供答案那對我來說是正確的，那就是我確實是瘋了。顯然，uniq命令實際上不像我預期的那樣工作（數據需要先排序）。所以解釋的確是$arr中的值不是唯一的。

來源

2012-08-02 14:16:04

哈希函數的隨機性，如SHA1

回答

相關問題