一、HashMap 簡(jiǎn)介

HashMap 底層采用哈希表結(jié)構(gòu) 數(shù)組加鏈表加紅黑樹(shù)實(shí)現(xiàn)，允許儲(chǔ)存null鍵和null值

數(shù)組優(yōu)點(diǎn)：通過(guò)數(shù)組下標(biāo)可以快速實(shí)現(xiàn)對(duì)數(shù)組元素的訪(fǎng)問(wèn)，效率高

鏈表優(yōu)點(diǎn)：插入或刪除數(shù)據(jù)不需要移動(dòng)元素，只需要修改節(jié)點(diǎn)引用效率高

二、源碼分析2.1 繼承和實(shí)現(xiàn)

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L;

繼承AbstractMap<K,V>

實(shí)現(xiàn)了map接口 cloneable接口和可序列化接口

2.2 屬性

//hashmap默認(rèn)容量為 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap默認(rèn)容量 16//最大容量為2的30 1073741824static final int MAXIMUM_CAPACITY = 1 << 30; ////默認(rèn)加載因子為0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;//鏈表轉(zhuǎn)為紅黑樹(shù)的閾值static final int TREEIFY_THRESHOLD = 8;//紅黑樹(shù)轉(zhuǎn)為鏈表的閾值static final int UNTREEIFY_THRESHOLD = 6;//鏈表轉(zhuǎn)為紅黑樹(shù)時(shí)數(shù)組容量必須大于64static final int MIN_TREEIFY_CAPACITY = 64;//transient Node<K,V>[] table;transient Set<Map.Entry<K,V>> entrySet;transient int size;//用于快速失敗機(jī)制 在對(duì)HashMap進(jìn)行迭代時(shí)，如果期間其他線(xiàn)程的參與導(dǎo)致HashMap的結(jié)構(gòu)發(fā)生變化了（比如put，remove等操作），直接拋出ConcurrentModificationException異常transient int modCount;//擴(kuò)容閾值，計(jì)算方法為數(shù)組容量*填充因子int threshold;//加載因子 填充因子final float loadFactor;

loadFactor決定數(shù)組何時(shí)進(jìn)行擴(kuò)容，而且為什么是0.75f

它也叫擴(kuò)容因子 比如數(shù)組長(zhǎng)度為32，所以數(shù)組擴(kuò)容閾值為32*0.75=24當(dāng)數(shù)組中數(shù)據(jù)個(gè)數(shù)為24時(shí)數(shù)組進(jìn)行擴(kuò)容，

數(shù)組容量在創(chuàng)建的時(shí)候就確定，擴(kuò)容時(shí)重新創(chuàng)建一個(gè)指定容量的數(shù)組，然后講舊數(shù)組的值復(fù)制到新數(shù)組中，擴(kuò)容過(guò)程非常耗時(shí)，所以0.75時(shí)基于容量和性能之間平衡的結(jié)果。

如果加載因子過(guò)大，也就是擴(kuò)容閾值會(huì)變大，擴(kuò)容門(mén)檻高，這樣容量的占用率就會(huì)降低，但哈希碰撞的幾率就會(huì)增加，效率下降 如果加載因子過(guò)小，擴(kuò)容閾值變小，擴(kuò)容門(mén)檻低，容量占用變大但哈希碰撞幾率下降

此外用于存儲(chǔ)數(shù)據(jù)的table字段使用transient修飾，通過(guò)transient修飾的字段在序列化的時(shí)候?qū)⒈慌懦谕猓敲碒ashMap在序列化后進(jìn)行反序列化時(shí)，是如何恢復(fù)數(shù)據(jù)的呢？HashMap通過(guò)自定義的readObject/writeObject方法自定義序列化和反序列化操作。這樣做主要是出于以下兩點(diǎn)考慮：

1.table一般不會(huì)存滿(mǎn)，即容量大于實(shí)際鍵值對(duì)個(gè)數(shù)，序列化table未使用的部分不僅浪費(fèi)時(shí)間也浪費(fèi)空間；

2.key對(duì)應(yīng)的類(lèi)型如果沒(méi)有重寫(xiě)hashCode方法，那么它將調(diào)用Object的hashCode方法，該方法為native方法，在不同JVM下實(shí)現(xiàn)可能不同；換句話(huà)說(shuō)，同一個(gè)鍵值對(duì)在不同的JVM環(huán)境下，在table中存儲(chǔ)的位置可能不同，那么在反序列化table操作時(shí)可能會(huì)出錯(cuò)。

所以在HashXXX類(lèi)中（如HashTable，HashSet，LinkedHashMap等等），我們可以看到，這些類(lèi)用于存儲(chǔ)數(shù)據(jù)的字段都用transient修飾，并且都自定義了readObject/writeObject方法。readObject/writeObject方法

2.3 節(jié)點(diǎn)類(lèi)型Node內(nèi)部類(lèi)

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next; } public final K getKey(){ return key; } public final V getValue() { return value; } public final String toString() { return key + '=' + value; } public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue; } public final boolean equals(Object o) {if (o == this) return true;if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false; }}

