哈希表講解
摘要: 哈希表也稱(chēng)散列表,是一種數據結構,在JAVA集合中的HASHMAP,HASHTABLE都運用了哈希表.它可以提供快速的插入操作和查找操作,不論有多少數據項,插入與刪除只需要接近常量的時(shí)間:O(1)時(shí)間級.在計算機程序中,如果需要在一秒種內查...
哈希表也稱(chēng)散列表,是一種數據結構,在JAVA集合中的HASHMAP,HASHTABLE都運用了哈希表.
它可以提供快速的插入操作和查找操作,不論有多少數據項,插入與刪除只需要接近常量的時(shí)間:O(1)時(shí)間級.
在計算機程序中,如果需要在一秒種內查找上千條記錄,通常使用哈希表.
哈希表的速度明顯比樹(shù)快.樹(shù)的操作通常需要O(N)的時(shí)間級.哈希表不僅速度快,而且編程實(shí)現也相對容易.
但哈希表也有缺點(diǎn),它是基于數組的,數組一旦被創(chuàng )建,就難以擴展.某些哈希表被填滿(mǎn)時(shí),性能急劇下降.,所以程序員必須清楚表中要存儲多少數據.
哈希表操作的平均時(shí)間是基于統計特性而不是隨機輸入的期望值.
哈希表的重要特性就是哈希函數.
我們用一個(gè)將大數(或解釋為數的字符串)映射成一個(gè)較小的,更容易管理的數的函數來(lái)達到這個(gè)目的.
將一個(gè)項映射成一個(gè)較小的下標的函數稱(chēng)為哈希函數.
需要哈希函數,是因為哈希表是基于數組的,而且關(guān)鍵字值的范圍通常比數組容量大.,關(guān)鍵字值通過(guò)哈希函數映射為數組的下標.
在JAVA中,通過(guò)取模運算來(lái)實(shí)現.arrayIndex=hugeNumber %smallRange,這就是一個(gè)簡(jiǎn)單的哈希函數.
哈希函數簡(jiǎn)化了操作,但也帶來(lái)了不可避免的麻煩:兩個(gè)或更多的不同項可能被散列到同一個(gè)位置,引起沖突.
哈希函數不僅要容易計算,而且要對鍵值的分布要均勻.如果有太多的沖突,哈希表的性能將顯著(zhù)下降.
對于下面的哈希函數:
public static int hash(String key , int tableSize){
int hashVal = 0;
for(int i=0;i<key.length;i++){
hashVal+=key.charAt(i);
}
return hashVal%tableSize;
}
這個(gè)哈希函數很簡(jiǎn)單,很容易實(shí)現,計算哈希值也非?？?但這是個(gè)糟糕的哈希函數.
假設tableSize很大,為10000,再假設所有的關(guān)鍵字值的長(cháng)度都是8個(gè)或少于8個(gè)字符.因為一個(gè)ASCII char是一個(gè)0到127之間的整數,那么哈希函數的值介于0到1016(127*8)之間,這個(gè)限制肯定不會(huì )產(chǎn)生一個(gè)均勻的分布.
為了減少沖突:
1. 開(kāi)放地址法
2. 鏈地址法
開(kāi)放地址法:
讓指定的數組大小兩倍于需要存儲的數據量.
因此,可能一半的單元是空的.當沖突發(fā)生時(shí),一個(gè)方法是通過(guò)系統的方法找到數組的一個(gè)空位,并把這個(gè)單詞填入,而不再用哈希函數得到的數組下標.
鏈地址法:
創(chuàng )建一個(gè)存放單詞鏈表的數組,數組內不直接存儲單詞.這樣,當發(fā)生沖突的時(shí)候,新的數據項直接接到這個(gè)數組下標所指的鏈表中.
開(kāi)放地址法
在開(kāi)放地址法中如果數據不能直接放在由哈希函數中,就得尋找空白位置,其中有簡(jiǎn)單的三種探索方法.
線(xiàn)性探索法,二次探索法,再哈希法.
線(xiàn)性探索法:就是當通過(guò)哈希函數找到的位置有沖突時(shí),再沿著(zhù)數組下標遞增向下探測,例如:尋找到1002置,但已經(jīng)有數據,就向1003,1004….尋找.
當哈希表越來(lái)越滿(mǎn)的時(shí)候,哈希表的性能就會(huì )嚴重降低.并且填充序列越來(lái)越長(cháng),這種現象稱(chēng)為聚集.
哈希表的容量總是選一個(gè)質(zhì)數.這可以使數據均勻分布.因為哈希函數是以表長(cháng)為模運算.
例如,表長(cháng)為15(下標0到14),有一特定的下標0,步長(cháng)為5,那么只能是0,5,10,0,5,10….以此類(lèi)推,一直循環(huán)下去.只探索到三個(gè)單元.表長(cháng)為13,就會(huì )有0,5,10,2,7,12,4,一直下去,只要表中有一空位,就一直探測下去,由于任何數想整除它都是不可能的,所以會(huì )探測到所有單元.
如果哈希表越來(lái)越滿(mǎn),都必須擴展數組,而且不能簡(jiǎn)單的把舊數組中的數據一一拷貝到新數組的相應位置,因為數據項的位置是由數組的長(cháng)度計算而來(lái)的.所以必須重新按照哈希函數給定數據項的位置.這也就是重新哈?；?這是一個(gè)耗時(shí)的過(guò)程.
為了降低聚集,運用二次探索法,已填入哈希表的數據項和表長(cháng)的比率叫做裝填因子.當裝填因子不太大的時(shí)候,聚集分布得比較連貫,哈希表中可能一部分有大量的聚集,而另一部分比較稀疏.聚集降低了哈希表的性能.
二次探索法的思想就是探測相隔較遠的單元,而不是線(xiàn)性探測的相鄰的單元.
如果數組下標為x,在線(xiàn)性探測中,是x+1,x+2,x+3…..而在二次探測中,是步數的平方,x+ ,x+ .....
如果表的大小為素數且負載因子不大于0.5,所有的探測將會(huì )到達不同的單元,項總是能被插入的.
一旦負載因子到達0.5就得立刻擴展數組.
在二次探索法中也有二次聚集現象,但二次聚集只是一個(gè)很小的理論缺陷.
為了消除原始聚集及二次聚集現象,可以用再哈希法也稱(chēng)雙重散列,原始聚集及二次聚集的原因是因為它們的探測步長(cháng)都是固定的.
現在找到產(chǎn)生一種依賴(lài)于關(guān)鍵字的探測序列,而不是每個(gè)關(guān)鍵字都一樣.這樣即使有關(guān)鍵字被映射到同一個(gè)數組下標,也可以有不同的探測序列.
方法是把關(guān)鍵字用不同的哈希函數再做一次哈?；?這個(gè)結果作為步長(cháng).對于指定的關(guān)鍵字,步長(cháng)在整個(gè)探測過(guò)程中都是不變的,不過(guò)不同的關(guān)鍵字使用不同的步長(cháng).
第二個(gè)哈希函數必須符合以上兩個(gè)要求:
1. 和第一個(gè)哈希函數不一樣
2. 不能輸出0,否則將沒(méi)有步長(cháng),每次探測將是原地踏步,算法將無(wú)法進(jìn)行.
專(zhuān)家發(fā)現以下哈希函數形式很好:
stepSize = constant – (key % constant ) 其中constant為質(zhì)數,并且小于數組容量.
鏈地址法
在開(kāi)放地址法中,尋找一個(gè)減少沖突的方法,
在鏈地址法中,數據項的關(guān)鍵字值還是映射到數組下標,而數據本身保存在每個(gè)單元的鏈表中.
此方法概念上去開(kāi)放地址法簡(jiǎn)單,但代碼相對復雜,因為它涉及到鏈表機制.
此方法中的裝填因子不同于開(kāi)放地址法,因為哈希表中N個(gè)單元要存儲N個(gè)或更多的數據項.裝填因子一般為1,或大于1.
當然如果鏈表中有許多項,存取時(shí)間變長(cháng),找到初始單元的時(shí)間為O(1),而搜索鏈表的時(shí)間與鏈表中的數據項數目M成正比,為O(M).因此并不希望鏈表太滿(mǎn).
在開(kāi)放地址法中,當裝填因子超過(guò)二分之一或三分之二的時(shí)候,哈希表的性能就嚴重下降.在鏈地址法中,裝填因子達到1以上,而且對性能沒(méi)有多在影響,因此鏈地址法比開(kāi)放地址法更鍵壯,尤其是不清楚要存儲多少數據項的時(shí)候.
還有一種方法類(lèi)似于鏈地址法,它在哈希表的每個(gè)單元用的是數組,而不是鏈表.這樣的數組有時(shí)稱(chēng)為桶.這種方法并沒(méi)有鏈地址法有效,因為桶容量不好選擇.太小會(huì )溢出,太大浪費空間.
對于哈希函數的經(jīng)驗就是既簡(jiǎn)單又快,而且去掉關(guān)鍵字中的無(wú)用數據,并盡量全用關(guān)鍵字的所有數據.
在實(shí)際情況中,裝填因子取決于存儲速度與效率之間的平衡.裝填因子變小,效率下降,但速度上升..
