學(xué)習(xí)資料腔召；
- 《Java程序性能優(yōu)化》
- 美團點評技術(shù)團隊 Java 8系列之重新認識HashMap
- 張旭童大佬 面試必備：HashMap源碼解析（JDK8）
這篇筆記是第二次整理，第一次是16年11月份，只是之前能寫出來的太少件余，中途而廢。最近又來看HashMap的東西竖伯，比上次看時理解的東西多了些蜡镶，就重新整理下
目前，HashMap內(nèi)械巡，還是有很多問題刹淌，不明白，以后會再做補充
重點學(xué)習(xí)HashMap讥耗，本篇學(xué)習(xí)筆記有勾，會有很多錯誤，請指出
1. Map接口
實現(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)點特性就是高性能菲宴，存放和查詢是很高效的，缺點就是無序性趋急，存入的元素喝峦，在遍歷時是無序的
LinkedHashMap繼承自HashMap，除了具備HashMap高性能優(yōu)點外呜达，還具有有序性谣蠢。LinkedHashMap在HashMap的基礎(chǔ)上，增加了一個鏈表來存放元素的順序
LinkedHashMap可以簡單理解為一個維護了元素次序表的HashMap
LinkedHashMap提供了兩種類型的順序：存放(插入)元素時的順序查近，最近訪問順序
可以使用3個參數(shù)的構(gòu)造方法來指定排序行為
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
accessOrder為true時眉踱，按照元素最后訪問時間來排序，默認情況下為false
當為true時霜威，使用get()執(zhí)行來一次獲取操作時谈喳，當前元素會被挪到整個LinkedHashMap最末尾位置
需要注意的是，當設(shè)置accessOrder為true時戈泼，不能用于Iterator遍歷
不要在迭代器模式中修改被迭代的集合
TreeMap實現(xiàn)了SortMap接口婿禽，可以對元素進行排序
TreeMap排序是指根據(jù)條件對存入的key進行按照規(guī)則進行了排序赏僧，是基于元素本身的固有順序。而LinkedHashMap只是基于元素進入集合的順序或者訪問的先后順序進行排序
TreeMap為了確定key的排序扭倾，可以通過兩種方式來指定
- 通過
TreeMap的構(gòu)造方法淀零，public TreeMap(Comparator<? super K> comparator)，指定一個Comparator - 使用一個自身實現(xiàn)了
Comparable接口的key
TreeMap內(nèi)部實現(xiàn)是基于紅黑樹膛壹。紅黑樹是一種平衡查找樹驾中，統(tǒng)計性能要優(yōu)于平衡二叉樹。具有良好的最壞情況運行時間恢筝，可以在O(log n)時間內(nèi)做查找哀卫、插入和刪除，其中n代表樹中元素的數(shù)目
詳細可以看HashMap撬槽、Hashtable此改、HashSet 和 ConcurrentHashMap 的比較
2. JDK1.8中的HashMap
在之前學(xué)習(xí)時，寫過一個Java基礎(chǔ)學(xué)習(xí)——HashMap原理學(xué)習(xí)侄柔，可以幫助理解原理學(xué)習(xí)
個人理解共啃，舉例：
一家超大型購物商場，擁有一百萬種不同品牌的商品
假如暂题，當世界上第一家這樣規(guī)模的大型商場開業(yè)時移剪，由于沒啥經(jīng)驗，商場的工作人員從倉庫取出商品擺放時薪者，從商場門口開始纵苛，在倉庫拿到啥就開始擺放啥，也不管物品是啥言津，只要能放得下攻人，就依次擺放。而等到顧客來買東西時悬槽，全靠隨緣怀吻。除非打5折，否則一年也賣不出多少東西
現(xiàn)實這種情況根本不會發(fā)生初婆，為了方便顧客快速定位商品的相對準確位置蓬坡，會 根據(jù)商品的固有屬性來分區(qū)
例如，我最愛的農(nóng)夫山泉磅叛，就會放在一個飲品區(qū)屑咳，和各種純凈水以及其他的喝的，擺在一個相對集中的區(qū)域弊琴。我到了一家從來沒有去過的大型商場去買農(nóng)夫山泉乔宿， 購買效率很大程度取決于我用了多久找到農(nóng)夫山泉所在的飲品區(qū)，到了飲品區(qū)访雪，再快速定位到純凈水貨架详瑞。實際生活中，一般情況下臣缀，即使很大型的商場坝橡，也可以比較快速的買到一瓶
確定飲水區(qū)的過程可以看作為HashMap中涉及hash操作的整個過程
圖來自美團技術(shù)點評 Java 8系列之重新認識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點：
-
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());
本次重點學(xué)習(xí)存放put()，擴容resize()
2.1 構(gòu)造方法
有 4 個 構(gòu)造方法杉适，最經(jīng)常使用的是空參的
public HashMap()-
public HashMap(int initialCapacity)谎倔，指定容量 -
public HashMap(int initialCapacity, float loadFactor)，指定容量猿推、負載因子 -
public HashMap(Map<? extends K, ? extends V> m)片习，存放另一個HashMap
/**
* The default initial capacity - MUST be a power of two.
* 默認大小
*
* 使用空參構(gòu)造方法時掷伙，默認初始化大小 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
* 默認負載因子
*
* 默認情況下的加載因子掸茅，可以通過構(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è)計的目的在于
* 擴容時秽五，更加高效的統(tǒng)計數(shù)組的index孽查，用位運算替代取余操作
*/
transient Node<K,V>[] table;
/**
* Constructs an empty HashMap with the default initialcapacity
* (16) and the default load factor (0.75).
*
* 空構(gòu)造方法：初始化 負載因子(loadFactor)為 0.75
* 此時，默認容量大小為 16坦喘，閾值就是 12
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
使用空參構(gòu)造方法時盲再，指定loadFactor為默認值0.75
負載因子是0 ～ 1之間的浮點數(shù)西设，決定了在擴容之前，HashMap的內(nèi)部數(shù)組鏈表的填充度
閾值(threshold) = 容量(capacity) * 負載因子(load factor)
當HashMap的實際容量超過閾值時答朋，HashMap便會擴容贷揽。因此，實際上HashMap的實際填充率不會超過負載因子
負載因子也可以設(shè)置為1或者大于1梦碗，但此時會導(dǎo)致大量的hash沖突
負載因子越大禽绪，使用越少的內(nèi)存空間，而一個數(shù)組索引位置上的鏈表長度就越大洪规，一個鏈表中存放的元素越多印屁，越容易引起hash值沖突。使用get()方法進行獲取元素操作斩例，進行遍歷鏈表時的效率也就越低
相反雄人，負載因子越小，一個數(shù)組索引位置上的鏈表樱拴，長度越小柠衍，一個鏈表中存放的元素越少，雖然遍歷的效率高了晶乔，但也就浪費了較多空間
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()
當使用put()方法存放一個元素時，首先會根據(jù)key計算hash值，之后利用hash值鳞尔，確定該元素所屬鏈表的索引index嬉橙。也就說這個兩步走，在put()中是必須要走的
JDK1.8中對計算索引兩步走又進行了優(yōu)化,先了解1.7的實現(xiàn)
2.3.1 在JDK1.7中的實現(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;
//這個特殊選項先不去管它
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).
//初始哈希值做進一步優(yōu)化（注：^為“異或”操作）
//異或：每一位上的值相同返回0，不同返回1级及。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
調(diào)用key類型自帶的hashCode()函數(shù)乒疏，計算原始哈希值
在最后計算hash值時，用了4次^運算饮焦，1.8中做的優(yōu)化便是由4次變做了1次
又看到了這篇：HashMap hash方法分析
看懂似懂非懂的
這里原理為啥這么寫的怕吴，先不管了，先記結(jié)論
結(jié)論:
無論1.X的JDK县踢，這個hash()方法的優(yōu)化目的都是為了防止Object key自身的hashCode()方法實現(xiàn)比較差转绷，為了使hash值更加均衡，減少hash沖突
兩步走硼啤，第二步议经，計算索引值
indexFor()的目的是為計算index，在買農(nóng)夫山泉的例子中谴返，就是快速定位飲品區(qū)煞肾，然后可以快速找到農(nóng)夫山泉貨架這個步驟
實際生活中，超市不會一個貨架只擺放一瓶農(nóng)夫山泉嗓袱。在元素多時籍救，HashMap也不會一個鏈表只存放一個元素
HashMap的最大容量是Integer.MAX_VALUE，但table.length一定不會是這么大渠抹。若一個元素占用一個鏈表蝙昙，那需要一個容量為2 ^ 31 - 1的數(shù)組，這樣雖然index不會存在沖突逼肯，但空間上是不允許的
計算這樣一個index首先想到的便是除法散列法
// 求模數(shù)實際是通過一個除法運算得到
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)運算等價于對length取模，也就是h%length，但&具有更高的效率
這也是為啥要將table.lenth設(shè)計為總是2的n次方原因
2的n次方缺菌，必然是偶數(shù)葫辐，length -1 為奇數(shù)，轉(zhuǎn)換成二進制之后伴郁，最后一位為1
當h & (length-1)時耿战，最后一位的是0還是1，就取決于h的值焊傅，也就是說index的奇偶性取決于h
假如length不一定是2的n次方剂陡，當length為奇數(shù)時，length-1轉(zhuǎn)換成二進制后狐胎，最后一位是0鸭栖，這樣無論h為多少，h & (length-1)時握巢，最后一位的都是0晕鹊，這樣index都是偶數(shù)，數(shù)組只有偶數(shù)索引處有值暴浦，也就造成了空間浪費
結(jié)論：
h & (length-1)既高效又能使index分布均勻
2.3.2 1.8中的實現(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);
}
只進行了一次^運算循狰，h值自身的高16位 和 低16位進行^運算
混合原始哈希碼的高位和低位，以此來加大低位的隨機性券勺。而且混合后的低位摻雜了高位的部分特征绪钥，這樣高位的信息也被變相保留下來
這也彌補了取余時只有低位參與運算，而導(dǎo)致hash沖突變多的情況
這么做可以在數(shù)組table的length比較小的時候关炼，也能保證考慮到高低Bit都參與到Hash的計算中程腹，同時不會有太大的開銷
圖來自美團技術(shù)點評 Java 8系列之重新認識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);
}
當key已經(jīng)存在的情況下社痛，會將舊的value替換见转，并返回舊的value
putVal()
- 判斷
HashMap內(nèi)的鏈表數(shù)組table是否已經(jīng)創(chuàng)建過，也就是判斷是否為初始化狀態(tài) - 確定
index蒜哀，判斷數(shù)組index位置上是否有鏈表斩箫，沒有就創(chuàng)建，有就準備遍歷 - 判斷鏈表上第一元素鍵值對是否和要存入的目標鍵值對相等;相等就直接進行覆蓋操作
- 判斷鏈表是否已轉(zhuǎn)為紅黑樹
- 遍歷鏈表，過程中確定是否進行轉(zhuǎn)換紅黑樹操作乘客，以及根據(jù)目標鍵值對確定是加到鏈表尾部還是覆蓋操作
-
put目標鍵值對成功狐血，++size，判斷是否需要擴容易核，并返回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é)點弦追，臨時鍵值對
// n，臨時數(shù)組長度花竞； i， index
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟1: table為null或者 lenght等于 0 掸哑，說明需要初始化约急，先擴容
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沖突，鏈表已存在
// 之后開始準備遍歷鏈表摔癣，此時的p奴饮，是鏈表的頭，鏈表上的第一個元素
else {
Node<K,V> e; K k;
// 步驟3：將要存入的對象鍵值對择浊，與p進行比較
// 若相等戴卜，就說明需要將value進行覆蓋，直接進行覆蓋操作
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é)點添加要存入的目標鍵值對
// 當鏈表內(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é)點担孔，結(jié)束循環(huán)江锨，進行覆蓋操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 此時，p.next 不為 null糕篇，沒有到鏈表尾部啄育，并且覆蓋節(jié)點不存在
// 將e賦給p，進行下一輪
p = e;
}
}
// 覆蓋操作
// e不 null拌消， 說明上面有覆蓋節(jié)點挑豌，進行了 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)成功存入目標鍵值對，之后主要就是判斷是否需要擴容
// 記錄HashMap結(jié)構(gòu)被改變次數(shù)
++modCount;
// 判斷是非需要進行擴容
// size 先加 1
if (++size > threshold)
resize();
// HashMap子類LinkedHashMap需要重寫的方法
afterNodeInsertion(evict);
// 返回 null
return null;
}
afterNodeAccess(e)和afterNodeInsertion(evict)這兩個方法先不用管浮毯，是為LinkedHashMap準備的
modCount這個值是用來記錄HashMap內(nèi)結(jié)構(gòu)被改變的次數(shù)
HashMap不是線程安全的完疫，在使用iterator進行迭代時，通過這個值來判斷债蓝，如果修改了HashMap結(jié)構(gòu)壳鹤，便會拋出異常
整個put()方法流程：
圖來美團點評技術(shù)團隊 Java 8系列之重新認識HashMap
2.5 擴容
當HashMap容量到達閾值時，再進行put操作就會進行擴容操作
擴容是1.8代碼改動比較大的地方饰迹，但原理是不變的芳誓。1.7更好理解，先看1.7中的實現(xiàn)
2.5.1 1.7版本
每次擴容操作都是2倍
resize()
void resize(int newCapacity) {
// 將table賦給臨時的oldTable
Entry[] oldTable = table;
// 判斷當前oldTable.length是否為 1 >> 30
// 是啊鸭，就直接將閾值設(shè)置為最大容量
// 之后便不會再進行擴容
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ù)裝進 newTable
transfer(newTable);
// 將新的數(shù)組賦給table
table = newTable;
// 修改為新的閾值
threshold = (int)(newCapacity * loadFactor);
}
transfer()
將數(shù)組鏈表中的元素裝進新的擴容后的鏈表數(shù)組
需要考慮的是锹淌，容量變大后，如何進行稀釋元素
void transfer(Entry[] newTable) {
// 臨時 Entry 數(shù)組
Entry[] src = table;
// 新的容量
int newCapacity = newTable.length;
// 遍歷數(shù)組
for (int j = 0; j < src.length; j++) {
// 當前index上的鏈表
Entry<K,V> e = src[j];
// 當前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);
// 進行標記赠制，將e.next指向鏈表頭
// 這里是單鏈表的頭插法
// 新元素放在鏈表頭赂摆，舊元素放鏈表尾部
e.next = newTable[i];
// 將鍵值對e 放在鏈表數(shù)組 i 位置上的鏈表頭位置
newTable[i] = e;
// 進行下一輪
e = next;
} while (e != null);
}
}
}
1.7的版本，遍歷鏈表钟些，根據(jù)鏈表元素的key重新計算index烟号，之后采用單鏈表的頭插法進行擴容后的鏈表填充操作
在進行transfer操作時，對于一個e鍵值對對象來說政恍，e.next指向的是newTable[i]汪拥，i位置上鏈表的頭
此時分2種情況，其實是一回事篙耗，感覺說2種情況更容易理解
當newTable[i] == null時迫筑，也就是此index上的鏈表第一次放入鍵值對元素，此時宗弯，e.next就是為null了脯燃，e就作為此鏈表的尾部了，在單鏈表中罕伯，尾部節(jié)點的next為null
當newTable[i] != null曲伊，說明index發(fā)生了沖突，也就是此index上的鏈表已經(jīng)存在元素了追他，e.next指向了newTable[i]坟募，也就是指向了上次放入的鍵值對元素，之后newTable[i] = e
下面舉個例子說明下擴容過程邑狸。假設(shè)了我們的hash算法就是簡單的用key進行mod 一下表的大小懈糯，也就是數(shù)組的長度。其中哈希桶數(shù)組table[]的size=2单雾， 所以key = 3赚哗、7她紫、5，put順序依次為 5屿储、7贿讹、3。在mod 2以后都沖突在table[1]這里了够掠。這里假設(shè)負載因子loadFactor=1民褂，即當鍵值對的實際大小size 大于table的實際大小時進行擴容。接下來的三個步驟是哈希桶數(shù)組 resize成4疯潭，然后所有的Node重新rehash的過程
例子來美團點評技術(shù)團隊 Java 8系列之重新認識HashMap
2.5.2 1.8版本
1.8的版本在稀釋操作時赊堪，做了優(yōu)化
HashMap的初始化容量為16，擴容是在之前的容量基礎(chǔ)上的2倍竖哩，最終一定還是2的n次方
擴容后哭廉，元素的位置有兩種情況：原來的位置；原位置2次冪的位置
n為table.length相叁，圖a表示擴容前的key1和key2兩種key確定索引位置的示例遵绰，圖b表示擴容后key1和key2兩種key確定索引位置的示例
其中hash1是key1對應(yīng)的哈希與高位運算結(jié)果
元素在重新計算hash之后，因為n變?yōu)?倍增淹，那么n-1的mask范圍在高位多1bit(紅色)街立，因此新的index就會發(fā)生這樣的變化：
1.8中，并不需要重新計算hash埠通，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變逛犹，是1的話索引變成原索引+oldCap
這樣既省去了重新計算hash值的時間端辱，而且同時，由于新增的1bit是0還是1可以認為是隨機的虽画，因此resize的過程舞蔽，均勻的把之前的沖突的節(jié)點分散到新的bucket
在1.7中，擴容時码撰，往新鏈表插入數(shù)據(jù)時渗柿，使用的是頭插法，在產(chǎn)生hash沖突時脖岛，同一個index的元素朵栖，在新鏈表中會倒置。而1.8中柴梆，不會
摘抄自美團點評技術(shù)團隊 Java 8系列之重新認識HashMap
- 初始化
newCap陨溅，newThr，并確定resize()是初始化還是元素存放數(shù)到達了閾值 - 開始遍歷鏈表數(shù)組绍在，判斷
index處是否有鏈表 - 遍歷每個鏈表
- 判斷鏈表內(nèi)是不是只有一個鍵值對
- 判斷鏈表是否轉(zhuǎn)位了紅黑樹
- 進行鍵值對
稀釋操作门扇，根據(jù)e.hash & oldCap雹有，確定下標是低位還是高位
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)到了上限霸奕，無需再擴容的容量
// 若到了，就將閾值直接設(shè)置為最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的容量大于默認大小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è)置為默認大小16
newCap = DEFAULT_INITIAL_CAPACITY;
// 默認閾值
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;
// 當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ù)新的容量進行 & 運算來計算 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值來計算擴容后鍵值對所出鏈表的位置
// 1.8 的優(yōu)化點：省去了一次重新計算index的過程
else {
// 步驟6
// 對于此時的 e 來說桶蝎，擴容后驻仅，有兩種情況：
// 放在原鏈表的原下標處，也就是低位登渣，low位
// 放在擴容后的新下標處噪服，也就是高位，high位
// high 位= low位 + 原哈希桶容量
// 低位鏈表的頭結(jié)點胜茧、尾節(jié)點
Node<K,V> loHead = null, loTail = null;
// 高位鏈表的頭結(jié)點粘优、尾節(jié)點
Node<K,V> hiHead = null, hiTail = null;
// e.next 臨時節(jié)點
Node<K,V> next;
do {
// 臨時節(jié)點賦值
next = e.next;
// e.hash & oldCap 計算 mask 范圍
// 結(jié)果可以分為: 等于0 大于0
// 等于0，位于原鏈表原下標位置
// 大于0呻顽，位于擴容后新鏈表high位
if ((e.hash & oldCap) == 0) {
// 尾節(jié)點為 null 雹顺，說明鏈表之前沒有存放過鍵值對
if (loTail == null)
// 賦值頭節(jié)點
loHead = e;
else
// 尾節(jié)點next 指為 e
// 尾節(jié)點的next 暫時為自身
loTail.next = e;
// 將e引用賦給尾節(jié)點
// 第一個元素插入時，由于只有一個節(jié)點
// 既是頭節(jié)點又是尾節(jié)點
loTail = e;
}
// 高位同上
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 低位節(jié)點存在
if (loTail != null) {
// 將尾節(jié)點 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時確定元素位置的方法與擴容拷貝元素確定位置的方式?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快速定位目標所在鏈表 - 判斷頭節(jié)點是否為獲取目標。是昧碉，直接返回目標
- 查看鏈表中是否還有其他節(jié)點英染；沒有直接返回
null - 判斷鏈表是否轉(zhuǎn)為
紅黑樹揽惹；是，就進行遍歷紅黑樹查找操作 - 遍歷鏈表四康，查找目標搪搏；找打就返回目標，否則直接返回
null - 此時闪金，說明
HashMap內(nèi)沒有查找的目標疯溺，返回null
final Node<K,V> getNode(int hash, Object key) {
// 鏈表數(shù)組
Node<K,V>[] tab;
// 頭節(jié)點
Node<K,V> first, e;
// table.length
int n;
// 臨時健key
K k;
// 步驟1: 鏈表數(shù)組不為 null 并且能找打目標鏈表
// 關(guān)鍵點在于 tab[(n - 1) & hash])，找到鏈表哎垦，確定頭節(jié)點
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 步驟2 ：判斷頭節(jié)點是否就是查找的目標
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 步驟3: 鏈表中還有其他節(jié)點
// 說明此時頭節(jié)點不是獲取目標
if ((e = first.next) != null) {
// 步驟4 ： 是否為紅黑樹
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 步驟5 ： 鏈表沒有被轉(zhuǎn)為紅黑樹
// 遍歷鏈表
do {
// 判斷是否為目標
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)鍵點在于確定有效的頭節(jié)點
3. 最后
紅黑樹不會，以后單獨進行學(xué)習(xí)漏设，不過目前不影響HashMap整體的流程學(xué)習(xí)
引用較多墨闲，侵刪
有錯誤，請指出
共勉 : ）