Node包含四個(gè)字段

final int hash; final K key; V value; Node<K,V> next;//包含鏈表下一個(gè)節(jié)點(diǎn)

HashMap通過(guò)hash方法計(jì)算key的哈希值，然后通過(guò)（n-1）&hash得到key在數(shù)組中存放的下標(biāo)，當(dāng)兩個(gè)key相同時(shí)，會(huì)以鏈地址法處理哈希碰撞

在鏈表中查找數(shù)據(jù)必須從第一個(gè)元素開(kāi)始，時(shí)間復(fù)雜度為O n 所以當(dāng)鏈表長(zhǎng)度越來(lái)越長(zhǎng)時(shí)HashMap的查詢(xún)效率就會(huì)越來(lái)越低

所以為了解決這個(gè)問(wèn)題JDK1.8實(shí)現(xiàn)了數(shù)組+鏈表+紅黑樹(shù)來(lái)解決 當(dāng)鏈表長(zhǎng)度超過(guò)8個(gè)時(shí)并且數(shù)組長(zhǎng)度大于64時(shí)進(jìn)行樹(shù)化，轉(zhuǎn)化后查詢(xún)時(shí)間復(fù)雜度為O(logN).

2.4 紅黑樹(shù)的節(jié)點(diǎn)

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next); }

包含左右孩子節(jié)點(diǎn)和雙親結(jié)點(diǎn)，和前驅(qū)節(jié)點(diǎn)，還有節(jié)點(diǎn)是否時(shí)紅或者黑

三、構(gòu)造方法3.1 構(gòu)造器1

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

最常用的構(gòu)造器。默認(rèn)的填充因子 0.75f 這里的填充因子后面會(huì)講到。

3.2 構(gòu)造器2

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}

給定容量構(gòu)造器

3.3 構(gòu)造器3

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)// 如果小于0，拋出異常throw new IllegalArgumentException('Illegal initial capacity: ' + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)//大于最大值initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor))//若填充因子小于0或者判斷非法throw new IllegalArgumentException('Illegal load factor: ' + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);} static final int tableSizeFor(int cap) {int n = cap - 1;　讓cap-1再賦值給n的目的是另找到的目標(biāo)值大于或等于原值n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

給定容量和填充因子。

這里的tableSizeFor會(huì)將傳進(jìn)的容量值進(jìn)行**大于等于最近**二次冪處理。跟循環(huán)數(shù)組的處理方式差不多

3.4 構(gòu)造器4

public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false);}四、put

public V put(K key, V value) { //底層是調(diào)用putval return putVal(hash(key), key, value, false, true);} //這里調(diào)用了hashmap提供的hash方法，32為都參與了運(yùn)算所以降低了hash碰撞的幾率，這里還跟數(shù)組容量有關(guān)//下面再討論 static final int hash(Object key) {int h; //這里就可以看到hashmapreturn (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

通過(guò)hash函數(shù)可以看到當(dāng)key為null時(shí)，key為0，所以HashMap 是允許儲(chǔ)存空值的。而后面的公式通過(guò)hashcode的高16位異或低1位得到的hash值，主要從性能、哈希碰撞角度考慮，減少系統(tǒng)開(kāi)銷(xiāo)，不會(huì)因?yàn)楦呶粵](méi)有參與下標(biāo)計(jì)算而引起的碰撞

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //請(qǐng)注意這里的hash是已經(jīng)算過(guò)的hash(key)，然后計(jì)算數(shù)組下標(biāo)位置(n - 1) & hash Node<K,V>[] tab; Node<K,V> p; int n, i; //首先判斷數(shù)組哈希表是否為null或者長(zhǎng)度為0，是則進(jìn)行數(shù)組初始化操作 if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; //這里tab指向table數(shù)組 n是數(shù)組長(zhǎng)度 //如果該數(shù)組下標(biāo)位置沒(méi)有數(shù)據(jù)直接插入 if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null); else {//該位置有元素 Node<K,V> e; K k;//首先判斷此位置的值的hash和key的地址和值是否相等//如果相等直接覆蓋//小問(wèn)題這里為什么先判斷hash值而不是判斷key值，因?yàn)閔ash值判斷最快，如果hash值不同就不用判斷下面的//hash不同則key一定不同，但key相同hash值是可能相同的，效率提高if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//否則就是該位置可以不存在，如果該節(jié)點(diǎn)是紅黑樹(shù)類(lèi)型，else if (p instanceof TreeNode) //則按照紅黑樹(shù)的插入 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else { //否則就為鏈表結(jié)構(gòu)，遍歷鏈表，尾插 for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果鏈表長(zhǎng)度大于等于轉(zhuǎn)為紅黑樹(shù)閾值8，則轉(zhuǎn)為紅黑樹(shù) //這里為什么要-1，因?yàn)閿?shù)組下標(biāo)從0開(kāi)始 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //轉(zhuǎn)為紅黑樹(shù)操作時(shí)，內(nèi)部還會(huì)判斷數(shù)組長(zhǎng)度是否小于MIN_TREEIFY_CAPACITY 64，如果是的話(huà)不轉(zhuǎn)換treeifyBin(tab, hash); break;//退出}//如果鏈表中已經(jīng)存在該key，直接覆蓋if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;//遍歷數(shù)組 e = p.nextp = e; }}//e代表被覆蓋的值if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null)e.value = value; // 如果onlyIfAbsent為false并且oldValue為null,我們便對(duì)我們的value進(jìn)行保存 afterNodeAccess(e); return oldValue;} } ++modCount; //如果鍵值對(duì)個(gè)數(shù)大于擴(kuò)容閾值，進(jìn)行擴(kuò)容操作 if (++size > threshold)resize(); afterNodeInsertion(evict); return null;}

