怎么樣的才算是好的哈希函數(shù)？
- 計算簡單，哈希函數(shù)的計算時間（指的是產生地址的時間），不應該超過其他查找技術與關鍵字比較的時間。
- 地址分布均勻，盡量讓哈希地址均勻分布在存儲空間中，這樣可以使空間有效的利用。
1.直接定址法
哈希地址：f(key) = a*key+b (a,b為常數(shù))
這種方法的優(yōu)點是：簡單，均勻，不會產生沖突。但是需要事先知道 key 的分布情況，適合查找表較小并且連續(xù)的情況。
2、數(shù)字分析法
比如我們的11位手機號碼“136xxxx5889”，其中前三位是接入號，一般對應不同運營公司的子品牌，如130是聯(lián)通如意 通，136是移動神州行等等。中間四位表示歸屬地。最后四位才是用戶號。
若我們現(xiàn)在要存儲某家公司員工登記表，如果用手機號碼作為 key，那么極有可能前7位都是相同的，所以我們選擇最后 四位作為 f(key) 就是不錯的選擇。
3、平方取中法
故名思義，比如 key 是1234，那么它的平方就是1522756，再抽取中間的3位就是227作為 f(key) 。
4、折疊法
折疊法是將 key 從左到右分割成位數(shù)相等的幾個部分(最后一部分位數(shù)不夠可以短些)，然后將這幾部分疊加求和，并按 哈希表的表長，取后幾位作為 f(key) 。
比如：我們的 key 是 9876543210，哈希表的表長為3位，我們將 key 分為4組，987|654|321|0 ，然后將它們疊加求和 987+654+321+0=1962，再取后3位即得到 f(key) = 962 。
5、除留余數(shù)法
哈希地址：f(key) = key % p (p<=m) m為哈希表表長。
這種方法是最常用的哈希函數(shù)構造方法。
事實上，如果p選得不好，就很容易出現(xiàn)同義沖突的情況：
如上圖所示，選擇p=11，就會出現(xiàn)key=12、144的沖突。
若哈希表表長為m，通常p為小于或者等于表長的最小質數(shù)或不包含小于20質因子的合數(shù)。
6、隨機數(shù)法
哈希地址：f(key) = random(key)
這里 random 是隨機函數(shù)，當 key 的長度不等時，采用這種方法比較合適。
