Map
java中的Map是一種可以存放鍵值對的數(shù)據(jù)集合，Map中的Key是不可重復的，同時一個Key只能對應(yīng)一個 Value.
Map是用來替換Java中的Dictionary,
Map可以提供三個視圖：
1. 將所有的Key返回為一個Set keySet()
1. 將所有的Value返回為一個Set valueSet（）
1. 或者將Key-value返回為一個Set
像TreeMap這一類，可以保證元素的存放和獲取順序，但是HashMap并不能保證。
1. HashMap
HashMap 是Map的實現(xiàn)類，同時HashMap 允許使用null作為key，或者value。 HashMap大致上跟HashTable是相同的（Hashtable是同步的，并且不允許null）
HashMap是基于哈希表結(jié)構(gòu)，其在沒有hash沖突的情況下，進行添加，刪除，查找等操作性能是很高的，只需要對指定位置進行一次從操作即可，其時間復雜度為 O(1),
在HashMap中，其主要的數(shù)據(jù)存儲方式就是數(shù)組。 我們通過Hash算法，將當前元(Entry)的關(guān)鍵字通過某一個函數(shù)直接映射到數(shù)組中的某個位置，通過數(shù)組下標一次定位就可以完成操作。
在HashMap中，我們將上面題導的映射函數(shù)稱之為 哈希函數(shù)，哈希函數(shù)的設(shè)計，決定了Hash沖突的次數(shù)，也就決定了當前HashMap的性能。
HashMap的基本操作例如 get，put 所需要的時間是固定的，HashMap的Iterator方法跟當前HashMap的容量成正比。 因此如果你想保證迭代器的性能，那么就不能將HashMap的初始容量設(shè)置的太大。
影響HashMap的關(guān)鍵因素：
1. **initial capacity**
1. **loadFactor** （初始值和**loadfactory**共同決定了當前**hashMap**的擴容次數(shù)）
1. **key**的**hash**算法 （如果**Key**的**hash**值重復較多，那么也可以直接降低當前**hashmap**的性能）
1.1 HashMap基本原理
假設(shè)我們需要存入兩個 <Key ->Value> 元素
A: <Chen -> henan>
B: <Wang -> shandong>
固定哈希算法為 函數(shù)f(x), indexA = f(Chen), indexB = f(Wang)
這樣我們得到了A，B兩個元素的數(shù)組角標，這樣就把相應(yīng)的Entry放入對應(yīng)數(shù)組位置就可以，用圖表示可以為：
1.2hash沖突
上面說到的hash函數(shù)，僅僅是指 將元素的Key轉(zhuǎn)換成 index的算法，有時候我們并不能保證我們使用的hash算法能夠保證 不同的鍵值對元素對應(yīng)不同的 數(shù)組index，這樣就有可能出現(xiàn) hash(Chen) == hash(Wang)的情況，這就是我們說的hash沖突。
通常情況下解決hash沖突的方法有很多種，例如：開放定址算法（發(fā)生沖突，繼續(xù)尋找下一塊未被使用的地址），再散列算法，鏈地址法，在HashMap中，設(shè)計者使用了鏈地址法，也就是對于沖突的元素，使用鏈表進行存儲
2 HashMap的實現(xiàn)
對于HashMap 如何存儲鍵值對數(shù)據(jù)的呢？
HashMap在內(nèi)存中是基于數(shù)組形式實現(xiàn)的：
transient Node<K,V>[] table; // 內(nèi)部使用一個數(shù)組存儲鍵值對元素
鍵值對元素的存儲格式, 使用Node對鍵值對進行包裝：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // Node包含當前鍵值對的hash值
final K key; //key值
V value; //value值
Node<K,V> next; //下一個節(jié)點的Node， 當出現(xiàn)hash沖突時使用
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
可以推出，一個HashMap的基本形式如下：
當鏈表數(shù)量超過8：
對于 index0、index3、index7出現(xiàn)了hash碰撞，所以，這個節(jié)點存儲的node就形成了一個單鏈表的形式。
如果通過hash算法定位到的數(shù)組位置 沒有鏈表，那么 刪除，替換，添加等操作的時間復雜度都是 O(1)
如果定位到的數(shù)組位置有hash沖突，那么這些操作的時間復雜度就為 O(n), n = 鏈表長度
3 HashMap源碼分析
下面我們就從HashMap的一些基本操作代碼入手，來探究下 HashMap的實現(xiàn)原理。
3.1 構(gòu)造方法
HashMap的兩個關(guān)鍵構(gòu)造因子：
initial compacity 初始化容量, 這個參數(shù) 決定了當前HashMap可以擁有多少個key-value 實體
loadFactor： 這個值 決定了當前HashMap的 裝填程度， 如果當前 容量超過 capacity loadFactor，那么就表示當前HashMap需要進行一次重新擴容，同時需要重新hash*。
因此，如果想要保證當前HashMap的性能， 適當?shù)?strong>Map大小以及加載因子是關(guān)鍵。
另一個影響HashMap性能的關(guān)鍵就是 Key的hash值，如果有大量Key的hash值是重復的，那么當前HashMap的性能也會降低。
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);
this.loadFactor = loadFactor; // hashMap的加載因子，簡單的說就是 hashMap可以進行擴容時的容量占比
this.threshold = tableSizeFor(initialCapacity); //對于給定的容量，hashTable都轉(zhuǎn)換為 相應(yīng)的2^n.
}
3.2 HashMap.put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
關(guān)于 hash(key)算法解釋參見：
HashMap的hash() - Black_Knight - 博客園 (cnblogs.com)
HashMap中的hash函數(shù) - 淡騰的楓 - 博客園 (cnblogs.com)
可以看到 HashMap.hash確實在兼容性能的基礎(chǔ)上做到了盡量減少hash碰撞。
3.2.1 putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 參見 3.2.2 創(chuàng)建一個長度為16的數(shù)組
if ((p = tab[i = (n - 1) & hash]) == null) //如果 通過hash值找到的位置沒有存放，那么直接創(chuàng)建新的node，并將值放入。
tab[i] = newNode(hash, key, value, null);
else { //以下就是處理hash沖突的步驟了。
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果指定hash位置已經(jīng)存放了Node，并且key的值 相等，那么就直接進行替換
else if (p instanceof TreeNode) //如果指定結(jié)點已經(jīng)變成了 樹，說明這里沖突太多，執(zhí)行樹圖的存放操作，數(shù)的操作參見 # 4.1.1
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) { //這里開始遍歷鏈表形式。
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); //鏈表接入新的結(jié)點之后，長度超出閾值，那么就需要將此鏈表變成樹
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //編輯尋找當前Key的Node，找到就跳出。
break;
p = e;
}
}
if (e != null) { // existing mapping for key 只有當鏈表中有一個已經(jīng)存在相同Key的node時，走這里，
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //這里暫時是空實現(xiàn)
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize(); //檢查當前數(shù)組的長度，看是否需要進行擴容
afterNodeInsertion(evict);
return null;
}
3.2.2 數(shù)組的初始化方法：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //第一次調(diào)用的話， table為null，
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //第一次初始化，默認的容量就是16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //第一次初始化，擴容閾值就是 16*0.75
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //第一次初始化（不設(shè)置容量的情況下），這里就創(chuàng)建一個長度為16的數(shù)組
table = newTab;
if (oldTab != null) { //第一次，這里不會走
。。。
}
return newTab;
}
3.3.3 鏈表長度太長，鏈表將會變成樹
static final int TREEIFY_THRESHOLD = 8; // 默認鏈表最長的長度為8
判斷是否滿足將當前鏈表變成樹的條件：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)// 如果數(shù)組為空，或者當前數(shù)組長度小于 默認長度64，那么就直接進行擴容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { //指定 hash位置的結(jié)點存在
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null); //到這里做完，還是類似于一個雙向鏈表的形式。
if ((tab[index] = hd) != null)
hd.treeify(tab);//這里的操作就是關(guān)鍵一部了， 將鏈表變成標準的樹結(jié)構(gòu)
}
}
將鏈表變成樹結(jié)構(gòu)：
有關(guān)紅黑樹的介紹：
【老實李】JDK1.8中HashMap的紅黑樹 - 簡書 (jianshu.com) //這個只是說明白了一小部分
解讀HashMap中的紅黑樹操作 - 知乎 (zhihu.com) // 這個講的比較深入。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) { //開始遍歷并且格式化之前創(chuàng)建的 樹結(jié)構(gòu)
next = (TreeNode<K,V>)x.next;
x.left = x.right = null; //首先將當前樹的左右二叉樹置為空
if (root == null) { //第一次進行的時候，這里就將第一個作為當前樹的跟。
x.parent = null;
x.red = false; //紅黑樹根節(jié)點必須是黑的
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
以上，分析了HashMap的插入方法，
- 第一次存放數(shù)據(jù)的時候，首先創(chuàng)建一個數(shù)組，（默認數(shù)組長度為16， 默認加載因子為0.75）
- HashMap通過特殊的hash算法盡可能的減少Hash碰撞。 // keyhash值得前16位和16位異或，然后取與當前容量，就是當前節(jié)點得index值
- 如果出現(xiàn)hash碰撞，那么就將相同 index位置變成一條鏈表
- 如果鏈表長度較長（>=8），并且當前hashMap得容量超過 64，那么就需要將當前鏈表變成一個紅黑樹結(jié)構(gòu)，同時又由于紅黑樹得自平衡性，可以保證查找刪除等操作得時間復雜度在 O(logn)
3.3 HashMap.remove()
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { //tab不為空并且數(shù)組長度>0,
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;//找到節(jié)點
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//找到樹結(jié)構(gòu)得節(jié)點
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;//找到鏈表結(jié)構(gòu)的節(jié)點
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //樹節(jié)點需要特殊處理
else if (node == p)
tab[index] = node.next;//如果是鏈表的第一個，那么就直接移除
else
p.next = node.next;//如果是鏈表中間的一個，那么就刪除中間的
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
總結(jié)
HashMap在進行數(shù)據(jù)存儲的時候使用了盡可能減少碰撞的hash算法，同時 使用了 數(shù)組、鏈表、紅黑樹的數(shù)據(jù)結(jié)構(gòu)，盡可能的將性能和空間進行平衡，這也體現(xiàn)了源碼工程師的智慧
