HashMap/hashTable詳解

Map是映射鍵值的對象。map不能包含重復(fù)鍵:每個鍵最多只能映射一個值。它模擬了數(shù)學(xué)函數(shù)的抽象。

Map接口包括基本操作的方法(如put、get、remove、containsKey、containsValue、size和empty)、批量操作(如putAll和clear)和集合視圖(如keySet、entrySet和values)。Java平臺包含三個通用的映射實(shí)現(xiàn):HashMap、TreeMap和LinkedHashMap。

它們的行為和性能與Set接口部分中描述的HashSet、TreeSet和LinkedHashSet類似。

下面從HashMap和hashTable兩個容器分別介紹對比介紹一下。

下面我來分別看一下HashMap 和 hashTable 在無參構(gòu)造函數(shù)實(shí)例化的具體實(shí)例：

由上圖我們可以看到HashMap的無參數(shù)構(gòu)造函數(shù)new 了一個：容量為16，加載因子為0.75，閾值為12的容器。

而hashTable的無參數(shù)構(gòu)造函數(shù)則new 了一個：容量為11，加載因子為0.75，閾值為8的容器。

其中閾值為容量和加載因子的乘積，意思是如果容器到了這個值，那么就要實(shí)施擴(kuò)容的機(jī)制了。下面我們看一下這兩個容器到了閾值分別是如何擴(kuò)容的呢？

首先是HashMap的擴(kuò)容機(jī)制：

從源碼上看，容器擴(kuò)大了原容器的length*2倍。必須是2的冥。（2的幾次方）

里面還有一個判斷如果原來容器的容量已經(jīng)達(dá)到了最大值，那么就把閾值調(diào)整到最大值，然后把原數(shù)組數(shù)據(jù)映射到新的更大的數(shù)組當(dāng)中。這也就是說當(dāng)數(shù)據(jù)量過多并且知道最大值的時候?yàn)榱吮苊夤１肀恢匦律⒘?防止內(nèi)部數(shù)據(jù)結(jié)構(gòu)頻繁被重新構(gòu)建)。

然后我們看一下hashTable是如何擴(kuò)容的：

原容器的大小乘以2+1，保證得到的數(shù)據(jù)是一個奇數(shù)。那么到這了我們考慮一下為什么table擴(kuò)容要求是奇數(shù)，而map擴(kuò)容必須是2的冥呢？

那么我們下面說一下HashMap的擴(kuò)容機(jī)制以及確認(rèn)元素位置的源碼，來分析一下為什么設(shè)計成2的冥：

通過位運(yùn)算符保證初始容量一定是2的冥

為了防止hash碰撞，在Entry數(shù)組（單鏈表）中為了保證每一個位置只有一個元素，通過hash%table.length=bucketIndex，bucketIndex為元素具體的位置，這樣能夠均勻的分布到容器的各個位置且不會有重復(fù)的。對集合操作效率也高。那么我們看一下源碼中是如何找到元素具體的位置的：

為了減少碰撞HashMap是做了二次hash運(yùn)算的。

h為最后計算的hash值，length為容器的容量。假設(shè)容量 = 16，我們計算一個hash值，來看一下h具體值為，并且我們計算一下indexFor的值是什么：

可以看到具體的hash值和在容器中的一個位置信息。

然后我們看一下，巧合的是根據(jù)我們的計算h & (length - 1) == h % length兩個等式正好相等。且

這個的位運(yùn)算的效率更高，這個應(yīng)該就是容量必須為2的冪的原因。保證了數(shù)據(jù)分散的均勻。

并且通過二次hash減少碰撞，那么什么是碰撞呢？碰撞就是兩個數(shù)計算出來的hash值一樣，且equals e1.equals(e2)不相等，這樣在一個hash位置上就會存儲多個鏈表。在取值或者刪除數(shù)據(jù)元素的時候效率比較低。

上面就是說的HashMap的容量為什么是2的冥的原因，下面來介紹一下hashTable的初始容量為什么是11，以及擴(kuò)容機(jī)制？

hashTable的key獲取hash為直接返回的當(dāng)前key的hashCode值例如：如果是一個String的lisi返回3322014。

通過拆分lisi為char數(shù)組元素，且每個值拿到ASCII值的十進(jìn)制。31*hash + 當(dāng)前碼值。

直接計算當(dāng)前hash & long int的最大值%當(dāng)前容器的容量，獲得具體在容器中的位置。

int newCapacity = (oldCapacity << 1) + 1;這個是hashTable的一個擴(kuò)容計算規(guī)則：保證了擴(kuò)容后容量始終為奇數(shù)。

那么hashTable的擴(kuò)容容量始終保證為奇數(shù)呢？

首先我猜測跟他的確認(rèn)地址是有關(guān)系的，在就是由于hashTable全程加了同步鎖為線程安全的，為了性能更高的操作容器才會這么設(shè)置，這塊如果有小伙伴能講解的比較清楚也歡迎評論交流指導(dǎo)。

最后總結(jié)一下：哈希表的大小為素數(shù)時，簡單的取模哈希的結(jié)果會更加均勻，所以單從這一點(diǎn)上看，HashTable的哈希表大小選擇，似乎更高明些。但另一方面我們又知道，在取模計算時，如果模數(shù)是2的冪，那么我們可以直接使用位運(yùn)算來得到結(jié)果，效率要大大高于做除法。所以從hash計算的效率上，又是HashMap更勝一籌。之所以不一樣是因?yàn)镠ashMap用的位移運(yùn)算確認(rèn)具體位置，而hashTable是直接用的模。（事實(shí)就是HashMap為了加快hash的速度，將哈希表的大小固定為了2的冪。當(dāng)然這引入了哈希分布不均勻的問題，所以HashMap為解決這問題，又對hash算法做了一些改動。HashMap和HashTable在計算hash時都用到了一個叫hashSeed的變量。這是因?yàn)橛成涞酵粋€hash桶內(nèi)的Entry對象，是以鏈表的形式存在的，而鏈表的查詢效率比較低，所以HashMap/HashTable的效率對哈希沖突非常敏感，所以可以額外開啟一個可選hash（hashSeed），從而減少哈希沖突。）

在結(jié)尾總結(jié)性的補(bǔ)充一下這個hashTable和HashMap的異同：

1.首先父類不同。hashTable的父類是Dictionary<K,V>，HashMap的父類是AbstractMap<K,V>.

2.HashMap是支持null鍵和null值的，而HashTable在遇到null時，會拋出NullPointerException異常。

3.初始化大小不同，擴(kuò)容機(jī)制不同。

4.hashTable為線程安全的，方法級別的強(qiáng)制同步。HashMap非線程安全的。所以HashMap效率性能要高。

相同點(diǎn)：都實(shí)現(xiàn)了Map<K,V>接口。

到此這篇關(guān)于Java集合之HashMap/hashTable詳解的文章就介紹到這了,更多相關(guān)HashMap/hashTable詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論