3散列函數最佳散列最小衝突的布隆過濾器的滑動窗口字符串

Question

我需要3個散列函數來將滑動窗口的字符串散列在文本上移動，稍後將用於在盛開矢量中進行搜索。我在編程中使用C＃

我讀了一些關於滾動散列函數和循環多項式的內容，它們用於滑動窗口應用程序。但真的，我沒有找到任何代碼，他們只是描述

所以，請任何人有任何關於3最好的C＃哈希函數使用滑動窗口字符串固定大小（5個字符），消耗少時間和最小數量的碰撞，要麼他們滾動哈希函數或其他人，請幫我一些C＃代碼或哈希函數名稱的鏈接

字符串都是十六進制，我的意思是由（0-9）和（AF）大寫字母，用連字符沿（ - ）...例如

我的字符串可以是AB-2C-65-ED-65

Duaa

Answer 1

Alpha chars only？上部和下部？如果您只有5個不區分大小寫的[a-z]字符，您可以從26 < 2^5以非常快的速度將它們打包成5 * 5 = 25位。所以32位int可以用零散列衝突打包整個字符串。

[編輯]

OK，現在你已經澄清的輸入。

[0-9]，[A-Z] + [' - ']是37個字符......剛剛超過32個字符限制的5位。所以，你需要6位來存儲每個字符。幸運的是，即使使用5個字符，總共只有6*5 = 30位，因此您可以將整個字符串完全打包爲32位整數，甚至不需要擺弄符號位，因此您將擁有非常快速，完全無損（零碰撞）哈希代碼，唯一標識每個字符串......甚至可以顛倒！所有數字都是正數，所以如果需要的話，您可以爲符號位分配一些其他含義。

以下是將[0-9]，[a-z] + [' - ']範圍內的5個字符打包爲int的新函數。你首先需要取出Hex字符串並將其解除回到正常狀態，然後通過下面的旋轉位運行它。

string c; //This is your text to hash. 

public override int GetHashCode() 
{ 
    if (c.Length > 5) throw new InvalidOperationException("Sliding window string too long"); 

    const char dash = (char)45; 
    //Pack all characters right-aligned within the int 
    return (c[0]-dash << 24) | (c[1]-dash << 18) | (c[2]-dash << 12) | (c[3]-dash << 6) | c[4]-dash; 
} 

注意：您也可以安全地使用ASCII 45和ASCII 109之間等其他幾個大字：無需修改這個代碼「./:;<=>?[\]^_」。