簡(jiǎn)介
HashMap是一個(gè)比較常用的鍵值對(duì)集合，在開(kāi)發(fā)中常用于映射關(guān)系。以下分析是基于Android中API25下的源碼
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
HashMap屬于map族類，并且默認(rèn)實(shí)現(xiàn)Serializable，可用于網(wǎng)絡(luò)傳輸和本地序列化。
基礎(chǔ)屬性
/**
* HashMap的默認(rèn)初始容量，必須是2的倍數(shù)
*/
static final int DEFAULT_INITIAL_CAPACITY = 4;
/**
* HashMap的最大容量，必須為2的倍數(shù)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)的擴(kuò)容因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* HashMap為空時(shí)候共享的空數(shù)組
*/
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
/**
* HashMap里面的存儲(chǔ)數(shù)組
* 每一個(gè)數(shù)據(jù)都是一個(gè)HashMapEntry，而HashMapEntry本質(zhì)上是一個(gè)單項(xiàng)鏈表
*/
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
/**
* HashMap中鍵值對(duì)的數(shù)量
*/
transient int size;
/**
* 臨界值決定什么時(shí)候進(jìn)行擴(kuò)容(當(dāng)前容量 * 擴(kuò)容因子)
*/
int threshold;
/**
* 擴(kuò)容因子，一個(gè)比例，相對(duì)于當(dāng)前容量來(lái)說(shuō)
* Android中只會(huì)使用0.75，而會(huì)忽視其它的數(shù)值
*/
final float loadFactor = DEFAULT_LOAD_FACTOR;
這里可以看到HashMap的基礎(chǔ)存儲(chǔ)結(jié)構(gòu)：
存儲(chǔ)結(jié)構(gòu)
后面會(huì)詳細(xì)看到具體的意義。
構(gòu)造
/**
* 創(chuàng)建一個(gè)空的HashMap
*
* @param initialCapacity 初始化容量
* @param loadFactor 擴(kuò)容因子，在Android中實(shí)際上并沒(méi)有用，還是采用默認(rèn)的0.75f
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//容量不能小于默認(rèn)容量和大于最大容量
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;//1 << 30
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;//4
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 實(shí)際上每次擴(kuò)容的時(shí)候threshold都會(huì)重新計(jì)算
threshold = initialCapacity;
init();//默認(rèn)空實(shí)現(xiàn)，子類可以嘗試實(shí)現(xiàn)這個(gè)方法做一些插入之類的操作
}
/**
* 創(chuàng)建一個(gè)空的HashMap，容量為4，擴(kuò)容因子0.75
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 從其它的HashMap上面復(fù)制一份
*
* @param m 想要復(fù)制的HashMap
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
/**
* 當(dāng)HashMap為空的時(shí)候初始化當(dāng)前HashMap
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
//下一次擴(kuò)容的大小為當(dāng)前容量*擴(kuò)容因子
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];//構(gòu)建一個(gè)容量大小的數(shù)組
}
/**
* 找到一個(gè)比number大的2的倍數(shù)
*/
private static int roundUpToPowerOf2(int number) {
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
/*稍微拆解一下方便理解
if(number >= MAXIMUM_CAPACITY){
rounded = MAXIMUM_CAPACITY;//不允許超過(guò)最大容量
}else{
//首先將number轉(zhuǎn)為2進(jìn)制表現(xiàn)形式，比方說(shuō)00100101
//通過(guò)highestOneBit則rounded為00100000
//找出最高位的1，其余位樸0
rounded = Integer.highestOneBit(number);
if(rounded != 0){
//如果number的2進(jìn)制中不止1個(gè)1,比方說(shuō)00100101
//因?yàn)閔ighestOneBit其余位樸0，得到rounded為00100000
//所以獲得要大于number的2的倍數(shù)，需要再乘以2，則rounded左移一位即可
rounded = ((Integer.bitCount(number) > 1) ? rounded << 1 : rounded);
}else{//如果number為0，容量取1即可
rounded = 1;
}
}*/
return rounded;
}
/**
* 將指定map的數(shù)據(jù)放入當(dāng)前HashMap中
* @param m 需要添加的數(shù)據(jù)
*/
private void putAllForCreate(Map<? extends K, ? extends V> m) {
//實(shí)際上就是遍歷一遍指定map，然后一個(gè)個(gè)添加到當(dāng)前HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
/**
* 該方法不會(huì)重新進(jìn)行擴(kuò)容操作
* 只有在構(gòu)造的時(shí)候復(fù)制map之類的場(chǎng)景下才會(huì)使用
*/
private void putForCreate(K key, V value) {
//計(jì)算key的hash值
int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//計(jì)算出當(dāng)前key在table的下標(biāo)
int i = indexFor(hash, table.length);
//下標(biāo)已經(jīng)計(jì)算成功
//在當(dāng)前table的鏈表中先查找是否有相同key的元素，有的話直接設(shè)置，不新建
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {//遍歷單向鏈表
Object k;
//key的hash值相同
//key是同一個(gè)引用或者key的equals相同
//此時(shí)直接復(fù)寫(xiě)value即可
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//當(dāng)前table的鏈表中沒(méi)有當(dāng)前key，在鏈表當(dāng)中新建一個(gè)節(jié)點(diǎn)
createEntry(hash, key, value, i);
}
/**
* 通過(guò)key的hash值和當(dāng)前HashMap的容量
* 計(jì)算出當(dāng)前node在table中的下標(biāo)
*/
static int indexFor(int h, int length) {
//假設(shè)h:0000 1110 length:0000 1000
//0000 1110 h
//0000 0111 length - 1，剛好將前面的所有位樸1
//0000 0110 結(jié)果
//結(jié)果必然是小于length
//而且從這個(gè)計(jì)算也知道，length必須是2的倍數(shù)
return h & (length-1);
}
/**
* 在指定的鏈表末尾添加一個(gè)節(jié)點(diǎn)
* @param hash 當(dāng)前要添加節(jié)點(diǎn)的key的hash值
* @param key 當(dāng)前要添加的節(jié)點(diǎn)的key
* @param value 當(dāng)前要添加的節(jié)點(diǎn)的value
* @param bucketIndex 當(dāng)前鏈表在table[]中的下標(biāo)位置
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];//從table中獲取鏈表
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);//新建一個(gè)HashMapEntry并且添加到鏈表中
size++;//HashMap的大小+1
}
從HashMap的拷貝型構(gòu)造函數(shù)的實(shí)現(xiàn)可以看出，為了更快的計(jì)算table[]的下標(biāo)，HashMap中的容量都是2的倍數(shù)，每一個(gè)table[i]都維持著一個(gè)鏈表。
鏈表結(jié)構(gòu)
先看一下table[i]中的鏈表結(jié)構(gòu)
/**
* Android添加的
* 單向鏈表結(jié)構(gòu)，每一次新建的時(shí)候會(huì)把節(jié)點(diǎn)放在鏈表的頭部
* @hide
* */
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;//當(dāng)前節(jié)點(diǎn)的key
V value;//當(dāng)前節(jié)點(diǎn)的value
HashMapEntry<K,V> next;//當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
int hash;//當(dāng)前節(jié)點(diǎn)的key的hash值
/**
* 創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并且將當(dāng)前節(jié)點(diǎn)放到指定鏈表的頭部
*/
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;//這樣實(shí)現(xiàn)的效率極高
key = k;
hash = h;
}
//...省略一些
}
HashMapEntry一個(gè)單向鏈表結(jié)構(gòu)，每一次新建的時(shí)候直接把當(dāng)前節(jié)點(diǎn)放到指定鏈表的頭部，操作效率極高。
基本操作
/**
* 將指定鍵值對(duì)添加到當(dāng)前HashMap中
* @param key 鍵值
* @param value 鍵值
* @return 如果當(dāng)前是覆蓋操作，返回被覆蓋的原來(lái)的value，否則為null
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//當(dāng)前HashMap為空
inflateTable(threshold);//初始化HashMap，此時(shí)會(huì)構(gòu)建好table[]、容量和擴(kuò)容值
}
if (key == null)//HashMap支持null作為key
return putForNullKey(value);
//計(jì)算key的hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//通過(guò)hash值計(jì)算出對(duì)應(yīng)table[]下標(biāo)
int i = indexFor(hash, table.length);
//先嘗試復(fù)寫(xiě)當(dāng)前table[]的鏈表中“相同”的key的value
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//這里可以看到如果hash值直接相等是效率最高的
//否則走equals
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//當(dāng)前鏈表中沒(méi)有指定key的節(jié)點(diǎn)，新建一個(gè)節(jié)點(diǎn)并且添加到鏈表當(dāng)中
addEntry(hash, key, value, i);
return null;
}
/**
* 當(dāng)添加到HashMap中的鍵值對(duì)的key為null的時(shí)候
* @param value key為null對(duì)應(yīng)的value
* @return 如果當(dāng)前是覆蓋操作，返回被覆蓋的原來(lái)的value，否則為null
*/
private V putForNullKey(V value) {
//可以看到key為null的時(shí)候，默認(rèn)hash為0
//先遍歷table[0]的鏈表，看是否需要覆蓋
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {//如果當(dāng)前節(jié)點(diǎn)key為null，直接覆蓋value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);//否則新建一個(gè)節(jié)點(diǎn)并且添加到鏈表當(dāng)中
return null;
}
/**
* 新建一個(gè)節(jié)點(diǎn)并且添加到指定的鏈表的頭部
* @param hash 需要添加的key的hash值
* @param key 需要添加的節(jié)點(diǎn)的key
* @param value 需要添加的節(jié)點(diǎn)的value
* @param bucketIndex 需要添加到table[]的下標(biāo)
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//先判斷是否需要進(jìn)行擴(kuò)容操作
if ((size >= threshold) && (null != table[bucketIndex])) {
//當(dāng)前大小已經(jīng)到了容量*擴(kuò)容因子的標(biāo)準(zhǔn)
//以當(dāng)前容量為基準(zhǔn)，直接擴(kuò)大一倍的方式進(jìn)行擴(kuò)容
resize(2 * table.length);
//重新計(jì)算hash值
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
//根據(jù)最新的table[]的長(zhǎng)度計(jì)算table[]下標(biāo)
bucketIndex = indexFor(hash, table.length);
}
//新建節(jié)點(diǎn)并放在放在table[bucketIndex]鏈表的頭部，大小+1
createEntry(hash, key, value, bucketIndex);
}
/**
* 擴(kuò)容操作
* 當(dāng)HashMap添加數(shù)據(jù)的時(shí)候發(fā)現(xiàn)已經(jīng)到了擴(kuò)容標(biāo)準(zhǔn)
* 則進(jìn)行擴(kuò)容
* @param newCapacity 當(dāng)前希望的新的容量
*/
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;//記錄舊的table[]
int oldCapacity = oldTable.length;//記錄舊的容量
if (oldCapacity == MAXIMUM_CAPACITY) {//擴(kuò)容前的容量已經(jīng)是最大容量，無(wú)法進(jìn)行擴(kuò)容
threshold = Integer.MAX_VALUE;//修改擴(kuò)容基準(zhǔn)為最大容量
return;
}
//根據(jù)當(dāng)前擴(kuò)容后的容量新建一個(gè)table[]
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;//轉(zhuǎn)換table[]為最新的表
//容量變化，重新計(jì)算下一次擴(kuò)容的基準(zhǔn)
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 當(dāng)進(jìn)行擴(kuò)容的時(shí)候，需要將舊的table[]數(shù)據(jù)轉(zhuǎn)移到當(dāng)前新的table[]上面
* @param newTable 擴(kuò)容后新建的table[]
*/
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;//擴(kuò)容后的大小
//遍歷舊的table[]，將舊的節(jié)點(diǎn)轉(zhuǎn)移到新的table[]中
for (HashMapEntry<K,V> e : table) {
while(null != e) {//遍歷當(dāng)前table[i]鏈表
HashMapEntry<K,V> next = e.next;
//通過(guò)每一個(gè)節(jié)點(diǎn)的hash值重新計(jì)算table[]的下標(biāo)
int i = indexFor(e.hash, newCapacity);
//將當(dāng)前節(jié)點(diǎn)放到新的table[]的鏈表的頭部
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
/**
* 從HashMap中獲得指定key對(duì)應(yīng)的value
* @param key 需要查找的key，支持null
* @return value，沒(méi)有的話為null
*/
public V get(Object key) {
if (key == null)//key為空，直接查找table[0]即可，相對(duì)于getEntry節(jié)省了indexFor的開(kāi)銷
return getForNullKey();
Map.Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
/**
* 當(dāng)key為null的時(shí)候，獲取指定的value
* 如果有key為null的節(jié)點(diǎn)，必然位于table[0]的鏈表且唯一
* @return value，沒(méi)有的話為null
*/
private V getForNullKey() {
if (size == 0) {//當(dāng)前HashMap還沒(méi)有數(shù)據(jù)
return null;
}
//遍歷table[0]，嘗試獲得key為null的節(jié)點(diǎn)的value
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
/**
* 根據(jù)指定的key獲得HashMap中對(duì)應(yīng)的節(jié)點(diǎn)的value
*/
final Map.Entry<K,V> getEntry(Object key) {
if (size == 0) {//當(dāng)前HashMap還沒(méi)有數(shù)據(jù)
return null;
}
//計(jì)算key的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//先計(jì)算hash值對(duì)應(yīng)的table的下標(biāo)
//然后遍歷對(duì)應(yīng)table[]的鏈表
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//這里可以看到如果hash值直接相等是效率最高的
//否則走equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
/**
* 從HashMap中移除指定key的節(jié)點(diǎn)
* @param key 鍵值對(duì)中的key
* @return 被移除的key節(jié)點(diǎn)對(duì)應(yīng)的value
*/
public V remove(Object key) {
Map.Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}
/**
* 從HashMap中移除指定key的節(jié)點(diǎn)
* @param key 鍵值對(duì)中的key
* @return 被移除的key節(jié)點(diǎn)
*/
final Map.Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {//當(dāng)前HashMap還沒(méi)有數(shù)據(jù)
return null;
}
//計(jì)算key的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//通過(guò)hash值計(jì)算出對(duì)應(yīng)table[]下標(biāo)
int i = indexFor(hash, table.length);
//記錄當(dāng)前table[]鏈表的頭結(jié)點(diǎn)
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
//從頭開(kāi)始遍歷當(dāng)前鏈表
while (e != null) {
HashMapEntry<K,V> next = e.next;//獲得當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
Object k;
//這里可以看到如果hash值直接相等是效率最高的
//否則走equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
//刪除當(dāng)前節(jié)點(diǎn)
modCount++;
size--;//HashMap大小-1
if (prev == e)//當(dāng)前需要?jiǎng)h除的節(jié)點(diǎn)是鏈表的頭結(jié)點(diǎn)
table[i] = next;//直接標(biāo)記當(dāng)前鏈表的頭結(jié)點(diǎn)為下一個(gè)節(jié)點(diǎn)
else//刪除鏈表非頭結(jié)點(diǎn)的節(jié)點(diǎn)
prev.next = next;//將當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)直接指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，從而當(dāng)前節(jié)點(diǎn)從鏈表中移除
e.recordRemoval(this);
return e;
}
prev = e;//記錄當(dāng)前節(jié)點(diǎn)為前置節(jié)點(diǎn)
e = next;//繼續(xù)遍歷下一個(gè)節(jié)點(diǎn)
}
//如果遍歷之后沒(méi)有找到對(duì)應(yīng)的key，此時(shí)鏈表的最后一個(gè)節(jié)點(diǎn)為null，這里直接返回null即可
return e;
}
/**
* 查找是否包含某一個(gè)key的節(jié)點(diǎn)
*/
public boolean containsKey(Object key) {
//實(shí)際上就是查找一邊當(dāng)前key的節(jié)點(diǎn)，如果節(jié)點(diǎn)不為空則包含
return getEntry(key) != null;
}
HashMap的核心操作就是put和get，并且支持key為null的情況。
put的時(shí)候首先嘗試覆蓋舊的節(jié)點(diǎn)，所以要先計(jì)算hash值找到對(duì)應(yīng)鏈表，然后遍歷鏈表尋找，如果沒(méi)有，則需要新建，在新建之前要判斷是否達(dá)到容量*擴(kuò)容因子的基準(zhǔn)，如果達(dá)到，首先要進(jìn)行擴(kuò)容操作。
擴(kuò)容會(huì)將當(dāng)前容量增加一倍的大小，然后還需要遍歷將舊的table[]鏈表中的節(jié)點(diǎn)轉(zhuǎn)移到新的table[]中，并且這個(gè)過(guò)程中還需要根據(jù)hash重新計(jì)算節(jié)點(diǎn)位于table[]的下標(biāo)。
get操作首先計(jì)算key對(duì)應(yīng)的hash值，然后獲得對(duì)應(yīng)的table[]的節(jié)點(diǎn)鏈表，進(jìn)而遍歷鏈表查找對(duì)應(yīng)的節(jié)點(diǎn)并且返回value。
總結(jié)
從上面可以看到，HashMap中會(huì)有不少遍歷鏈表的操作，這個(gè)其實(shí)就說(shuō)明hash散列的重要性，如果不同的值但是最后放到了同一個(gè)table[i]的鏈表中，會(huì)導(dǎo)致某一個(gè)鏈表特別長(zhǎng)，這樣對(duì)于遍歷效率來(lái)說(shuō)不是太好。
擴(kuò)容操作需要轉(zhuǎn)移舊的節(jié)點(diǎn)等操作，所以說(shuō)對(duì)于已知初始容量的HashMap來(lái)說(shuō)，最好是指定容量，避免多余的擴(kuò)容操作。
HashMap并不是線程安全的，如果多個(gè)線程對(duì)鏈表進(jìn)行操作，會(huì)造成不可預(yù)期問(wèn)題，此時(shí)應(yīng)該嘗試ConcurrentHashMap或者Collections.synchronizedMap()。
