|
Google 發(fā)布了 CityHash 系列字符串散列算法。今天發(fā)布的有兩種算法：CityHash64 與 CityHash128。它們分別根據(jù)字串計算 64 和 128 位的散列值。這些算法不適用于加密，但適合用在散列表等處。Google 一直在根據(jù)其數(shù)據(jù)中心常用的 CPU 對算法進行優(yōu)化，結(jié)果發(fā)現(xiàn)對大多數(shù)個人計算機與筆記本同樣有效益。尤其是在 64 位寄存器、指令集級的并行，以及快速非對其內(nèi)存存取方面。 該算法的開發(fā)受到了前人在散列算法方面的巨大啟發(fā)，尤其是 Austin Appleby 的 MurmurHash。但 CityHash 的主要優(yōu)點是大部分步驟包含了至少兩步獨立的數(shù)學(xué)運算。現(xiàn)代 CPU 通常能從這種代碼獲得最佳性能。 但 CityHash 也有其缺點：代碼較同類流行算法復(fù)雜。Google 希望為速度而不是為了簡單而優(yōu)化，因此沒有照顧較短輸入的特例。 總體而言，CityHash64 與 CityHash128 是解決經(jīng)典問題的全新算法。在實際應(yīng)用中，Google 預(yù)計 CityHash64 在速度方面至少能提高 30%，并有望提高多達兩倍。此外，這些算法的統(tǒng)計特性也很完備。 via Google Open Source Blog |
