Re: [資料] string hash functions performance

看板CSSE (電腦科學及軟體工程)作者reader (讀者)時間16年前 (2008/12/14 20:51)推噓2(2推 0噓 4→)

留言6則, 3人參與討論串2/3 (看更多)

※ 引述《reader (讀者)》之銘言： : 既然講到了演算法的實證資料，就想起這一篇文章： : http://www.fantasy-coders.de/projects/gh/html/x435.html : 算是很不錯的 string hash function performance 資料，不過是 : 德文的，幸好圖表很多，看圖大概也能看懂，也有列出程式碼。 : 我以前是用 DJB2, 一直很煩惱要不要用 FNV, 但看過這一篇之後， : 就決定改用 FNV 了。 : string hash function 在有大量會員，需要高效率的登入功能的 : 高負載網路服務，就顯得十分重要了。現在有新的實證研究了: http://smallcode.weblogs.us/2008/01/22/hash-functions-an-empirical-comparison/ http://smallcode.weblogs.us/2008/02/04/hash-functions-additional-tests/ http://smallcode.weblogs.us/2008/02/12/hash-functions-part-3/ http://smallcode.weblogs.us/2008/06/17/murmur-hash/ 而我自己根據這幾篇研究，試做了一個 x273 的方法: UINT Hash273(const CHAR *key, SIZE_T len) { UINT hash = 0; UINT i = 0; UINT n = (UINT)len & -4; UINT e = (UINT)len - n; for(; i < n; i += 4) { hash = 273 * hash + key[i + 0]; hash = 273 * hash + key[i + 1]; hash = 273 * hash + key[i + 2]; hash = 273 * hash + key[i + 3]; } if(e == 0) return hash; hash = 273 * hash + key[i + 0]; if(e == 1) return hash; hash = 273 * hash + key[i + 1]; if(e == 2) return hash; hash = 273 * hash + key[i + 2]; return hash; } (以上程式風格是為了嵌入這一系列文章的程式碼而寫成這樣的。已做了速度最佳化處理。) 結果是: Words Win32 Numbers Prefix Postfix Variables Shakespeare Bernstein 146 879 426 326 315 651 875 K&R 143 890 867 329 320 657 886 x17 137 848 81 317 299 639 831 x17 unrolled 132 826 84 307 292 622 806 x65599 139 846 207 320 317 639 836 FNV-1a 151 961 88 368 357 693 907 universal 155 981 91 376 366 705 923 Weinberger 168 1205 272 483 472 831 1068 Paul Hsieh 156 840 110 292 275 660 951 One At Time 161 1024 103 393 377 741 961 lookup3 153 846 92 290 278 665 948 Arash Partow 152 978 1046 384 362 717 928 CRC-32 158 1010 79 386 366 719 950 Ramakrishna 152 955 211 370 351 704 925 Fletcher 139 677 1178 261 229 593 1254 Murmur2 135 771 85 265 251 607 831 x273 129 748 70 248 243 591 802 (Adler-32 的結果太糟糕，我直接砍了) 好像就這樣不小心被我弄出了一個在這一張表中，看起來是效率第一名的新字串雜湊函數 XD 所以在這邊推薦使用的公式是: hash(n+1) = hash(n) * 273 + char(n) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 82.103.134.5 ※ 編輯: reader 來自: 82.103.134.5 (12/14 21:06)