一、HashMap的結(jié)構(gòu)及其原理
1.什么是HashMap
HashMap是基于哈希表的Map接口的非同步實現(xiàn)。是雙列集合，一次儲存鍵與值鍵與值一一對應(yīng)（鍵是唯一性，值不唯一，同時鍵與值都可以是null）。
2.數(shù)據(jù)結(jié)構(gòu)
Java中最基本的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和引用（指針），HashMap通過這兩個數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。HashMap是一個==“鏈表散列”==的數(shù)據(jù)接口，即通過數(shù)組+鏈表結(jié)合實現(xiàn)。而從jdk1.8起，為了進(jìn)一步提高效率，引入了紅黑樹，即數(shù)組+鏈表/紅黑樹。（當(dāng)同一hash索引下的節(jié)點個數(shù)超過8個的話，就通過紅黑樹的形式存儲起來）
為什么要采取這種結(jié)構(gòu)呢？
這里我們簡單的說一下，不做深究：
1.數(shù)組的查找通過索引查找是非?？斓模瑫r間復(fù)雜度o(1)。
2.鏈表呢，我們刪除和增加效率是非常高的。
3.紅黑樹，將普通鏈表的查找速度由o(n)降低到了o(logn)
所以這幾者相結(jié)合，將會達(dá)到很好的效果，具體如何結(jié)合的，我們通過下面的分析一步一步探究。
3.通過源碼一步一步研究HashMap的存儲元素過程
去看了源碼，密密麻麻的好多代碼啊，難道要一行一行的去研究嗎？
不用，研究他們的核心部分即可，那從何處開始研究呢？
我們就通過我們使用HashMap的步驟去研究：
1.
HashMap map = new HashMap();
附上這行代碼的源碼：
/**
* 哈希表的加載因子
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
/**
* 在構(gòu)造函數(shù)未指定的時候，加載因子的默認(rèn)值=0.75f
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 其他的屬性都是默認(rèn)值
}
這里我們要記住的就是loadFactor（加載因子），那么這個加載因子有什么用呢？
這個加載因子是和數(shù)組的空間利用率有關(guān)，即一個數(shù)組的長度為length時，我們所能存儲元素的長度只能是length*loadFactor。
2.
public V put(K key, V value)，key代表鍵，value代表值
看這個方法的源代碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//繼續(xù)解刨，看putVal(hash(key),key,value,false,true)
//首先我們看看hash(key)干嘛的
static final int hash(Object key) {
int h;
/*
我們看到，當(dāng)key為空的時候，會返回值0，不為空的時候，會將key的哈希值的高位（16位）與低位（16位）進(jìn)行^（異或）計算，然后返回結(jié)果值，這個結(jié)果有什么用呢，是用來用于后面再次計算得出所在數(shù)組中的索引值
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//這個就是儲存每個節(jié)點的具體步驟了
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/*
變量名解釋：tab（數(shù)組） p（節(jié)點,數(shù)組中每個元素）
n為數(shù)組的長度,i為數(shù)組的索引
*/
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果tab引用為空指針，或者數(shù)組長度為0,即返回一個新的數(shù)組，長度為n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
這里有個(n-1)&hash式子,計算的結(jié)果是數(shù)組的索引
這里的邏輯是判斷數(shù)組中這個索引的對應(yīng)的值是否為null，若是
為空的話，將將這個節(jié)點儲存在這個索引的位置
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//執(zhí)行這里，說明這個索引位置儲存的不是鏈表就是紅黑樹了
Node<K,V> e; K k;
/*
這里的邏輯是，這個索引位置已有節(jié)點了，那么就判斷添加的的key
和這里已有節(jié)點的key是否是同一個地址的或者是否是內(nèi)容相同的，是的話，就將添加進(jìn)來的value值替換掉原有節(jié)點的value值
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷當(dāng)前索引位置的對象是否屬于紅黑樹，是的話，添加上去
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//執(zhí)行這里說明這里不是紅黑樹，是鏈表
/*
遍歷循環(huán)鏈表
*/
for (int binCount = 0; ; ++binCount) {
//此節(jié)點的下一個節(jié)點是否為空節(jié)點，是的話，直接賦值節(jié)點
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//判斷此位置的鏈表個數(shù)是否超過了8個，超過
//將執(zhí)行teeifyBin()方法(擴(kuò)容或轉(zhuǎn)為紅黑樹)，并結(jié)束并推出循環(huán)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//節(jié)點不為空，判斷哈希值和key是否是一樣的，是的話結(jié)束并退出循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;//遍歷下一個節(jié)點
}
}
//判斷添加的節(jié)點是否為新節(jié)點，不是新節(jié)點，則將新的value值替換老的value值，并返回老的value值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//記錄HashMap結(jié)構(gòu)修改的個數(shù)(只有添加了新的節(jié)點)
++modCount;
//添加元素后此時數(shù)組中元素個數(shù)>數(shù)組中規(guī)定的個數(shù)(數(shù)組長度*負(fù)載因子)時擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
這里我們通過源碼分析了我們使用HashMap添加對象的一系列過程，這里我們畫個圖看看一比較形象的邏輯：
通過分析put(K key,V value)的源碼，我們知道了HashMap內(nèi)部結(jié)構(gòu):
- 數(shù)組Node<K key,V value>:
//節(jié)點，通過內(nèi)部內(nèi)實現(xiàn)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//存放hash值（key的）
final K key; //存放key值
V value; //存放value至
Node<K,V> next; //存放下一個節(jié)點的地址
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
上面就是鏈表的組成部分，一個一個節(jié)點組成的。而數(shù)組呢，就是存放每一個hash值相同的節(jié)點，從第一個開始存放，往后相同的hash值節(jié)點便通過鏈表的形式存放。
-
hash算法：
hash算法是我們需要了解的部分，因為你存入的元素放在數(shù)組的那個位置是通過這個來計算的，即上面出現(xiàn)的計算公式：
(n-1)&hash
計算出索引位置的算法.png
具體計算過程如圖所示。（這里需要注意的是，因為數(shù)組的長度始終是2的次方冪，這里的與運(yùn)算，就相當(dāng)于給length-1取模運(yùn)算）
注意：通過這樣的算法，我們其實可以知道，總會有一種情況，計算得出的值是相同的，所以需要解決哈希沖突，HashMap的解決辦法就是一開始我們介紹的形式，數(shù)組+鏈表，即==鏈表法==。還有一種方法是==開放地址法==（即通過探測算法，當(dāng)此位置被占用，即尋找下一個可用的位置）。
二.HashMap的哈希表散列運(yùn)算
我們知道每一個對象都有它的哈希值，這是Object類中的本地方法，具體怎么計算的，目前我也不知道，只要知道這個對于每一個對象得出的值基本不可能即可。
因為通過%（取模運(yùn)算）是要進(jìn)行/（除法）運(yùn)算的，效率低。（其實到底低多少我也不知道）
而通過&（與運(yùn)算）是直接通過對二進(jìn)制來計算的，效率高。
那么：
(n-1)&hash
n為什么要-1呢？
首先，我們要知道n是數(shù)組的長度，而HashMap的數(shù)組長度是==偶數(shù)，即長度為2的冪次方，每次擴(kuò)容都是之前的一倍==。
然后我們知道偶數(shù)的二進(jìn)制最低位是0，那好，偶數(shù)的與運(yùn)算我們可以很明確的得出，結(jié)果必然是偶數(shù)，所以，如果直接用偶數(shù)來進(jìn)行哈希表散列將浪費(fèi)一半的空間。
所以，我們將n-1得到奇數(shù)，而奇數(shù)進(jìn)行與運(yùn)算，得到的結(jié)果可能是可能是偶數(shù)，也可能是奇數(shù)，這樣就不會浪費(fèi)空間了！
