概述
HashMap是基于哈希表(散列表)，實(shí)現(xiàn)Map接口的雙列集合，數(shù)據(jù)結(jié)構(gòu)是“鏈表散列”，也就是數(shù)組+鏈表 ，key唯一的value可以重復(fù)，允許存儲(chǔ)null 鍵null 值，元素?zé)o序。
哈希表
數(shù)組：一段連續(xù)控件存儲(chǔ)數(shù)據(jù)，指定下標(biāo)的查找，時(shí)間復(fù)雜度O(1),通過(guò)給定值查找，需要遍歷數(shù)組，自已對(duì)比復(fù)雜度為O（n） 二分查找插值查找，復(fù)雜度為O(logn)
線性鏈表：增 刪除僅處理結(jié)點(diǎn)，時(shí)間復(fù)雜度O(1)查找需要遍歷也就是O(n)
二叉樹(shù)：對(duì)一顆相對(duì)平衡的有序二叉樹(shù)，對(duì)其進(jìn)行插入，查找，刪除，平均復(fù)雜度O(logn)
哈希表：哈希表中進(jìn)行添加，刪除，查找等操作，性能十分之高，不考慮哈希沖突的情況下，僅需一次定位即可完成，時(shí)間復(fù)雜度為O(1)哈希表的主干就是數(shù)組
hash沖突
如果兩個(gè)不同的元素，通過(guò)哈希函數(shù)得出的實(shí)際存儲(chǔ)地址相同怎么辦？也就是說(shuō)，當(dāng)我們對(duì)某個(gè)元素進(jìn)行哈希運(yùn)算，得到一個(gè)存儲(chǔ)地址，然后要進(jìn)行插入的時(shí)候，發(fā)現(xiàn)已經(jīng)被其他元素占用了，其實(shí)這就是所謂的哈希沖突，也叫哈希碰撞。前面我們提到過(guò)，哈希函數(shù)的設(shè)計(jì)至關(guān)重要，好的哈希函數(shù)會(huì)盡可能地保證 計(jì)算簡(jiǎn)單和散列地址分布均勻,但是，我們需要清楚的是，數(shù)組是一塊連續(xù)的固定長(zhǎng)度的內(nèi)存空間，再好的哈希函數(shù)也不能保證得到的存儲(chǔ)地址絕對(duì)不發(fā)生沖突。那么哈希沖突如何解決呢？哈希沖突的解決方案有多種:開(kāi)放定址法（發(fā)生沖突，繼續(xù)尋找下一塊未被占用的存儲(chǔ)地址），再散列函數(shù)法，鏈地址法，而HashMap即是采用了鏈地址法，也就是數(shù)組+鏈表的方式
鏈表則是主要為了解決哈希沖突而存在的，如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）,那么對(duì)于查找，添加等操作很快，僅需一次尋址即可；如果定位到的數(shù)組包含鏈表，對(duì)于添加操作，其時(shí)間復(fù)雜度為O(n)，首先遍歷鏈表，存在即覆蓋，否則新增；對(duì)于查找操作來(lái)講，仍需遍歷鏈表，然后通過(guò)key對(duì)象的equals方法逐一比對(duì)查找。所以，性能考慮，HashMap中的鏈表出現(xiàn)越少，性能才會(huì)越好
HashMap數(shù)據(jù)結(jié)構(gòu)
HashMap的底層就是一個(gè)數(shù)組，數(shù)組中每一項(xiàng)有事一個(gè)鏈表，當(dāng)新建一個(gè)HashMap時(shí)候，就會(huì)初始化一個(gè)數(shù)組，查看源碼如下，直接看重點(diǎn)，table = new Entry[capacity]; 創(chuàng)建一個(gè)Entry數(shù)組，也就是上面的table ,這個(gè)Entry結(jié)構(gòu)就是static的包含key value 還有一個(gè)next的指針，指向下一個(gè)元素的引用，也就構(gòu)成了鏈表
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
entry結(jié)構(gòu)：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
HashMap存儲(chǔ)
調(diào)用put 方法時(shí)候，如果key存在key不會(huì)覆蓋，新的value會(huì)替代舊的value，返回舊的value;如果key不存在，該方法返回null
看它的源碼，調(diào)用put時(shí)候，根據(jù)key的hashCode重新計(jì)算hash值，根據(jù)hash值得到這個(gè)元素在數(shù)組中的位置 也就是下標(biāo)，如果數(shù)組在該位置上已有其他元素，那么在這個(gè)位置上的元素將以鏈表的形式存放，新加入的在立案表頭，先加入的在尾部
public V put(K key, V value) {
//其允許存放null的key和null的value，當(dāng)其key為null時(shí)，調(diào)用putForNullKey方法，放入到table[0]的這個(gè)位置
if (key == null)
return putForNullKey(value);
//通過(guò)調(diào)用hash方法對(duì)key進(jìn)行哈希，得到哈希之后的數(shù)值。該方法實(shí)現(xiàn)可以通過(guò)看源碼，其目的是為了盡可能的讓鍵值對(duì)可以分不到不同的桶中
int hash = hash(key);
//根據(jù)上一步驟中求出的hash得到在數(shù)組中是索引i
int i = indexFor(hash, table.length);
//如果i處的Entry不為null，則通過(guò)其next指針不斷遍歷e元素的下一個(gè)元素。
for (Entry<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;
}
HashMap的讀取
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) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<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()方法也會(huì)是首先計(jì)算key的 hashCode 找到數(shù)組中對(duì)應(yīng)位置的某一元素，通過(guò)key的equals方法在對(duì)應(yīng)位置的鏈表中找到要的元素，
key(hashcode)-->hash-->indexFor-->最終索引位置，找到對(duì)應(yīng)位置table[i]，再查看是否有鏈表，遍歷鏈表，通過(guò)key的equals方法比對(duì)查找對(duì)應(yīng)的記錄。要注意的是，有人覺(jué)得上面在定位到數(shù)組位置之后然后遍歷鏈表的時(shí)候，e.hash == hash這個(gè)判斷沒(méi)必要，僅通過(guò)equals判斷就可以。其實(shí)不然，試想一下，如果傳入的key對(duì)象重寫(xiě)了equals方法卻沒(méi)有重寫(xiě)hashCode，而恰巧此對(duì)象定位到這個(gè)數(shù)組位置，如果僅僅用equals判斷可能是相等的，但其hashCode和當(dāng)前對(duì)象不一致，這種情況，根據(jù)Object的hashCode的約定，不能返回當(dāng)前對(duì)象，而應(yīng)該返回null，后面的例子會(huì)做出進(jìn)一步解釋。
hash算法
hash(int h)方法是根據(jù)key的hashCode重新計(jì)算一次散列。此算法加入了高位計(jì)算，防止低位不變，高位變化時(shí)，造成的hash沖突
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//得到k的hashcode值
h ^= k.hashCode();
//進(jìn)行計(jì)算
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
我們根據(jù)hash值獲得在數(shù)組中的位置，我們希望hashmap里面元素位置盡量分布均勻，盡量是的沒(méi)個(gè)位置上的元素?cái)?shù)量只有一個(gè)每當(dāng)hash算法求得這個(gè)位置的時(shí)候，馬上就可以知道對(duì)應(yīng)位置的元素就是我們要讀取的，不用再遍歷鏈表，提神效率
HashMap的容量
任意對(duì)象，它的hashCode()返回值相同，那么程序調(diào)用hash(int h)方法所計(jì)算得到的hash碼值總是相同的，為了讓他的hash值得到位置分布更均勻，可以對(duì)他 % 運(yùn)算，但是%運(yùn)算性能肯定是沒(méi)有位與運(yùn)算 舉個(gè)例子比如我們的h是10 h% 4=2;使用10&（4-1） 也就是1010&0011 = 0010 也就是2，但是我們計(jì)算機(jī)存儲(chǔ)是二進(jìn)制，所以性能高不少！
static int indexFor(int h, int length) {
return h & (length-1);
}
HashMap底層數(shù)組的長(zhǎng)度總是 2 的 n 次方,通過(guò)這個(gè)indexFor方法得到保存位
為什么是2的n次方
假如是長(zhǎng)度15 ，而我們的h 是8 和9 2種情況， 那么forIndex計(jì)算如下
1000 1001
1110 1110
——————————————
1000 1000
結(jié)果是一樣的，也就是在數(shù)組中一個(gè)位置上那么查詢的時(shí)候就要遍歷鏈表得到8或者9，降低查詢效率。同時(shí)，長(zhǎng)度15時(shí)候，hash值會(huì)和 1110 與運(yùn)算，最后一位是1的比如0001，0011,0111,1011.。。。這幾個(gè)位置算下來(lái)一直都是尾數(shù)是0 ，這樣就相當(dāng)于這幾個(gè)位置存不到數(shù)據(jù)，造成空間浪費(fèi)，可用長(zhǎng)度，變小了也就意味著增加了碰撞的幾率，減慢查詢效率，而當(dāng)長(zhǎng)度是2的n次方時(shí)候，比如1111 11111 都能保證得到和原來(lái)hash低位相同，也就是擴(kuò)容后只有一個(gè)位差異，多出來(lái)最左邊位的1 這樣只要對(duì)應(yīng)左邊的哪一個(gè)差異位為0，就能保證得到新的數(shù)組索引和老的數(shù)組索引一直 ，這樣數(shù)據(jù)在數(shù)組的分布比較均勻，也就是說(shuō)減少碰撞的幾率，減少了鏈表的遍歷，提升效率
h: 0 1000
16的length-1 0 1110
32的length-1 1 1110
————————————————
h的 01000 的第一個(gè)0為0就能保證一直，為1沒(méi)辦法！
最終存儲(chǔ)流程：
HashMap的resize（rehash）
當(dāng) HashMap 中的元素越來(lái)越多的時(shí)候，hash沖突的幾率也就越來(lái)越高，因?yàn)閿?shù)組的長(zhǎng)度是固定的，所以為了提高查詢的效率，就要對(duì)HashMap的數(shù)組進(jìn)行擴(kuò)容，在HashMap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)是：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，這就是 resize（rehash）
loadFactor指的是負(fù)載因子 HashMap能夠承受住自身負(fù)載（大小或容量）的因子，loadFactor的默認(rèn)值為 0.75認(rèn)情況下，數(shù)組大小為 16，那么當(dāng)HashMap中元素個(gè)數(shù)超過(guò) 160.75=12 的時(shí)候，就把數(shù)組的大小擴(kuò)展為 216=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知 HashMap 中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高 HashMap 的性能
負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對(duì)于使用鏈表法的散列表來(lái)說(shuō)，查找一個(gè)元素的平均時(shí)間是 O(1+a)，因此如果負(fù)載因子越大，對(duì)空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過(guò)于稀疏，對(duì)空間造成嚴(yán)重浪費(fèi)
HashMap不是線程安全的
總結(jié)
HashMap在底層將key-value當(dāng)成一個(gè)整體進(jìn)行處理，這個(gè)整體就是一個(gè)Entry對(duì)象。HashMap底層采用一個(gè) Entry[]數(shù)組來(lái)保存所有的key-value，當(dāng)需要存儲(chǔ)一個(gè)Entry對(duì)象時(shí)，會(huì)根據(jù) hash 算法來(lái)決定其在數(shù)組中的存儲(chǔ)位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲(chǔ)位置；當(dāng)需要取出一個(gè)Entry時(shí)，也會(huì)根據(jù)hash算法找到其在數(shù)組中的存儲(chǔ)位置，再根據(jù)equals方法從該位置上的鏈表中取出該Entry
常見(jiàn)面試題
當(dāng)兩個(gè)對(duì)象的hashcode相同會(huì)發(fā)生什么？
hashcode相同，說(shuō)明兩個(gè)對(duì)象HashMap數(shù)組的同一位置上，接著HashMap會(huì)遍歷鏈表中的每個(gè)元素，通過(guò)key的equals方法來(lái)判斷是否為同一個(gè)key，如果是同一個(gè)key，則新的value會(huì)覆蓋舊的value，并且返回舊的value。如果不是同一個(gè)key，則存儲(chǔ)在該位置上的鏈表的鏈頭
如果兩個(gè)鍵的hashcode相同，你如何獲取值對(duì)象？
遍歷HashMap鏈表中的每個(gè)元素，并對(duì)每個(gè)key進(jìn)行hash計(jì)算，最后通過(guò)get方法獲取其對(duì)應(yīng)的值對(duì)象
你了解重新調(diào)整HashMap大小存在什么問(wèn)題嗎？
當(dāng)多線程的情況下，可能產(chǎn)生條件競(jìng)爭(zhēng)。當(dāng)重新調(diào)整HashMap大小的時(shí)候，確實(shí)存在條件競(jìng)爭(zhēng)，如果兩個(gè)線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會(huì)同時(shí)試著調(diào)整大小。在調(diào)整大小的過(guò)程中，存儲(chǔ)在鏈表中的元素的次序會(huì)反過(guò)來(lái)，因?yàn)橐苿?dòng)到新的數(shù)組位置的時(shí)候，HashMap并不會(huì)將元素放在LinkedList的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競(jìng)爭(zhēng)發(fā)生了，那么就死循環(huán)了
