如何將哈希統一投影到固定數量的桶中

各位統計學家，您好，

我有一個生成散列的源（例如，計算帶有時間戳和其他信息的字符串並使用 md5 散列），我想將它投影到固定數量的桶中（比如 100）。

樣本哈希：0fb916f0b174c66fd35ef078d861a367

我最初的想法是只使用哈希的第一個字符來選擇一個桶，但這會導致投影非常不均勻（即一些字母很少出現，而另一些則非常頻繁）

然後，我嘗試使用 char 值的總和將此六進製字符串轉換為整數，然後取模來選擇一個存儲桶：

import sys

for line in sys.stdin:
   i = 0
   for c in line:
       i += ord(c)
   print i%100

它似乎在實踐中有效，但我不知道是否有任何常識或理論結果可以解釋為什麼以及在多大程度上這是正確的？

[編輯] 經過一番思考，我得出以下結論：理論上，您可以通過將散列解釋為數字來將散列轉換為（非常大的）整數： i = h[0] + 16h[1]+16 16h[2] … + 16^31h[31] （每個字母代表一個十六進制數）。然後你可以對這個大數字取模以將其投影到存儲桶空間。[/編輯]

謝謝 ！

注意：將討論中出現的答案放在評論中，以便感興趣的人更容易閱讀

（更新後的版本）

假設我們有一個生成獨立事件的源，我們希望將這些事件均勻分佈到桶。

關鍵步驟是：

1. 散列每個事件為整數大小的
2. 投影到作為
3. 找到匹配的桶以便

對於 1. 一個流行的解決方案是使用MurmurHash生成一個 64 位或 128 位整數。

對於 3. 一個簡單的解決方案是迭代並檢查在

在（python）偽代碼中，整個過程可能是：

def hash_to_bucket(e, B):
   i = murmurhash3.to_long128(str(e))
   p = i / float(2**128)
   for j in range(0, B):
       if j/float(B) <= p and (j+1)/float(B) > p:
           return j+1
   return B

---

（以前的版本，真的不是最優的）

第一個觀察是哈希的第n個字母應該相對於字母表均勻分佈（這裡是 16 個字母長 - 感謝@leonbloy 指出）。

然後，要將其投影到 [0,100[ 範圍，訣竅是從散列中獲取 2 個字母（例如，第 1 和第 2 位置）並生成一個整數：

int_value = int(hash[0])+16*int(hash[1])

該值位於 [0,16+(16-1)16[ 範圍內，因此我們只需將其取模*為 100 即可生成 [0, 100[ 範圍內的存儲桶：

正如評論中指出的那樣，做所以影響分佈的均勻性，因為第一個字母比第二個字母更有影響力。

bucket = int_value % 100

理論上，您可以將整個哈希轉換為（非常大的）整數，方法是將其解釋為數字： i = h[0] + 16h[1]+1616h[2] … + 16^ 31h[31]（每個字母代表一個十六進制數）。然後你可以對這個大數字取模以將其投影到存儲桶空間。然後可以注意到，取 i 的模可以分解為分配和加法運算：

引用自：https://stats.stackexchange.com/questions/26344