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