HashMap大家肯定非常的熟悉，HashMap底層其實就是一個數(shù)組亲澡，只不過數(shù)組的每一項都是一條鏈盲憎，也是面試中經(jīng)常喜歡問到的知識點，"請說下HashMap的工作原理"半夷，ememem.....其實面試官主要是想考察我們知其然還要知其所以然婆廊，所以我們不能一直停留在會用api，還要帶著問題去研究源碼巫橄。比如淘邻，為什么HashMap的鍵(key)和值(value)可以為null，而HashTable鍵和值確卻都不能為null湘换？如果兩個鍵的hashcode相同宾舅，會發(fā)生什么情況统阿？以及如何取到相應(yīng)的值？
為什么說要帶著問題看源碼呢筹我？因為這樣目的性更強效率更高扶平，漫無目的的看源碼會使你陷入其中而不能自拔，帶著問題看蔬蕊，點到為止结澄。下面就進入正題，首先先來一張自己畫的HashMap結(jié)構(gòu)草圖岸夯，大家將就著看吧概而，有助于理解
hashmap數(shù)據(jù)結(jié)構(gòu)圖.png
簡單的說明下，HashMap底層其實就是一個table數(shù)組囱修，只不過數(shù)組的每一項是由一條鏈組成的，而這每一條鏈表都是由若干個節(jié)點組成王悍，每一個節(jié)點就是一個Entry對象破镰，每一個Entry對象中存儲的是我們的key對象和value對象以及下一個節(jié)點next（鏈表中如果不止一個節(jié)點的話，那么前一個節(jié)點的next就會指向下一個節(jié)點）压储，由上圖可知鲜漩，假如有一條很長很長的鏈表分布在數(shù)組的某一項上面，如果我們想取某一個value值的話集惋，就需要遍歷數(shù)組i位置的這條鏈表孕似，所以如果這些鏈表都能均勻的分布到數(shù)組的每一項上，而不是像剛才那樣的話刮刑，我們?nèi)≈档乃俣染蜁旌芏嗪砑馈Ｆ鋵嵾@些在HashMap內(nèi)部都做了很好的優(yōu)化處理，接下來我們就一起來探究HashMap源碼雷绢，看看是如何優(yōu)化的泛烙。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
可以看到HashMap繼承自AbstractMap抽象類，實現(xiàn)了Map接口中的方法
接著看下HashMap的一些成員變量聲明
//默認的初始容量(必須是2的整數(shù)次冪)翘紊，jdk版本不同蔽氨，有的是16
static final int DEFAULT_INITIAL_CAPACITY = 4;
//最大容量(2的30次方)，如果配置的容量大于此值的話就會用此值替換
static final int MAXIMUM_CAPACITY = 1 << 30;
//加載因子(0.75是基于時間和空間的一種折中結(jié)果)帆疟，在擴容時起到關(guān)鍵作用
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空table數(shù)組（HashMap的底層其實就是一個鏈式數(shù)組）
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
//存儲數(shù)據(jù)的HashMapEntry數(shù)組(靜態(tài)內(nèi)部類HashMapEntry實現(xiàn)了Map.Entry<K,V>接口)
//table數(shù)組中存儲的就是一個個Entry鏈鹉究，Entry中存儲的就是一個個key-value鍵值對數(shù)據(jù)
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
//鍵值對的數(shù)量
transient int size;
//HashMap的閾值，用于判斷是否需要擴容(threshold = 容量*加載因子)
int threshold;
//加載因子實際大小
final float loadFactor = DEFAULT_LOAD_FACTOR;
//HashMap修改的次數(shù)
transient int modCount;
通常我們用到HashMap的時候需要去new HashMap()踪宠；那么我們就從HashMap的構(gòu)造方法開始查看
//傳入容量值自赔、加載因子
public HashMap(int initialCapacity, float loadFactor) {
//容量值不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果設(shè)置的容量值大于HashMap允許的最大容量，糾正并將HashMap允許的最大值賦值給他
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
//同理如果小于HashMap的默認初始容量大小的話柳琢，就將默認值賦值給他
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
//加載因子不能小于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
//在部分版本上這個閾值等于容量*加載因子
threshold = initialCapacity;
init();
}
//一個參的構(gòu)造方法匿级，加載因子用HashMap默認的
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//無參的構(gòu)造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//將子map傳進來蟋滴，如果m為null的話會報空指針錯誤
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
//創(chuàng)建鏈表數(shù)組
inflateTable(threshold);
//將m中的key-value鍵值對都添加到HashMap數(shù)組中
putAllForCreate(m);
}
這里要特別說明的是，HashMap鏈表數(shù)組中存儲的是鍵值對(key對象和value對象)痘绎，而不是只存儲value或者key
接下來分析下HashMap是如何存取的
存
public V put(K key, V value) {
//先判斷當前鏈表數(shù)組是否為空數(shù)組津函，是則調(diào)用inflateTable方法創(chuàng)建一個數(shù)組
if (table == EMPTY_TABLE) {
//此方法中通過table = new HashMapEntry[capacity]創(chuàng)建一個數(shù)組
inflateTable(threshold);
}
//如果key是null的話，會調(diào)用putForNullKey方法孤页，將值存放到table數(shù)組的第0項位置處尔苦，即第一個桶中
if (key == null)
return putForNullKey(value);
//根據(jù)key的hashcode計算出hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//通過hash值計算出此條鍵值對在桶中的位置
int i = indexFor(hash, table.length);
//HashMapEntry是單鏈表結(jié)構(gòu)，e.next查找下一個節(jié)點數(shù)據(jù)
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//遍歷行施，如果key相同允坚，那么就將此key的新value值覆蓋舊value值，并直接返回舊value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//走到這一步說明添加到數(shù)組中的鍵值對的key不相同蛾号，那么就將此鍵值對數(shù)據(jù)添加到數(shù)組的i位置
addEntry(hash, key, value, i);
return null;
}
通過對key==null的處理稠项，我們看下putForNullKey(value)方法
//從此方法中我們可以得到兩點關(guān)鍵信息
private V putForNullKey(V value) {
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
//1、由下面第二點注釋可知鲜结，key為null的鍵值對數(shù)據(jù)是都存儲在table[0]位置的
//2展运、程序能夠進入這個if (e.key == null)判斷中，說明table[0]位置已經(jīng)存在了key為null的鍵值對數(shù)據(jù)
//所以精刷，遍歷table[0]如果此位置已經(jīng)有key為null的value數(shù)據(jù)了拗胜，那么就將新value值覆蓋舊value值，并將舊value值返回
//同時還能得出HashMap的key是唯一的怒允，相同的key對應(yīng)的鍵值對會被覆蓋
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//2埂软、如果key為null的話，并且之前table[0]位置還沒有存儲key為null的鍵值對數(shù)據(jù)時纫事，會將此鍵值對添加到table[0]位置
addEntry(0, null, value, 0);
return null;
}
接下來我們再看下如果我們在存儲時key為null和key不為null兩種情況下是如何將這個鍵值對存儲到鏈表數(shù)組中的
//key為null的情況勘畔，并且是第一次存儲時
//由上面分析已經(jīng)知道key=null時位于table[0]位置，所以bucketIndex為0丽惶，他的hash值也為0
addEntry(0, null, value, 0);
//要存儲的key不為null的情況
addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) {
//首先在put存儲key-value對象時咖杂，要判斷當前數(shù)組中存儲的key-value對象數(shù)量是否達到了HashMap的閾值，
//超過閾值則需要對HashMap進行擴容
if ((size >= threshold) && (null != table[bucketIndex])) {
//對HashMap進行擴容蚊夫，重新調(diào)整他的容量
resize(2 * table.length);
//key為null的話那么hash值為0诉字；
//key不為null的話，由于擴容了知纷，所以需要重新根據(jù)key的hashcode值去計算hash值
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
//通過hash值計算出此條key-value對象在table數(shù)組中的位置索引
//因為進行了擴容壤圃，所以需要重新確定bucketIndex
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
HashMap的擴容
接著我們看下resize方法
void resize(int newCapacity) {
//舊HashMap
HashMapEntry[] oldTable = table;
//舊HashMap的容量
int oldCapacity = oldTable.length;
//在擴容前需要進行判斷，
//如果舊HashMap的容量已經(jīng)達到最大要求值琅轧，則不能再擴容伍绳，直接返回，同時將閾值設(shè)置為Integer.MAX_VALUE
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根據(jù)擴容要求的容量大小new一個新的HashMap
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
//下面會介紹
transfer(newTable);
//并將新HashMap賦值給舊HashMap
table = newTable;
//閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
看下這個transfer方法
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
//主要操作就是循環(huán)遍歷舊HashMap乍桂，取出一個個key-value對象并存儲到擴容之后的新HashMap中
//由此可見擴容是耗性能的冲杀，所以如果我們知道要存儲的數(shù)量大致數(shù)量的話效床，在new這個HashMap的時候就給他一個合適的容量，
//這樣也就避免了擴容权谁，降低了性能的損耗
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
上面我們分析了HashMap是如何進行擴容的剩檀，以及擴容需要注意和優(yōu)化的知識點，接下來繼續(xù)看createEntry方法
void createEntry(int hash, K key, V value, int bucketIndex) {
//將table數(shù)組的bucketIndex位置的值賦給e鏈表
HashMapEntry<K,V> e = table[bucketIndex];
//1旺芽、將key-value鍵值對數(shù)據(jù)插入到新new的Entry鏈表中
//2沪猴、再將這個存儲了新鍵值對的HashMapEntry存儲到table數(shù)組的bucketIndex處
//3、設(shè)置e指向下一個節(jié)點(新插入的鍵值對都是存儲在鏈表的頭部的)
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
//put一條鍵值對數(shù)據(jù)之后采章，鍵值對數(shù)量就+1
size++;
}
取
public V get(Object key) {
//取key為null的value值运嗜，上面分析已經(jīng)知道，key為null時悯舟，key-value是存儲在table[0]位置
//getForNullKey()方法就是循環(huán)遍歷table[0]位置找到key為null時對應(yīng)的value值
if (key == null)
return getForNullKey();
//key不為null時
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
下面把getForNullKey()方法和getEntry(key)方法也貼出來分析下
//這個方法在上面取值方法中已經(jīng)簡單分析過了
private V getForNullKey() {
if (size == 0) {
return null;
}
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//日式走到這個方法時担租，key是不為null的，不明白這里為什么還要對key是否為null進行判斷抵怎？奋救？
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//根據(jù)key的hashcode計算出hash值，再根據(jù)hash值就可以計算出在table數(shù)組中的哪一個位置
//得到table在這個位置處的HashMapEntry鏈表便贵，循環(huán)遍歷鏈表中的節(jié)點
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
到此，對于HashMap如何存儲冗荸、擴容承璃、以及取值等進行了詳細的分析，基于jdk版本的不同蚌本，可能源碼也不相同盔粹，例如，最新的HashMap源碼中是通過樹來進行存儲的程癌，我也是分析完之后發(fā)現(xiàn)并不是最新的源碼舷嗡，所以，以后有時間再對最新的HashMap源碼進行分析吧嵌莉，如有分析不對的地方进萄，還望各位老鐵指正