流程圖

五、get

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //如果桶為空，size為0，目標(biāo)位置是否為空，是直接返回null if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//如果數(shù)組該下標(biāo)位置就是要找的值，直接返回if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first;//否則如果頭節(jié)點(diǎn)的next有值if ((e = first.next) != null) { //如果該類(lèi)型為紅黑樹(shù)，從紅黑樹(shù)中找 if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key); do {//否則遍歷鏈表if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null);} } return null;}六、resize

數(shù)組的擴(kuò)容和初始化都要靠resize完成

final Node<K,V>[] resize() { //擴(kuò)容前數(shù)組 Node<K,V>[] oldTab = table; //擴(kuò)容前數(shù)組大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; //擴(kuò)容前擴(kuò)容閾值 int oldThr = threshold; //定義新數(shù)組和新閾值 int newCap, newThr = 0; //如果擴(kuò)容前數(shù)組 if (oldCap > 0) {//如果超過(guò)最大值就不用再擴(kuò)容if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab;}//2倍擴(kuò)容不能大于最大值else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //擴(kuò)容閾值/2 newThr = oldThr << 1; // double threshold } //數(shù)組中沒(méi)有值，帶參初始化會(huì)進(jìn)入這里 //且擴(kuò)容因子大于0 else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr; //不帶參默認(rèn)會(huì)到這里 else {//否則擴(kuò)充因子 <= 0//就是沒(méi)初始化過(guò)，使用默認(rèn)的初始化容量，16 * 0.75newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果新容量為0，重新計(jì)算threshold擴(kuò)容閾值 if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({'rawtypes','unchecked'}) //定義新數(shù)組進(jìn)行擴(kuò)容 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //這里采用高低映射的方式進(jìn)行對(duì)新數(shù)組的映射 if (oldTab != null) {//遍歷舊數(shù)組復(fù)制到新數(shù)組中//遍歷for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) {oldTab[j] = null;//如果當(dāng)前節(jié)點(diǎn)鏈表數(shù)據(jù)只有一個(gè)，則直接賦值if (e.next == null) newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode) //否則紅黑樹(shù)操作 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order //鏈表賦值 高低映射 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do {next = e.next;//判斷原索引和擴(kuò)容后索引是否相同if ((e.hash & oldCap) == 0) { //相同則低位鏈表尾插 if (loTail == null)loHead = e; elseloTail.next = e; loTail = e;}else { //否則高位鏈表尾插 if (hiTail == null)hiHead = e; elsehiTail.next = e; hiTail = e;} } while ((e = next) != null); //如果低位映射不為空，斷低位尾部后的數(shù)據(jù)，因?yàn)槲舶秃罂赡苓€會(huì)有數(shù)據(jù)，因?yàn)槭莻€(gè)鏈表，所以采用頭尾引用來(lái)記錄有效值 //付給新數(shù)組 if (loTail != null) {loTail.next = null;newTab[j] = loHead; } //高位引用 直接講原索引+oldCap放到哈希桶中 //因?yàn)槭?倍擴(kuò)容，擴(kuò)容后位置是原位置+增長(zhǎng)的長(zhǎng)度 if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead; }} }} } return newTab;}七、基于JDK1.7的優(yōu)化7.1 底層實(shí)現(xiàn)

1.7基于數(shù)組+鏈表 而1.8基于鏈表+數(shù)組+紅黑樹(shù)

7.2 hash

final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}

效率基于1.8低

7.3 put

1.7使用的是數(shù)組加鏈表，解決哈希沖突采用的是鏈表，而且1.8采用的是尾插，而1.7采用頭插

7.4 擴(kuò)容

1.7在擴(kuò)容時(shí)會(huì)重新計(jì)算h每個(gè)元素的hash值，按舊鏈表的正序遍歷鏈表，然后在新鏈表的頭部插入，所以會(huì)出現(xiàn)逆序的情況，而1.8是通過(guò)高低位映射，不會(huì)出現(xiàn)逆序。

到此這篇關(guān)于Java源碼解析之HashMap的put、resize方法詳解的文章就介紹到這了,更多相關(guān)HashMap的put、resize方法內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！