目錄
一跋炕、數(shù)據(jù)模型
? 在網(wǎng)上看過一些所謂的HashMap源碼分析，大部分依舊是比較抽象的律适。究其原因辐烂，主要還是對(duì)HashMap的數(shù)據(jù)結(jié)構(gòu)不理解。以下以圖示展示捂贿。
?
HashMap中存在一個(gè)內(nèi)部類：
? ? static class Node<K,V> implements Map.Entry<K,V> {
? ? ? ? final int hash;
? ? ? ? final K key;
? ? ? ? V value;
? ? ? ? Node<K,V> next;
? ? ? ? // do soemthig
? ? }
該內(nèi)部類中纠修，有四個(gè)屬性，我們存儲(chǔ)的是key和value厂僧。其中hash通過key計(jì)算的hashcode值扣草，next是指向下一個(gè)節(jié)點(diǎn)。由此可以理解存儲(chǔ)原理了颜屠。
二辰妙、重要屬性
? ? /**
? ? * The default initial capacity - MUST be a power of two.
? ? */
? ? // 思考:為什么必須是2的倍數(shù)?
? ? static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
? ? // 最大長(zhǎng)度
? ? static final int MAXIMUM_CAPACITY = 1 << 30;
int threshold;
threshold = capacity * loadFactor，當(dāng)Size>=threshold的時(shí)候甫窟，那么就要考慮對(duì)數(shù)組的擴(kuò)增了密浑，也就是說，這個(gè)的意思就是衡量數(shù)組是否需要擴(kuò)增的一個(gè)標(biāo)準(zhǔn)粗井。同時(shí)需要對(duì)應(yīng)數(shù)組上有元素尔破。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
負(fù)載因子：該屬性是表示在擴(kuò)容之前容量占有率的一個(gè)標(biāo)尺。它控制數(shù)組存放Node是的疏密程度浇衬。loadFactor越趨近于1懒构，那么數(shù)組中存放的數(shù)據(jù)(entry)也就越多，也就越密径玖，也就是會(huì)讓鏈表的長(zhǎng)度增加，loadFactor越小颤介，也就是趨近于0梳星，那么數(shù)組中存放的數(shù)據(jù)也就越稀赞赖。默認(rèn)的0.75f是一個(gè)權(quán)衡后的值。
? ? static final int TREEIFY_THRESHOLD = 8;
如果鏈表超過了這個(gè)值冤灾，則將單鏈表轉(zhuǎn)變?yōu)榧t黑樹前域。（1.8版本）
? ? static final int UNTREEIFY_THRESHOLD = 6;
如果紅黑樹的節(jié)點(diǎn)被刪，且小于該閾值韵吨，則變?yōu)殒湵怼?/p>
? ? transient int size;
記錄數(shù)組已使用的容量匿垄，用來個(gè)閾值進(jìn)行比較。
final float loadFactor;
填充因子
static final int MIN_TREEIFY_CAPACITY = 64;
桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對(duì)應(yīng)的table的最小大小
三归粉、構(gòu)造方法
? ? // 構(gòu)造函數(shù)一
? ? public HashMap() {
? ? ? ? this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
? ? }
? ? // 構(gòu)造函數(shù)二
? ? public HashMap(int initialCapacity) {
? ? ? ? this(initialCapacity, DEFAULT_LOAD_FACTOR);
? ? }
? ? // 構(gòu)造函數(shù)三
? ? public HashMap(int initialCapacity, float loadFactor) {
? ? ? ? if (initialCapacity < 0)
? ? ? ? ? ? throw new IllegalArgumentException("Illegal initial capacity: " +
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity);
? ? ? ? if (initialCapacity > MAXIMUM_CAPACITY)
? ? ? ? ? ? initialCapacity = MAXIMUM_CAPACITY;
? ? ? ? if (loadFactor <= 0 || Float.isNaN(loadFactor))
? ? ? ? ? ? throw new IllegalArgumentException("Illegal load factor: " +
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loadFactor);
? ? ? ? this.loadFactor = loadFactor;
? ? ? ? this.threshold = tableSizeFor(initialCapacity);
? ? }
? ? // 構(gòu)造函數(shù)四
? ? public HashMap(Map<? extends K, ? extends V> m) {
? ? ? ? this.loadFactor = DEFAULT_LOAD_FACTOR;
? ? ? ? putMapEntries(m, false);
? ? }
我們用的最多的就是第一個(gè)構(gòu)造方法椿疗，負(fù)載因子默認(rèn)是0.75f。構(gòu)造函數(shù)三是手動(dòng)設(shè)置初始容量和負(fù)載因子糠悼，構(gòu)造函數(shù)二調(diào)用的構(gòu)造函數(shù)三届榄，手動(dòng)設(shè)置初始容量大小。構(gòu)造函數(shù)是將別的map映射到自己的map中倔喂。
四铝条、普通方法
put()
上面我們了解了HashMap的存儲(chǔ)結(jié)構(gòu)。在給HashMap中添加元素的時(shí)候席噩，我們應(yīng)該考慮這樣一個(gè)問題：如何確定元素的添加的位置班缰？
我們來分析代碼：
? ? public V put(K key, V value) {
? ? ? ? return putVal(hash(key), key, value, false, true);
? ? }
? ? final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
? ? ? ? Node<K,V>[] tab; Node<K,V> p; int n, i;
? ? ? ? // 如果數(shù)組未進(jìn)行初始化或者為空，則通過resize()初始化,并返回?cái)?shù)組的長(zhǎng)度
? ? ? ? if ((tab = table) == null || (n = tab.length) == 0)
? ? ? ? ? ? n = (tab = resize()).length;
? ? ? ? // (n - 1) & hash 確定節(jié)點(diǎn)放在數(shù)組的哪個(gè)位置（這個(gè)表達(dá)式中可以看出為什么數(shù)組的擴(kuò)容的長(zhǎng)度為什么要是2的n次冪的原因了）
? ? ? ? // 確定后的在數(shù)組中的該位置為空悼枢，則新的節(jié)點(diǎn)放在這個(gè)位置
? ? ? ? if ((p = tab[i = (n - 1) & hash]) == null)
? ? ? ? ? ? tab[i] = newNode(hash, key, value, null);
? ? ? ? // 以下的else中的邏輯表示確定的該位置不是空
? ? ? ? else {
? ? ? ? ? ? Node<K,V> e; K k;
? ? ? ? ? ? // 如果與數(shù)組中的節(jié)點(diǎn)的hash值相等埠忘，則直接取代
? ? ? ? ? ? if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? e = p;
? ? ? ? ? ? // 如果是紅黑樹節(jié)點(diǎn)
? ? ? ? ? ? else if (p instanceof TreeNode)
? ? ? ? ? ? ? ? e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
? ? ? ? ? ? // 如果是鏈表節(jié)點(diǎn)
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? for (int binCount = 0; ; ++binCount) {
? ? ? ? ? ? ? ? ? ? if ((e = p.next) == null) {
? ? ? ? ? ? ? ? ? ? ? ? p.next = newNode(hash, key, value, null);
? ? ? ? ? ? ? ? ? ? ? ? // 節(jié)點(diǎn)到達(dá)閾值，轉(zhuǎn)為紅黑樹
? ? ? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
? ? ? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? p = e;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if (e != null) { // existing mapping for key
? ? ? ? ? ? ? ? V oldValue = e.value;
? ? ? ? ? ? ? ? if (!onlyIfAbsent || oldValue == null)
? ? ? ? ? ? ? ? ? ? e.value = value;
? ? ? ? ? ? ? ? afterNodeAccess(e);
? ? ? ? ? ? ? ? return oldValue;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? ++modCount;
? ? ? ? // 如果數(shù)組中的元素個(gè)數(shù)超過閾值萧芙，則進(jìn)行擴(kuò)容
? ? ? ? if (++size > threshold)
? ? ? ? ? ? resize();
? ? ? ? afterNodeInsertion(evict);
? ? ? ? return null;
? ? }
通過以上的源碼给梅，我們可以看出。在添加新節(jié)點(diǎn)時(shí)双揪，通過hash確定其位置动羽。分以下種情況：
數(shù)組的該位置為空，直接添加到該位置
數(shù)組的該位置不為空渔期，但是與新節(jié)點(diǎn)的hash相同运吓，則直接取代
數(shù)組的該位置不為空，且節(jié)點(diǎn)下面是單鏈表
數(shù)組的該位置不為空疯趟，且元素下面是紅黑樹
確定位置時(shí)拘哨，hash值起著重要的作用，我們看看該方法：
? ? static final int hash(Object key) {
? ? ? ? int h;
? ? ? ? return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
? ? }
這里通過位運(yùn)算重新計(jì)算了hash值的值信峻。為什么要重新計(jì)算倦青？
主要是因?yàn)閚值比較小，hash只參與了低位運(yùn)算盹舞，高位運(yùn)算沒有用上产镐。這就增大了hash值的碰撞概率隘庄。而通過這種位運(yùn)算的計(jì)算方式，使得高位運(yùn)算參與其中癣亚，減小了hash的碰撞概率丑掺，使hash值盡可能散開。
注意：我們?cè)诜治鲋匾獙傩訢EFAULT_INITIAL_CAPACITY的時(shí)候述雾，數(shù)組的初始化或者擴(kuò)容為什么給必須是2的n次冪街州？
在以上源碼的(n - 1) & hash中給出了答案：(n - 1) & hash等價(jià)于對(duì) length 取余。但取余的計(jì)算效率沒有位運(yùn)算高玻孟，所以(n - 1) & hash也是一個(gè)小的優(yōu)化唆缴。例如，假設(shè) hash = 185取募，n = 16琐谤。
resize()
這個(gè)方法我們?cè)趐ut()方法中已經(jīng)調(diào)用過，作用是用來進(jìn)行數(shù)組的初始化和擴(kuò)容玩敏。下面看看源碼：
final Node<K,V>[] resize() {
? ? // 當(dāng)前table保存
? ? Node<K,V>[] oldTab = table;
? ? // 保存table大小
? ? int oldCap = (oldTab == null) ? 0 : oldTab.length;
? ? // 保存當(dāng)前閾值
? ? int oldThr = threshold;
? ? int newCap, newThr = 0;
? ? // 之前table大小大于0
? ? if (oldCap > 0) {
? ? ? ? // 之前table大于最大容量
? ? ? ? if (oldCap >= MAXIMUM_CAPACITY) {
? ? ? ? ? ? // 閾值為最大整形
? ? ? ? ? ? threshold = Integer.MAX_VALUE;
? ? ? ? ? ? return oldTab;
? ? ? ? }
? ? ? ? // 容量翻倍斗忌，使用左移，效率更高
? ? ? ? else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
? ? ? ? ? ? oldCap >= DEFAULT_INITIAL_CAPACITY)
? ? ? ? ? ? // 閾值翻倍
? ? ? ? ? ? newThr = oldThr << 1; // double threshold
? ? }
? ? // 之前閾值大于0
? ? else if (oldThr > 0)
? ? ? ? newCap = oldThr;
? ? // oldCap = 0并且oldThr = 0旺聚，使用缺省值（如使用HashMap()構(gòu)造函數(shù)织阳，之后再插入一個(gè)元素會(huì)調(diào)用resize函數(shù)，會(huì)進(jìn)入這一步）
? ? else {? ? ? ? ?
? ? ? ? newCap = DEFAULT_INITIAL_CAPACITY;
? ? ? ? newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
? ? }
? ? // 新閾值為0
? ? 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"})
? ? // 初始化table
? ? Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
? ? table = newTab;
? ? // 之前的table已經(jīng)初始化過
? ? if (oldTab != null) {
? ? ? ? // 復(fù)制元素砰粹，重新進(jìn)行hash
? ? ? ? for (int j = 0; j < oldCap; ++j) {
? ? ? ? ? ? Node<K,V> e;
? ? ? ? ? ? if ((e = oldTab[j]) != null) {
? ? ? ? ? ? ? ? oldTab[j] = null;
? ? ? ? ? ? ? ? if (e.next == null)
? ? ? ? ? ? ? ? ? ? newTab[e.hash & (newCap - 1)] = e;
? ? ? ? ? ? ? ? else if (e instanceof TreeNode)
? ? ? ? ? ? ? ? ? ? ((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;
? ? ? ? ? ? ? ? ? ? // 將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0進(jìn)行分割唧躲，分成兩個(gè)不同的鏈表，完成rehash
? ? ? ? ? ? ? ? ? ? do {
? ? ? ? ? ? ? ? ? ? ? ? next = e.next;
? ? ? ? ? ? ? ? ? ? ? ? if ((e.hash & oldCap) == 0) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? if (loTail == null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail = e;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? ? ? ? ? if (hiTail == null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail = e;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? } while ((e = next) != null);
? ? ? ? ? ? ? ? ? ? if (loTail != null) {
? ? ? ? ? ? ? ? ? ? ? ? loTail.next = null;
? ? ? ? ? ? ? ? ? ? ? ? newTab[j] = loHead;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? if (hiTail != null) {
? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = null;
? ? ? ? ? ? ? ? ? ? ? ? newTab[j + oldCap] = hiHead;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return newTab;
}
其實(shí)仔細(xì)分析源代碼碱璃，基本上只要理解了HashMap的結(jié)構(gòu)弄痹，其余的邏輯也就和 清楚了。
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;
? ? ? ? // 桶數(shù)組不為空且長(zhǎng)度大于0且通過hash定位的位置節(jié)點(diǎn)不為空嵌器，則走以下流程肛真，不然返回null
? ? ? ? if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
? ? ? ? ? ? // 如果與桶數(shù)組該位置的節(jié)點(diǎn)hash相同，則返回該節(jié)點(diǎn)
? ? ? ? ? ? if (first.hash == hash && // always check first node
? ? ? ? ? ? ? ? ((k = first.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? return first;
? ? ? ? ? ? // 如果該位置節(jié)點(diǎn)還有節(jié)點(diǎn)爽航，則繼續(xù)查找
? ? ? ? ? ? if ((e = first.next) != null) {
? ? ? ? ? ? ? ? // 桶數(shù)組該節(jié)點(diǎn)下面是紅黑樹
? ? ? ? ? ? ? ? if (first instanceof TreeNode)
? ? ? ? ? ? ? ? ? ? return ((TreeNode<K,V>)first).getTreeNode(hash, key);
? ? ? ? ? ? ? ? // 桶數(shù)組該節(jié)點(diǎn)下面是鏈表蚓让，遍歷
? ? ? ? ? ? ? ? do {
? ? ? ? ? ? ? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? ? ? ? ? return e;
? ? ? ? ? ? ? ? } while ((e = e.next) != null);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return null;
? ? }
五、總結(jié)
? 一直都覺得HashMap的源碼很簡(jiǎn)單讥珍，仔細(xì)看看历极，其實(shí)不然。其中涉及了很多很多的知識(shí)點(diǎn)衷佃，比如數(shù)據(jù)結(jié)構(gòu)就涉及了數(shù)組趟卸、鏈表和紅黑樹。其余的細(xì)節(jié)都是數(shù)不勝數(shù)。細(xì)細(xì)研讀該源碼一整天锄列，都沒有將其中的細(xì)節(jié)詳盡解析新蟆。
不過，在這篇文章結(jié)束之時(shí)右蕊，也有一些思考和想法：
1.數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，也是靈魂（通常伴隨算法）吮螺。只有對(duì)數(shù)據(jù)結(jié)構(gòu)了然于心饶囚，才能詳細(xì)了解底層原理；
2.伴隨jdk升級(jí)的過程中鸠补，我們能很明顯感受到一些優(yōu)化萝风。比如將十進(jìn)制的值優(yōu)化為二進(jìn)制的值；十進(jìn)制的計(jì)算優(yōu)化為位運(yùn)算紫岩；構(gòu)造函數(shù)中规惰，不給出長(zhǎng)度，而是在添加第一個(gè)元素的時(shí)候給出長(zhǎng)度（默認(rèn)長(zhǎng)度或者設(shè)置的長(zhǎng)度）泉蝌；
3.put()方法是HashMap的核心歇万，弄清楚了這個(gè)方法，其余的源代碼都不難勋陪；
4.讀源碼一定要靜下心來贪磺，心不靜，就只能浮在表面诅愚；
5.個(gè)人水平和精力有限寒锚，難免有漏洞，希望大家多多指教违孝。
