學(xué)習(xí)資料；
- 《Java程序性能優(yōu)化》
- 美團(tuán)點(diǎn)評技術(shù)團(tuán)隊(duì) Java 8系列之重新認(rèn)識HashMap
- 張旭童大佬 面試必備：HashMap源碼解析（JDK8）
這篇筆記是第二次整理，第一次是16年11月份，只是之前能寫出來的太少，中途而廢。最近又來看HashMap的東西，比上次看時理解的東西多了些，就重新整理下
目前，HashMap內(nèi)，還是有很多問題，不明白，以后會再做補(bǔ)充
重點(diǎn)學(xué)習(xí)HashMap，本篇學(xué)習(xí)筆記，會有很多錯誤，請指出
1. Map接口
實(shí)現(xiàn)map接口的主要有四個HashTable,HashMap,LinkedHashMap,TreeMap
HashTable,HashMap區(qū)別：
-
HashTable的大部分方法都做了同步，而HashMap沒有。HashMap不是線程安全的 -
HashTable不允許key，value為null，而HashMap可以為null - 兩者對
key的hash算法和hash值到內(nèi)存索引的映射算法不同
HashMap優(yōu)點(diǎn)特性就是高性能，存放和查詢是很高效的，缺點(diǎn)就是無序性，存入的元素，在遍歷時是無序的
LinkedHashMap繼承自HashMap，除了具備HashMap高性能優(yōu)點(diǎn)外，還具有有序性。LinkedHashMap在HashMap的基礎(chǔ)上，增加了一個鏈表來存放元素的順序
LinkedHashMap可以簡單理解為一個維護(hù)了元素次序表的HashMap
LinkedHashMap提供了兩種類型的順序：存放(插入)元素時的順序，最近訪問順序
可以使用3個參數(shù)的構(gòu)造方法來指定排序行為
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
accessOrder為true時，按照元素最后訪問時間來排序，默認(rèn)情況下為false
當(dāng)為true時，使用get()執(zhí)行來一次獲取操作時，當(dāng)前元素會被挪到整個LinkedHashMap最末尾位置
需要注意的是，當(dāng)設(shè)置accessOrder為true時，不能用于Iterator遍歷
不要在迭代器模式中修改被迭代的集合
TreeMap實(shí)現(xiàn)了SortMap接口，可以對元素進(jìn)行排序
TreeMap排序是指根據(jù)條件對存入的key進(jìn)行按照規(guī)則進(jìn)行了排序，是基于元素本身的固有順序。而LinkedHashMap只是基于元素進(jìn)入集合的順序或者訪問的先后順序進(jìn)行排序
TreeMap為了確定key的排序，可以通過兩種方式來指定
- 通過
TreeMap的構(gòu)造方法，public TreeMap(Comparator<? super K> comparator)，指定一個Comparator - 使用一個自身實(shí)現(xiàn)了
Comparable接口的key
TreeMap內(nèi)部實(shí)現(xiàn)是基于紅黑樹。紅黑樹是一種平衡查找樹，統(tǒng)計性能要優(yōu)于平衡二叉樹。具有良好的最壞情況運(yùn)行時間，可以在O(log n)時間內(nèi)做查找、插入和刪除，其中n代表樹中元素的數(shù)目
詳細(xì)可以看HashMap、Hashtable、HashSet 和 ConcurrentHashMap 的比較
2. JDK1.8中的HashMap
在之前學(xué)習(xí)時，寫過一個Java基礎(chǔ)學(xué)習(xí)——HashMap原理學(xué)習(xí)，可以幫助理解原理學(xué)習(xí)
個人理解，舉例：
一家超大型購物商場，擁有一百萬種不同品牌的商品
假如，當(dāng)世界上第一家這樣規(guī)模的大型商場開業(yè)時，由于沒啥經(jīng)驗(yàn)，商場的工作人員從倉庫取出商品擺放時，從商場門口開始，在倉庫拿到啥就開始擺放啥，也不管物品是啥，只要能放得下，就依次擺放。而等到顧客來買東西時，全靠隨緣。除非打5折，否則一年也賣不出多少東西
現(xiàn)實(shí)這種情況根本不會發(fā)生，為了方便顧客快速定位商品的相對準(zhǔn)確位置，會 根據(jù)商品的固有屬性來分區(qū)
例如，我最愛的農(nóng)夫山泉，就會放在一個飲品區(qū)，和各種純凈水以及其他的喝的，擺在一個相對集中的區(qū)域。我到了一家從來沒有去過的大型商場去買農(nóng)夫山泉， 購買效率很大程度取決于我用了多久找到農(nóng)夫山泉所在的飲品區(qū)，到了飲品區(qū)，再快速定位到純凈水貨架。實(shí)際生活中，一般情況下，即使很大型的商場，也可以比較快速的買到一瓶
確定飲水區(qū)的過程可以看作為HashMap中涉及hash操作的整個過程
圖來自美團(tuán)技術(shù)點(diǎn)評 Java 8系列之重新認(rèn)識HashMap
簡單說來，HashMap就是將key做hash算法，然后將hash值映射到內(nèi)存地址，之后可以直接獲取key所對應(yīng)的數(shù)據(jù)
HashMap就可以簡單看作這樣一家超大型超市，根據(jù)不同商品固有屬性key，做hash算法后，得到一個index，便得知該商品所處區(qū)域，也就是快速計算得到鏈表數(shù)組索引。而一個品牌的商品肯定不止一個，這樣做hash算法后，結(jié)果index肯定會有沖突，這時就要用到貨架鏈表，將同一個品牌的商品依次擺放在貨架上，最終，一個key就和value建立的映射
JDK1.8中，HashMap內(nèi)部結(jié)構(gòu)是數(shù)組(哈希桶)+鏈表+紅黑樹
HashMap的高性能需要下面3點(diǎn)：
-
hash()算法必須是高效的 -
hash值映射內(nèi)存地址，也就是計算數(shù)組索引，映射算法必須是高效的 - 根據(jù)內(nèi)存地址，數(shù)組索引，可以直接獲取得對應(yīng)的值
最常用到的就是put()，get()方法
Map<String, String> map = new HashMap<>();
map.put("1", "a");
map.put("2", "b");
for (String key : map.keySet()) {
System.out.println("key = " + key + " ;;; value = " + map.get(key));
}
if (map.containsKey("1")) {
map.remove("1");
}
System.out.println("size = " + map.size());
本次重點(diǎn)學(xué)習(xí)存放put()，擴(kuò)容resize()
2.1 構(gòu)造方法
有 4 個 構(gòu)造方法，最經(jīng)常使用的是空參的
public HashMap()-
public HashMap(int initialCapacity)，指定容量 -
public HashMap(int initialCapacity, float loadFactor)，指定容量、負(fù)載因子 -
public HashMap(Map<? extends K, ? extends V> m)，存放另一個HashMap
/**
* The default initial capacity - MUST be a power of two.
* 默認(rèn)大小
*
* 使用空參構(gòu)造方法時，默認(rèn)初始化大小 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
* 默認(rèn)負(fù)載因子
*
* 默認(rèn)情況下的加載因子，可以通過構(gòu)造方法來改變
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
* 鏈表數(shù)組
*
* 這個table會在 HashMap 第一次使用時被創(chuàng)建，一般會在 put()方法時
*
* table.length 一直都會是 2 的 n 次方，這樣設(shè)計的目的在于
* 擴(kuò)容時，更加高效的統(tǒng)計數(shù)組的index，用位運(yùn)算替代取余操作
*/
transient Node<K,V>[] table;
/**
* Constructs an empty HashMap with the default initialcapacity
* (16) and the default load factor (0.75).
*
* 空構(gòu)造方法：初始化 負(fù)載因子(loadFactor)為 0.75
* 此時，默認(rèn)容量大小為 16，閾值就是 12
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
使用空參構(gòu)造方法時，指定loadFactor為默認(rèn)值0.75
負(fù)載因子是0 ～ 1之間的浮點(diǎn)數(shù)，決定了在擴(kuò)容之前，HashMap的內(nèi)部數(shù)組鏈表的填充度
閾值(threshold) = 容量(capacity) * 負(fù)載因子(load factor)
當(dāng)HashMap的實(shí)際容量超過閾值時，HashMap便會擴(kuò)容。因此，實(shí)際上HashMap的實(shí)際填充率不會超過負(fù)載因子
負(fù)載因子也可以設(shè)置為1或者大于1，但此時會導(dǎo)致大量的hash沖突
負(fù)載因子越大，使用越少的內(nèi)存空間，而一個數(shù)組索引位置上的鏈表長度就越大，一個鏈表中存放的元素越多，越容易引起hash值沖突。使用get()方法進(jìn)行獲取元素操作，進(jìn)行遍歷鏈表時的效率也就越低
相反，負(fù)載因子越小，一個數(shù)組索引位置上的鏈表，長度越小，一個鏈表中存放的元素越少，雖然遍歷的效率高了，但也就浪費(fèi)了較多空間
transient，不需要被序列化的屬性可以使用。目前不理解，先不管
2.2 Node，鍵值對單向鏈表
Node[]table數(shù)組中的元素，Node就是存放key，value的對象，結(jié)構(gòu)是單向鏈表，每個Node都會指向下一個，若沒有next就指向null
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 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() {
// 將key 和 value的hash值，異或
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 設(shè)置 Value，并將覆蓋的舊value返回
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 比較兩個Node對象是否相等
// 比較key value是否完全相等
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;
}
}
2.3 數(shù)組索引計算
在1.7中，HashMap內(nèi)部是數(shù)組 + 鏈表
在1.8中，鏈表的長度一旦超過8時，就會轉(zhuǎn)為紅黑樹
// 1.8 增加的變量
static final int TREEIFY_THRESHOLD = 8;
高效確定一個元素key所在鏈表的索引，需要兩步：
- 計算元素
健key的hash值，hash(Object key)方法 - 利用計算得到的
hash，獲取數(shù)組索引，indexFor(hash(key),table.length)
HashMap的高效性，很關(guān)鍵一部分就在于hash()算法以及indexFor()
當(dāng)使用put()方法存放一個元素時，首先會根據(jù)key計算hash值，之后利用hash值，確定該元素所屬鏈表的索引index。也就說這個兩步走，在put()中是必須要走的
JDK1.8中對計算索引兩步走又進(jìn)行了優(yōu)化,先了解1.7的實(shí)現(xiàn)
2.3.1 在JDK1.7中的實(shí)現(xiàn)
目前不懂為啥1.7中，這樣來設(shè)計計算hash值，在知乎看到了也有人問這個問題：
JDK 源碼中 HashMap 的 hash 方法原理是什么？
最高票的回答很贊，而且在回答中答主給了自己的學(xué)習(xí)筆記How is hashCode() calculated in Java?，很有深度
兩步走，第一步，計算hash值
final int hash(Object k) {
int h = 0;
//這個特殊選項(xiàng)先不去管它
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//第一件事：調(diào)用Key自帶的hashCode()函數(shù)獲得初始哈希值
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).
//初始哈希值做進(jìn)一步優(yōu)化（注：^為“異或”操作）
//異或：每一位上的值相同返回0，不同返回1。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
調(diào)用key類型自帶的hashCode()函數(shù)，計算原始哈希值
在最后計算hash值時，用了4次^運(yùn)算，1.8中做的優(yōu)化便是由4次變做了1次
又看到了這篇：HashMap hash方法分析
看懂似懂非懂的
這里原理為啥這么寫的，先不管了，先記結(jié)論
結(jié)論:
無論1.X的JDK，這個hash()方法的優(yōu)化目的都是為了防止Object key自身的hashCode()方法實(shí)現(xiàn)比較差，為了使hash值更加均衡，減少hash沖突
兩步走，第二步，計算索引值
indexFor()的目的是為計算index，在買農(nóng)夫山泉的例子中，就是快速定位飲品區(qū)，然后可以快速找到農(nóng)夫山泉貨架這個步驟
實(shí)際生活中，超市不會一個貨架只擺放一瓶農(nóng)夫山泉。在元素多時，HashMap也不會一個鏈表只存放一個元素
HashMap的最大容量是Integer.MAX_VALUE，但table.length一定不會是這么大。若一個元素占用一個鏈表，那需要一個容量為2 ^ 31 - 1的數(shù)組，這樣雖然index不會存在沖突，但空間上是不允許的
計算這樣一個index首先想到的便是除法散列法
// 求模數(shù)實(shí)際是通過一個除法運(yùn)算得到
h % length
在JDK1.7中，計算鏈表所處的數(shù)組索引index用的是h & (length-1)
用的是&而不是%
這便是代碼設(shè)計者牛B的地方
// 1.8 中已刪除，
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 :
// "length must be a non-zero power of 2";
return h & (length-1);
}
HashMap中鏈表的length總是2的n次方，length總是2的n次方時，h & (length-1)運(yùn)算等價于對length取模，也就是h%length，但&具有更高的效率
這也是為啥要將table.lenth設(shè)計為總是2的n次方原因
2的n次方，必然是偶數(shù)，length -1 為奇數(shù)，轉(zhuǎn)換成二進(jìn)制之后，最后一位為1
當(dāng)h & (length-1)時，最后一位的是0還是1，就取決于h的值，也就是說index的奇偶性取決于h
假如length不一定是2的n次方，當(dāng)length為奇數(shù)時，length-1轉(zhuǎn)換成二進(jìn)制后，最后一位是0，這樣無論h為多少，h & (length-1)時，最后一位的都是0，這樣index都是偶數(shù)，數(shù)組只有偶數(shù)索引處有值，也就造成了空間浪費(fèi)
結(jié)論：
h & (length-1)既高效又能使index分布均勻
2.3.2 1.8中的實(shí)現(xiàn)
在1.8代碼中，indexFor(int h, int length)刪除了，在確定index值時，簡化成了tab[i = (n - 1) & hash]，其中hash便是hash(Object key)方法計算的值，使用的原理和indexFor()還是一樣的，只是減少了一次方法調(diào)用
1.8中獲取索引index
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
只進(jìn)行了一次^運(yùn)算，h值自身的高16位 和 低16位進(jìn)行^運(yùn)算
混合原始哈希碼的高位和低位，以此來加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來
這也彌補(bǔ)了取余時只有低位參與運(yùn)算，而導(dǎo)致hash沖突變多的情況
這么做可以在數(shù)組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷
圖來自美團(tuán)技術(shù)點(diǎn)評 Java 8系列之重新認(rèn)識HashMap
看到有人說(h = key.hashCode()) ^ (h >>> 16)這一步處理，是擾動函數(shù)，目的就是為了是使hash值分布更均勻，之后再計算index也能減少沖突
2.4 put放入
put()
在put()方法內(nèi)，調(diào)用了putVal()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
當(dāng)key已經(jīng)存在的情況下，會將舊的value替換，并返回舊的value
putVal()
- 判斷
HashMap內(nèi)的鏈表數(shù)組table是否已經(jīng)創(chuàng)建過，也就是判斷是否為初始化狀態(tài) - 確定
index，判斷數(shù)組index位置上是否有鏈表，沒有就創(chuàng)建，有就準(zhǔn)備遍歷 - 判斷鏈表上第一元素鍵值對是否和要存入的目標(biāo)鍵值對相等;相等就直接進(jìn)行覆蓋操作
- 判斷鏈表是否已轉(zhuǎn)為紅黑樹
- 遍歷鏈表，過程中確定是否進(jìn)行轉(zhuǎn)換紅黑樹操作，以及根據(jù)目標(biāo)鍵值對確定是加到鏈表尾部還是覆蓋操作
-
put目標(biāo)鍵值對成功，++size，判斷是否需要擴(kuò)容，并返回null
/**
* onlyIfAbsent，為true時，不改變已經(jīng)存在的value
* evict，為false時，說明是在初始化狀態(tài)中調(diào)用
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab，臨時鏈表數(shù)組 ; p ，節(jié)點(diǎn)，臨時鍵值對
// n，臨時數(shù)組長度； i， index
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟1: table為null或者 lenght等于 0 ，說明需要初始化，先擴(kuò)容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟2: 確定index，index上鏈表為null，就創(chuàng)建鏈表
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// index上鏈表不為 null，就說明index沖突，鏈表已存在
// 之后開始準(zhǔn)備遍歷鏈表，此時的p，是鏈表的頭，鏈表上的第一個元素
else {
Node<K,V> e; K k;
// 步驟3：將要存入的對象鍵值對，與p進(jìn)行比較
// 若相等，就說明需要將value進(jìn)行覆蓋，直接進(jìn)行覆蓋操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步驟4: p是否已轉(zhuǎn)為紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 此時，還為鏈表
else {
// 步驟5: 遍歷鏈表
for (int binCount = 0; ; ++binCount) {
// 在尾部節(jié)點(diǎn)添加要存入的目標(biāo)鍵值對
// 當(dāng)鏈表內(nèi)元素個數(shù)為8時，就將鏈表轉(zhuǎn)換為紅黑樹，并結(jié)束
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 存在覆蓋節(jié)點(diǎn)，結(jié)束循環(huán)，進(jìn)行覆蓋操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 此時，p.next 不為 null，沒有到鏈表尾部，并且覆蓋節(jié)點(diǎn)不存在
// 將e賦給p，進(jìn)行下一輪
p = e;
}
}
// 覆蓋操作
// e不 null， 說明上面有覆蓋節(jié)點(diǎn)，進(jìn)行了 e = p 操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// HashMap子類LinkedHashMap需要重寫的方法
afterNodeAccess(e);
return oldValue;
}
}
// 步驟6
// 此時，已經(jīng)成功存入目標(biāo)鍵值對，之后主要就是判斷是否需要擴(kuò)容
// 記錄HashMap結(jié)構(gòu)被改變次數(shù)
++modCount;
// 判斷是非需要進(jìn)行擴(kuò)容
// size 先加 1
if (++size > threshold)
resize();
// HashMap子類LinkedHashMap需要重寫的方法
afterNodeInsertion(evict);
// 返回 null
return null;
}
afterNodeAccess(e)和afterNodeInsertion(evict)這兩個方法先不用管，是為LinkedHashMap準(zhǔn)備的
modCount這個值是用來記錄HashMap內(nèi)結(jié)構(gòu)被改變的次數(shù)
HashMap不是線程安全的，在使用iterator進(jìn)行迭代時，通過這個值來判斷，如果修改了HashMap結(jié)構(gòu)，便會拋出異常
整個put()方法流程：
圖來美團(tuán)點(diǎn)評技術(shù)團(tuán)隊(duì) Java 8系列之重新認(rèn)識HashMap
2.5 擴(kuò)容
當(dāng)HashMap容量到達(dá)閾值時，再進(jìn)行put操作就會進(jìn)行擴(kuò)容操作
擴(kuò)容是1.8代碼改動比較大的地方，但原理是不變的。1.7更好理解，先看1.7中的實(shí)現(xiàn)
2.5.1 1.7版本
每次擴(kuò)容操作都是2倍
resize()
void resize(int newCapacity) {
// 將table賦給臨時的oldTable
Entry[] oldTable = table;
// 判斷當(dāng)前oldTable.length是否為 1 >> 30
// 是，就直接將閾值設(shè)置為最大容量
// 之后便不會再進(jìn)行擴(kuò)容
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 創(chuàng)建一個大小為newCapacity 的 Entry數(shù)組
Entry[] newTable = new Entry[newCapacity];
// 將 oldTable 數(shù)據(jù)裝進(jìn) newTable
transfer(newTable);
// 將新的數(shù)組賦給table
table = newTable;
// 修改為新的閾值
threshold = (int)(newCapacity * loadFactor);
}
transfer()
將數(shù)組鏈表中的元素裝進(jìn)新的擴(kuò)容后的鏈表數(shù)組
需要考慮的是，容量變大后，如何進(jìn)行稀釋元素
void transfer(Entry[] newTable) {
// 臨時 Entry 數(shù)組
Entry[] src = table;
// 新的容量
int newCapacity = newTable.length;
// 遍歷數(shù)組
for (int j = 0; j < src.length; j++) {
// 當(dāng)前index上的鏈表
Entry<K,V> e = src[j];
// 當(dāng)前index上有元素
if (e != null) {
// 釋放舊Entry數(shù)組的對象引用
src[j] = null;
// 遍歷鏈表
do {
// 臨時 next 鍵值對
Entry<K,V> next = e.next;
// 計算 e 新的index
int i = indexFor(e.hash, newCapacity);
// 進(jìn)行標(biāo)記，將e.next指向鏈表頭
// 這里是單鏈表的頭插法
// 新元素放在鏈表頭，舊元素放鏈表尾部
e.next = newTable[i];
// 將鍵值對e 放在鏈表數(shù)組 i 位置上的鏈表頭位置
newTable[i] = e;
// 進(jìn)行下一輪
e = next;
} while (e != null);
}
}
}
1.7的版本，遍歷鏈表，根據(jù)鏈表元素的key重新計算index，之后采用單鏈表的頭插法進(jìn)行擴(kuò)容后的鏈表填充操作
在進(jìn)行transfer操作時，對于一個e鍵值對對象來說，e.next指向的是newTable[i]，i位置上鏈表的頭
此時分2種情況，其實(shí)是一回事，感覺說2種情況更容易理解
當(dāng)newTable[i] == null時，也就是此index上的鏈表第一次放入鍵值對元素，此時，e.next就是為null了，e就作為此鏈表的尾部了，在單鏈表中，尾部節(jié)點(diǎn)的next為null
當(dāng)newTable[i] != null，說明index發(fā)生了沖突，也就是此index上的鏈表已經(jīng)存在元素了，e.next指向了newTable[i]，也就是指向了上次放入的鍵值對元素，之后newTable[i] = e
下面舉個例子說明下擴(kuò)容過程。假設(shè)了我們的hash算法就是簡單的用key進(jìn)行mod 一下表的大小，也就是數(shù)組的長度。其中哈希桶數(shù)組table[]的size=2， 所以key = 3、7、5，put順序依次為 5、7、3。在mod 2以后都沖突在table[1]這里了。這里假設(shè)負(fù)載因子loadFactor=1，即當(dāng)鍵值對的實(shí)際大小size 大于table的實(shí)際大小時進(jìn)行擴(kuò)容。接下來的三個步驟是哈希桶數(shù)組 resize成4，然后所有的Node重新rehash的過程
例子來美團(tuán)點(diǎn)評技術(shù)團(tuán)隊(duì) Java 8系列之重新認(rèn)識HashMap
2.5.2 1.8版本
1.8的版本在稀釋操作時，做了優(yōu)化
HashMap的初始化容量為16，擴(kuò)容是在之前的容量基礎(chǔ)上的2倍，最終一定還是2的n次方
擴(kuò)容后，元素的位置有兩種情況：原來的位置；原位置2次冪的位置
n為table.length，圖a表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例，圖b表示擴(kuò)容后key1和key2兩種key確定索引位置的示例
其中hash1是key1對應(yīng)的哈希與高位運(yùn)算結(jié)果
元素在重新計算hash之后，因?yàn)?code>n變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：
1.8中，并不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成原索引+oldCap
這樣既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket
在1.7中，擴(kuò)容時，往新鏈表插入數(shù)據(jù)時，使用的是頭插法，在產(chǎn)生hash沖突時，同一個index的元素，在新鏈表中會倒置。而1.8中，不會
摘抄自美團(tuán)點(diǎn)評技術(shù)團(tuán)隊(duì) Java 8系列之重新認(rèn)識HashMap
- 初始化
newCap，newThr，并確定resize()是初始化還是元素存放數(shù)到達(dá)了閾值 - 開始遍歷鏈表數(shù)組，判斷
index處是否有鏈表 - 遍歷每個鏈表
- 判斷鏈表內(nèi)是不是只有一個鍵值對
- 判斷鏈表是否轉(zhuǎn)位了紅黑樹
- 進(jìn)行鍵值對
稀釋操作，根據(jù)e.hash & oldCap，確定下標(biāo)是低位還是高位
final Node<K,V>[] resize() {
// 臨時oldTab數(shù)組
Node<K,V>[] oldTab = table;
// 舊的容量，初始化階段,在HashMap沒有放入鍵值對時為0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 舊的閾值
int oldThr = threshold;
// 初始化新的容量，新的閾值
int newCap, newThr = 0;
// 步驟1
// 舊的容量大于0
if (oldCap > 0) {
// 判斷是否已經(jīng)到了上限，無需再擴(kuò)容的容量
// 若到了，就將閾值直接設(shè)置為最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的容量大于默認(rèn)大小16，乘2后小于容量上限
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 閾值 2 倍
newThr = oldThr << 1;
}
// 此時容量oldCap = 0，鏈表數(shù)組table為null， 閾值大于0
// 說明，是使用了`new HashMap(cap，thr)`，指定了容量和閾值
else if (oldThr > 0)
// 將閾值設(shè)置為舊的閾值
newCap = oldThr;
// oldCap == 0 ， oldThr == 0，table為null，閾值也為0
// 說明是使用了`new HashMap()`
else {
// 將新的容量設(shè)置為默認(rèn)大小16
newCap = DEFAULT_INITIAL_CAPACITY;
// 默認(rèn)閾值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 此時對應(yīng)的是`new HashMap(cap，thr)`，指定了容量和閾值這種情況
if (newThr == 0) {
// 計算閾值
float ft = (float)newCap * loadFactor;
// 設(shè)置新的閾值
newThr = (newCap < MAXIMUM_CAPACITY
&&
ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
}
// 將獲取的newThr賦給threshold，也就是更新HashMap的閾值
threshold = newThr;
// 建立臨時鏈表數(shù)組
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 將新的鏈表數(shù)組引用指向table
table = newTab;
// 當(dāng)oldTab不為null時，之前有存放過鍵值對
// 遍歷
if (oldTab != null) {
// 步驟2
// 先遍歷鏈表數(shù)組
for (int j = 0; j < oldCap; ++j) {
// 臨時鍵值對
Node<K,V> e;
// 步驟3
// 若在 j 位置上，有鏈表
if ((e = oldTab[j]) != null) {
// 將 j 位置的鏈表引用釋放
oldTab[j] = null;
// 步驟4
// e.next 為 null
// 鏈表內(nèi)只有一個鍵值對
if (e.next == null)
// 根據(jù)新的容量進(jìn)行 & 運(yùn)算來計算 index
// 將 e 放在新計算的index位置
newTab[e.hash & (newCap - 1)] = e;
// 步驟5
// e 是否為 紅黑樹
// 此時，說明hash沖突，鏈表上有超過個鍵值對，轉(zhuǎn)換成了紅黑樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 鏈表上有鍵值對，但還沒超過8個
// 利用hash值來計算擴(kuò)容后鍵值對所出鏈表的位置
// 1.8 的優(yōu)化點(diǎn)：省去了一次重新計算index的過程
else {
// 步驟6
// 對于此時的 e 來說，擴(kuò)容后，有兩種情況：
// 放在原鏈表的原下標(biāo)處，也就是低位，low位
// 放在擴(kuò)容后的新下標(biāo)處，也就是高位，high位
// high 位= low位 + 原哈希桶容量
// 低位鏈表的頭結(jié)點(diǎn)、尾節(jié)點(diǎn)
Node<K,V> loHead = null, loTail = null;
// 高位鏈表的頭結(jié)點(diǎn)、尾節(jié)點(diǎn)
Node<K,V> hiHead = null, hiTail = null;
// e.next 臨時節(jié)點(diǎn)
Node<K,V> next;
do {
// 臨時節(jié)點(diǎn)賦值
next = e.next;
// e.hash & oldCap 計算 mask 范圍
// 結(jié)果可以分為: 等于0 大于0
// 等于0，位于原鏈表原下標(biāo)位置
// 大于0，位于擴(kuò)容后新鏈表high位
if ((e.hash & oldCap) == 0) {
// 尾節(jié)點(diǎn)為 null ，說明鏈表之前沒有存放過鍵值對
if (loTail == null)
// 賦值頭節(jié)點(diǎn)
loHead = e;
else
// 尾節(jié)點(diǎn)next 指為 e
// 尾節(jié)點(diǎn)的next 暫時為自身
loTail.next = e;
// 將e引用賦給尾節(jié)點(diǎn)
// 第一個元素插入時，由于只有一個節(jié)點(diǎn)
// 既是頭節(jié)點(diǎn)又是尾節(jié)點(diǎn)
loTail = e;
}
// 高位同上
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 低位節(jié)點(diǎn)存在
if (loTail != null) {
// 將尾節(jié)點(diǎn) next 置 null
loTail.next = null;
// 低位放在原index處
newTab[j] = loHead;
}
// 高位同上
if (hiTail != null) {
hiTail.next = null;
// 高位放在原 index+oldCap 處
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
關(guān)于e.hash & oldCap
在知乎看到了解釋：
jdk1.8 HashMap put時確定元素位置的方法與擴(kuò)容拷貝元素確定位置的方式?jīng)_突？
摘自上面的知乎鏈接
2.6 get()獲取
get()方法也是高頻使用的方法
public V get(Object key) {
Node<K,V> e;
// 先根據(jù) key 計算 hash 值
// 若不存在，就返回 null
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
getNode()
- 根據(jù)
hash和key快速定位目標(biāo)所在鏈表 - 判斷頭節(jié)點(diǎn)是否為獲取目標(biāo)。是，直接返回目標(biāo)
- 查看鏈表中是否還有其他節(jié)點(diǎn)；沒有直接返回
null - 判斷鏈表是否轉(zhuǎn)為
紅黑樹；是，就進(jìn)行遍歷紅黑樹查找操作 - 遍歷鏈表，查找目標(biāo)；找打就返回目標(biāo)，否則直接返回
null - 此時，說明
HashMap內(nèi)沒有查找的目標(biāo)，返回null
final Node<K,V> getNode(int hash, Object key) {
// 鏈表數(shù)組
Node<K,V>[] tab;
// 頭節(jié)點(diǎn)
Node<K,V> first, e;
// table.length
int n;
// 臨時健key
K k;
// 步驟1: 鏈表數(shù)組不為 null 并且能找打目標(biāo)鏈表
// 關(guān)鍵點(diǎn)在于 tab[(n - 1) & hash])，找到鏈表，確定頭節(jié)點(diǎn)
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 步驟2 ：判斷頭節(jié)點(diǎn)是否就是查找的目標(biāo)
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 步驟3: 鏈表中還有其他節(jié)點(diǎn)
// 說明此時頭節(jié)點(diǎn)不是獲取目標(biāo)
if ((e = first.next) != null) {
// 步驟4 ： 是否為紅黑樹
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 步驟5 ： 鏈表沒有被轉(zhuǎn)為紅黑樹
// 遍歷鏈表
do {
// 判斷是否為目標(biāo)
if (e.hash == hash &&((k = e.key) == key
|| (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 步驟6 ： 返回 null
return null;
}
獲取方法的流程倒是比put()簡單，關(guān)鍵點(diǎn)在于確定有效的頭節(jié)點(diǎn)
3. 最后
紅黑樹不會，以后單獨(dú)進(jìn)行學(xué)習(xí)，不過目前不影響HashMap整體的流程學(xué)習(xí)
引用較多，侵刪
有錯誤，請指出
共勉 : ）
