字元串hash函數的本質
前言
以前在《memcached 源碼閱讀之 字元串 hash 與 蒐集的一些 字元串 hash》中已經記錄了一些hash函數.
現在看其本質演算法.本質
如果對演算法不感興趣的人, 只需要看看這個小節就行了, 下面小節的都是經典書籍與人物的演算法,都是本質演算法穿上了一個馬甲.
hash函數的本質是掃描字元串過程中, 根據之前的結果, 當前位置,當前字元的值使用一個公式計算出當前結果. 當然稍微複雜的hash演算法會考慮之前所有的的結果,位置以及字元, 甚至會迭代多次.這篇文章提到了一些書籍, 系統和一些人, 如果想要任何書籍的人都可以加公眾號要相關書籍.
核心代碼如下:
BKDR Hash
在Brian Kernighan與Dennis Ritchie的《The C Programming Language》一書被展示而得名,是一種簡單快捷的hash演算法,也是Java目前採用的字元串的Hash演算法。
有人說將乘法分解為位運算及加減法可以提高效率.
但其實在Intel平臺上,CPU內部對二者的處理效率都是差不多的;在ARM這類RISC系統上由於ARM內部使用Booth』s Algorithm來模擬32位整數乘法運算,它的效率與乘數有關.
SDBM Hash
在開源項目SDBM(一種簡單的資料庫引擎)中被應用而得名,它與BKDRHash思想一致,只是種子不同而已。
RS Hash
因Robert Sedgwicks在其《Algorithms in C》一書中展示而得名。
AP Hash
由Arash Partow發明的一種hash演算法。
JS Hash
由Justin Sobel編的一種hash演算法。
DEK hash
本演算法是由於Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。
FNV Hash
Unix system系統中使用的一種著名hash演算法,後來微軟也在其hash_map中實現。
DJB Hash
由Daniel J. Bernstein教授編的一種hash演算法。
PJW Hash
本演算法是基於AT&T貝爾實驗室的Peter J. Weinberger的論文而發明的一種hash演算法。
CRC32 hash
這個就不需要介紹了.
參考資料
General Purpose Hash Function Algorithms
其他文章
UNION架構篇UNION優化篇UNION誕生篇union運營篇談談cache浪潮之巔排名演算法
關於作者
曾是一名ACMer, 現在是鵝長視頻部門的後臺開發
這裡主要記錄工作中的技術架構與經驗,計算機相關的技術,數學、演算法、生活上好玩的東西
長按二維碼關注作者, 瞭解作者發布的最新好玩的東西
aHR0cDovL3dlaXhpbi5xcS5jb20vci82RG1CbVZmRWFBb1hyUlA2OTJ6Ng== (二維碼自動識別)
推薦閱讀: