絃樂 - 優文庫

哈希函數我需要一個散列函數（字節），其絃樂

具有較低的碰撞率（即使是很短的字符串）的字符串
可以快速計算（O(n)時間是必須的，但我希望它儘可能快）
鑑於hash(string1)和hash(string2)，計算hash(append(string1, string2)) 可以O(1)完成。

我能想出迄今最好的是這樣的：（在Java中的僞代碼）

public static int[] HASH_ENTROPY = new int[] {...} // 255 large prime numbers 

public int hash() 
    int hash = 0; 
    for (int i=0; i < this.array.length; i++) 
     hash += HASH_ENTROPY[this.array[i] + 128]; 
    return hash;

是否有更好的算法？這一個執行＃1和＃3，但我想知道如果它太慢必須訪問數組中的隨機元素。

來源

2013-12-08 nikdeapen

這與RSA和其他類似的方法並不是不一樣的，而不是隻是'大'的素數，你可以使用與許多事情相關的質數（即3,17等）。我知道Ramanujan也出現了有一個非常好的散列數（不能想象它離開我的頭頂）。 –

該算法是順序無關的，這意味着anagrams會發生碰撞;這似乎與慾望＃1相矛盾，儘管通過依賴訂單的散列算法使＃3變得如此之快是非常棘手的。我真的不認爲查詢熵值的速度很重要，但另一方面，自那以後，它們也沒有太大的幫助。 – rici

@nikdeapen爲什麼你使用哈希（安全或查找）的目的？什麼是所需的哈希鍵長度？ –

我建議你使用：

public uint32_t hash() 
    uint32_t hash = 0x1f351f35; // 2x Barker code 
    for (int i=0; i < this.array.length; i++) { 
     char c = this.array[i]; 
     hash = ((hash << 1) | (hash >> 31)) + (HASH_ENTROPY[(uint8_t)(hash + c)]^c); 
    } 
    return hash;

來源

2013-12-08 05:38:39 maxihatop

這很好用，但比我給出的慢了4-5倍。使用此功能是否有任何實質性好處？ – nikdeapen

好處 - 抵抗anagrams散列（「ab」）！=散列（「ba」）;雪崩效應，當輸入數據中的1位變化時，輸出變化〜50％位。 – maxihatop

你會怎麼做：*給定'hash（string1）'和'hash（string2）'，計算'hash（append（string1，string2））'可以在O（1）。*？ –

另外，如果你需要快速計算時間，你可以考慮另一種散列函數：

public uint32_t hash() 
    uint32_t hash = 0x1f351f35; // 2x Barker code 
    for (int i=0; i < this.array.length; i++) { 
     hash += (hash << 4) + this.array[i]; 
    } 
    return hash;

重要：前散列函數使用熵陣列;你可以在每個程序開始時用隨機值填充這個數組，所以當外面的某個人特別用相同的散列生成很多字符串時，會產生通用的散列，抵抗外部攻擊，從而產生服務的衝突和DOS。此功能很快，但不能抵禦邪惡攻擊。

來源

2013-12-09 16:00:28 maxihatop

絃樂

回答

相關問題