HashMap 的工作原理（Android7.1源碼）
其他相關(guān)文章
簡介
HashMap 是以散列表形式實(shí)現(xiàn)的Map (Key-Value)
初始化
...
//保存數(shù)據(jù)的散列表
transient HashMapEntry<K烧栋，V>[] table = (HashMapEntry<K相赁，V>[]) EMPTY_TABLE;
...
//實(shí)際存在的size個數(shù)
transient int size;
...
//table擴(kuò)展的閾值
int threshold;
//HashMap構(gòu)造函數(shù)中并沒有對table分配空間 而是使用EMPTY_TABLE
public HashMap(int initialCapacity谊囚， float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
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).
//注釋的意思是在當(dāng)table為空(也就是當(dāng)前，剛創(chuàng)建的HashMap就是一個空列表)時inflateTable中會對table散列表進(jìn)行分配空間
threshold = initialCapacity;
//空實(shí)現(xiàn)
init();
}
新創(chuàng)建的HashMap并沒有對table散列表分配內(nèi)存空間瑞躺，在后面的put方法中我們將分析具體分配空間的位置以及函數(shù).散列表的存儲元素是HashMapEntry酱虎。
/** @hide */ // Android added.
static class HashMapEntry<K蹄胰，V> implements Map.Entry<K，V> {
final K key;
V value;
HashMapEntry<K丢氢，V> next;
int hash;
}
除了Key與Value值之外還有HashMapEntry的引用傅联，這里先簡單介紹下這個next值，它鏈接的對象將會是一個鏈表的Head或者紅黑樹的Head疚察，它就是解決HashMap沖突的方法之一 - 鏈接法蒸走。
put 方法
public V put(K key， V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash貌嫡， table.length);
for (HashMapEntry<K载碌，V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash， key衅枫， value嫁艇， i);
return null;
}
當(dāng)table為空時，第一次使用put方法時會觸發(fā)這個table散列表的初始化弦撩。
當(dāng)key是空時步咪，將會插入value，并返回老的數(shù)據(jù)
-
通過singleWordWangJenkinsHash方法來獲取HashCode.
... public static int singleWordWangJenkinsHash(Object k) { int h = k.hashCode(); h += (h << 15) ^ 0xffffcd7d; h ^= (h >>> 10); h += (h << 3); h ^= (h >>> 6); h += (h << 2) + (h << 14); return h ^ (h >>> 16); }實(shí)質(zhì)是通過key的hashCode()益楼，然后再處理得到hash值猾漫，這個hash的值很重要。
通過indexFor方法計算得出當(dāng)前數(shù)據(jù)在table散列表的索引位置
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);
}
依舊是通過'與'運(yùn)算來高效計算出索引值悯周，由于length永遠(yuǎn)是2的倍數(shù)或者是0，所以在這里位運(yùn)算提高了速度（通過與上length - 1可以快速計算出index）陪竿。
一般HashMap的平均查找數(shù)據(jù)時間復(fù)雜度(1)禽翼，這一個優(yōu)點(diǎn)主要得益于這個Hashcode的計算，為了更低的沖突率族跛，在前面的singleWordWangJenkinsHash函數(shù)中最后一步的h ^ (h >>> 16)闰挡，就是將h的高16與低16位異或操作，讓hash值盡力不會出現(xiàn)部分位數(shù)相同的情況礁哄， 讓indexFor計算更加平均长酗，每一個值對應(yīng)一個index，減少沖突率桐绒。
- 通過獲得的index在散列表指定位置找到HashMapEntry夺脾，由于HashMap是使用鏈接法來解決沖突的之拨，所以如果出現(xiàn)沖突(也就是不同的key得到的index相同)，通過上面我們講的next值向下查找如果找到一樣的數(shù)據(jù)咧叭，則替換并返回敦锌，如果不存在則在此處添加數(shù)據(jù)。
void addEntry(int hash佳簸， K key乙墙， V value， int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash生均， table.length);
}
createEntry(hash听想， key， value马胧， bucketIndex);
}
//擴(kuò)充table散列表
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor汉买， MAXIMUM_CAPACITY + 1);
}
//將老列表中的數(shù)據(jù)插入到新數(shù)據(jù)表中
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K，V> e : table) {
//此處e代表table中的Entry
while(null != e) {
//這個while循環(huán)是如果Entry含有next值佩脊，將會順著next向下查找
HashMapEntry<K蛙粘，V> next = e.next;
//計算在新table中的index
int i = indexFor(e.hash， newCapacity);
//將當(dāng)前Entry拷貝到新位置前如果那個位置存在數(shù)據(jù)
//則保存到Entry的next中
e.next = newTable[i];
//移到新位置
newTable[i] = e;
e = next;
}
}
}
-
調(diào)用addEntry方法
- 當(dāng)數(shù)據(jù)數(shù)量達(dá)到閾值則要擴(kuò)展成原先的兩倍
- 在resize函數(shù)中威彰，當(dāng)列表的大小已經(jīng)是最大值出牧，設(shè)置閾值為integer的最大值，不再擴(kuò)展
- 生成一個新的表歇盼，然后執(zhí)行transfer將老表中的數(shù)據(jù)轉(zhuǎn)換到新表中去舔痕。
- 在transfer函數(shù)中，先遍歷老表table豹缀，找出已經(jīng)有數(shù)據(jù)的Entry伯复，重新通過indexFor計算在新表中的index，將原先的entry移到新位置邢笙， 如果原先數(shù)據(jù)中存在next值則繼續(xù)順著next進(jìn)行移動數(shù)據(jù)啸如。transfer函數(shù)不僅僅是擴(kuò)展散列表大小那么簡單，通過transfer這一步可以將原先已經(jīng)存在的沖突均勻分散開氮惯，這一步可以提高當(dāng)前HashMap的獲取數(shù)據(jù)的速度叮雳， 重點(diǎn)就在indexFor方法中的與操作，待會我將來分析為何起到這個作用
- transfer完數(shù)據(jù)后筐骇，更新閾值.
- 結(jié)束了resize方法后债鸡，重新計算bucketIndex江滨，然后通過createEntry來插入數(shù)據(jù).
indexFor 的神奇作用
//計算公式
h & (length-1);
//假設(shè)一個Key的hashCode是 0000 0000 0000 0000 0000 0001 1111 1111
//另一個Key的hashCode是 0000 0000 0000 0000 0000 0000 1111 1111
//length正好是256 也就是2的八次方 0001 0000 0000
//length - 1等于 0000 1111 1111
//執(zhí)行與運(yùn)算
//兩個index一樣 index1 = index2 = 255;
//當(dāng)resize()函數(shù)執(zhí)行翻倍時
//length正好是512 也就是2的九次方 0010 0000 0000
//length - 1等于 0001 1111 1111
//執(zhí)行與運(yùn)算
//index1 等于 0001 1111 1111
//index2 等于 0000 1111 1111
//兩者不相等了
通過上面的注釋的計算介紹铛纬，可以很清晰的看到原本沖突的兩個key，通過擴(kuò)充后唬滑，并且只要一個indexFor的函數(shù)告唆，執(zhí)行相與操作就可以將沖突完美化解棺弊。
get 方法
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K，V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K擒悬，V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
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;
}
get方法很簡單懂牧，就是通過key直接找數(shù)據(jù)侈净，第一步獲取hash值，通過indexFor獲取數(shù)據(jù)在數(shù)組的位置僧凤，然后遍歷畜侦，如果沒有沖突的話，直接可以獲取到數(shù)據(jù)并退出遍歷躯保，存在沖突就需要在next的鏈表中查找旋膳。
沖突的壞處
這個標(biāo)題段也許是多余的吧，希望不明白的人可以知道下吧途事。
HashMap的高效率依靠的就是通過HashCode散列式插入到表的不同位置验懊，當(dāng)不存在沖突的時候，get()查找可以是(1)的時間復(fù)雜度尸变，直接就可以取到數(shù)據(jù)义图，如果存在沖突就必須沿著next的鏈表一個一個查詢比對，效率大大降低召烂。
題外話
Java8中的HashMap源碼中歌溉，在解決沖突部分，使用了紅黑樹與鏈表替換使用的方式來管理沖突的數(shù)據(jù)骑晶，提高沖突時的get(object)搜索速度痛垛，當(dāng)沖突數(shù)據(jù)少時用鏈表，大時使用紅黑樹桶蛔。
總是HashMap是出了名的用空間換時間的數(shù)據(jù)結(jié)構(gòu)匙头，也是常用的數(shù)據(jù)結(jié)構(gòu)，但是內(nèi)存使用率低是它致命的弱點(diǎn)仔雷，為此Android有一個ArrayMap數(shù)據(jù)結(jié)構(gòu)在一定程度上來替代它蹂析，下面的章節(jié)中我將分析ArrayMap這個數(shù)據(jù)結(jié)構(gòu)，講解什么時候使用ArrayMap什么時候使用HashMap碟婆。
更多好文章請關(guān)注微信公眾號【Android技術(shù)椀绺В】，微信公眾號剛剛創(chuàng)建不久希望大家多多支持竖共。
