改善散列函數值的分佈

Question

假設我有大量的字符串（比如每個約50個字符的100億個字符串）。我想將這些字符串分配到10個桶中。每個桶應該佔據約10％的字符串。使用散列函數h（）我可以這樣做：

int bucket_for_s = h(s) % 10 

但是，這並不能保證分配的均勻性。假設我爲所有字符串做了上述操作，並發現30％轉到1號桶，5％轉到2號桶，等等。我的問題是：

給定h（）分佈，有沒有辦法生成一個新的散列函數h2（），它將更均勻地分配字符串？

另外，是否有一個過程，可以生成一系列的哈希函數h2（），h3（）...所以1：每個哈希函數都比前一個和2更好：我只需要生成一個合理數量的散列函數？

我還應該提到，不幸的是，我不能簡單地將輸入分成10個部分，因爲我的輸入分佈在多臺機器上。我正在尋找一種確定性的解決方案，我可以單獨應用到每臺機器上並獲得相同的結果（因此最終「hello」會轉到桶x，無論它存儲在哪臺機器上）。

Answer 1

加密實體散列函數在散列輸出的所有位上應該已經具有非常均勻的分佈。

如果你正在使用類似Java的hashCode()我相信貌似

S [0] * 31 ^（N-1）+ S 1 * 31 ^（N-2）+ ... + s [n-1]

你可能會看到一個不太理想的散列分佈。

嘗試使用加密散列（如SHA-256）作爲基礎。

Google的City Hash分佈不如SHA-256，但速度要快得多。這可以以較少的計算成本提供足夠的分配。

Answer 2

如何解決A方向它簡化爲2桶，而不是10或N.

假設你獲得與分配p剷鬥1和q剷鬥2，當然p + q = 1的分佈h()。

現在，我們的目標是要找到這樣的分佈h2()與參數p1, q1, p2, q2說： 給出桶1，它使用的機會p1, q1 (p1+q1=1)並給予鬥2，它使用的機會p2, q2 (p2+q2=1)：

  h()   h2() 

       /bucket1 p*p1 
     bucket1 p - 
    /   \ bucket2 p*q1 
x - 
    \   /bucket1 q*p2 
     bucket2 q - 
       \ bucket2 q*q2 

，我們的目標是，即使機會所有的2桶：

p*q1 + q*p2 = 1/2 (total chances for bucket 1 after h2()) 
p*q2 + q*q2 = 1/2 (total chances for bucket 2 after h2()) 

和以前一樣：

p1 + q1 = 1 
p2 + q2 = 1 

這是具有4個變量的4個方程的線性系統（參數p1,q1,p2,q2分佈h2()）。

注意：有10個桶，我們會有h()和p1, p2, ..., p10，其中p1 + p2 + ... + p10 = 1。如果桶的數量大於2，則方程式數量少於未知數量：對於像p1這樣的每個分配，您將獲得h2()的組成部分p11+p12+...+p1_10=1）。因此，對於10個桶，存在100個未知參數h2()和僅20個方程。這意味着在求解剩餘參數的方程式之前，可以對80個參數h2()給出一些任意（但可行）的值。不漂亮，但仍是一個解決方案。

Answer 3

鏈接哈希函數或生成一系列哈希函數將是非常計算昂貴的。您應該使用已經具有所需屬性的散列函數。

可能的候選人

從你所描述的，哈希函數應該是確定的（你的「你好」的例子） - 這是所有散列函數真 - 也應該產生均勻分佈。

加密散列如SHA-256應該符合您的要求，因爲即使只是稍微不同的輸入（如「hello」和「hallo」），它也會輸出完全不同的散列。通過對哈希使用模（％）操作，您可以隨意使用盡可能多的桶（當然，不會超過哈希的數量）。

但是，密碼散列函數是爲了安全性和校驗和而構建的，涉及一些複雜的計算。就你而言，你很可能不需要他們提供的強大的安全相關屬性。

您可能更想查找所謂的「非加密散列函數」，它具有寬鬆的屬性並且更適合查找 - 所以它們針對速度進行了優化。 Java的hashCode(),MurmurHash和已經提到的CityHash（Google announcement）可能是一個好的開始。

的散列函數對散列甚至

也就是說分佈確定性性質，散列函數是確定性的關於輸入，某個輸入爲「你好」散列將始終是相同的，甚至如果你多次調用散列函數。如果您的數據集包含一些含有大量精確重複項的元素（例如，「a」和「the」是標記文本的常見嫌疑犯），則無論您使用哪種散列函數，都可能容易導致大小不一的小桶。

假設您想要使用哈希的均勻分佈來均勻分配工作負載，可以使用以下策略來克服此問題。將每個桶視爲可由任何可用機器處理的工作包或作業。如果你有比機器更多的工作包（比方說10臺機器有20或30個包），只要你允許靈活的調度，你可以平均分配工作量。當機器A得到一個超大包裝並需要一些時間來處理時，機器B可以同時處理兩個中小包裝，從而減小了超大包裝對整體性能的影響。

Answer 4

散列函數旨在產生均勻分佈。如果數據不是這種情況，那麼您的數據在某種程度上與特定散列函數「部分」相反，當您選擇另一個數據時問題應該消失。

鑑於這是一個理論問題，一個辦法是：

美白有色噪聲

您可以用int bucket_for_s

int bucket_for_s = put_in_bucket(s) 

put_in_bucket: 
    x = h(s) % 10 + 10*((h(s)/10)%10) 
    if(0<=x<=2) return 0 
    if(3<=x<=5) return 1 
    if(6<=x<=9) return 2 
    #The previous bucket_1 (30%) is now split into 3 buckets 
    if(10<=x<=27) return 0 
    #The previous bucket_2 (5%) is now enlarged 
    #to incorporate more of the small old buckets (or parts of buckets) 
    #This bucket is now bucket_4 
    #... more of the same 
    if(83<=x<=99) return 9 

播放，您可以通過另一個數字，直到你擴展這個想法對您的「分辨率」感到滿意

您可以從put_in_bucket中取出邏輯並將其放入h2(s)使用h1(s)。

該方法用於對白色噪聲（或在此情況下增白有色噪聲）進行着色，因此稱爲名稱。