轉換DJB哈希到64位

將丹伯恩斯坦的散列函數仍正常工作，如果我使用的是64位無符號整數？轉換DJB哈希到64位

uint64 
hash_djb2(register uchar *str, register size_t length) { 
    register uint64 hash = 5381L; 
    while (length--) { 
     hash = ((hash << 5L) + hash) + *str++; /* hash * 33 + c */ 
    } 
    return hash; 
}

來源

2011-12-01 Ian

我不知道所有2^64可能值的分佈是否與32位版本相同，但一個重要屬性仍然成立。乘數33不與2^64共享任何公約數。因此，所有通過散列運行的角色仍會對最終結果產生影響。換句話說，這兩個字符串的散列結果將會不同：

hash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") => 0x87b2af4e3d92de7a 
hash("baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") => 0xd496edbee1219cfb

它應該仍然是一個有用的散列函數。當然，我不禁想知道爲什麼你需要這麼大的散列值。一個非常大的哈希表？或者其他一些用途？

來源

2011-12-01 00:32:05

我正在製作一個哈希表，可以運行超過40億行（不太可能，但一種可能性）..另外，碰撞的可能性較低很好... – Ian

@伊恩：謝謝你滿足我的好奇心。這聽起來像你會推動一些界限;那些可以是很好的類型的項目。 –

的DJB散列函數是基於一個Linear Congruential Generator，其具有形如x =（A·X + C）模m。

通過檢查的功能，我們意識到a = 33，c = input在DJB的情況，但因爲它是由可變哈希，在它的原始形式無符號長類型規定的模有點隱蔽，其中包含32位數據。當該值超出無符號長整型的值時，它將溢出並繼續，從而得到2^32的模。

根據Knuth在他的計算機程序設計藝術第2卷：第3.2.1章中的數值算法，m必須被（a-1）的所有素數因子整除，以使線性同餘發生器具有最大週期（週期=模）（以及伯恩斯坦先生已經考慮到的其他事實）。由於具有m = 2^64沒有引入新的主要因素，因爲根據定義2既2^32和2^64的素數，該規則得到滿足。

你會那麼，這個新的哈希算法，能只要得到一個週期爲您模，這意味着你將包括一個64位整數的所有可能的值。

請記住，雖然，改變算法的任何數學值不能輕易完成。完全理解新算法的缺陷和好處需要進行全新的統計分析，即使您只更改了它的一個變量。你不能簡單地改變數值，並希望得到與原始線性同餘發生器相同的特徵。諸如熵和碰撞之類的統計特徵將不會從前一種算法中保留。然後，您不能聲稱已經實施了DJB的算法，無論是引用DJB的任何統計的表現證明了你的具體實現。

來源

2012-02-03 16:39:31 Soravux

轉換DJB哈希到64位

回答

相關問題