一、HashMap的數(shù)據(jù)結(jié)構(gòu)
java編程語言中，最基本的數(shù)據(jù)結(jié)構(gòu)就兩種。一個是數(shù)組，另外一個是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的，hashmap也不例外。Hashmap實(shí)際上是一個數(shù)組和鏈表的結(jié)合體。IDK1.8里面對HaspMap做了一個更新，采用了數(shù)組+鏈表+紅黑樹，為什么要做更新呢？因?yàn)閿?shù)組加鏈表，即使哈希函數(shù)取得再好，也很難達(dá)到元素百分百均勻分布，當(dāng) HashMap 中有大量的元素都存放到同一個桶中時，這個桶下有一條長長的鏈表，這個時候 HashMap 就相當(dāng)于一個單鏈表，假如單鏈表有 n 個元素，遍歷的時間復(fù)雜度就是 O(n)，完全失去了它的優(yōu)勢。針對這種情況，JDK 1.8 中引入了紅黑樹（查找時間復(fù)雜度為 O(logn)）來優(yōu)化這個問題,當(dāng)桶中的元素元素大于八個時就會轉(zhuǎn)化為紅黑樹。圖中的紅色小圓點(diǎn)即代表一個key-value。
HashMap的工作原理
HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當(dāng)我們將鍵值對傳遞給put()方法時，它調(diào)用鍵對象的hashCode()方法來計(jì)算hashcode，讓后找到bucket位置來儲存值對象。當(dāng)獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當(dāng)發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點(diǎn)中。 HashMap在每個鏈表節(jié)點(diǎn)中儲存鍵值對對象。
當(dāng)兩個不同的鍵對象的hashcode相同時會發(fā)生什么？ 它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。
因?yàn)镠ashMap的好處非常多，我曾經(jīng)在電子商務(wù)的應(yīng)用中使用HashMap作為緩存。因?yàn)榻鹑陬I(lǐng)域非常多的運(yùn)用Java，也出于性能的考慮，我們會經(jīng)常用到HashMap和ConcurrentHashMap。
HashMap源代碼
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; #aka 16,初始容量為16
static final int MAXIMUM_CAPACITY = 1 << 30; #最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; # 擴(kuò)容因子
The bin count threshold for using a tree rather than list for a bin.
static final int TREEIFY_THRESHOLD = 8;
HashMap結(jié)構(gòu)圖
新增的紅黑樹代碼如下
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
紅黑樹這塊，JDK1.8更新了一個重要的操作----桶的樹形化treeifyBin()
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)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
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);
}
}
// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
二、HashMap的get操作
HashMap的hashcode的作用
hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，
hashCode是用來在散列存儲結(jié)構(gòu)中確定對象的存儲地址的。
如果兩個對象相同，就是適用于equals(java.lang.Object) 方法，那么這兩個對象的hashCode一定要相同。
兩個對象的hashCode相同，并不一定表示兩個對象就相同，也就是不一定適用于equals(java.lang.Object) 方法，
只能夠說明這兩個對象在散列存儲結(jié)構(gòu)中，如Hashtable，他們“存放在同一個籃子里”。
例如內(nèi)存中有這樣的位置
0 1 2 3 4 5 6 7
而我有個類，這個類有個字段叫ID，我要把這個類存放在以上8個位置之一，如果不用HashCode而任意存放，
那么當(dāng)查找時就需要到這八個位置里挨個去找，或者用二分法一類的算法。
但以上問題如果用HashCode就會使效率提高很多
定義我們的HashCode為ID％8，比如我們的ID為9，9除8的余數(shù)為1，那么我們就把該類存在1這個位置，
如果ID是13，求得的余數(shù)是5，那么我們就把該類放在5這個位置。依此類推。
但是如果兩個類有相同的HashCode，例如9除以8和17除以8的余數(shù)都是1，
也就是說，我們先通過HashCode來判斷兩個類是否存放某個桶里，但這個桶里可能有很多類，
那么我們就需要再通過equals在這個桶里找到我們要的類。
equals相等，hashcode必相等；hashcode相等，equals可能不相等。
Q:為什么需要hashCode?
1、通過hashCode可以很快的查到小內(nèi)存塊。
2、通過hashCode比較比equal方法快，當(dāng)get時先比較hashCode，如果hashCode不同，直接返回false。
Q:HashMap和HashTable的區(qū)別
Hashtable是基于陳舊的Dictionary類的，HashMap是Java 1.2引進(jìn)的Map接口的一個實(shí)現(xiàn)，它們都是集合中將數(shù)據(jù)無序存放的。
1、hashMap去掉了HashTable的contains方法，但是加上了containsValue()和containsKey()方法，HashTable Synchronize同步的，線程安全，HashTable不允許空鍵值為空，效率低。
HashMap 非Synchronize線程同步的，線程不安全，HashMap允許空鍵值為空，效率高。
查看Hashtable的源代碼就可以發(fā)現(xiàn)，除構(gòu)造函數(shù)外，Hashtable的所有 public 方法聲明中都有 synchronized 關(guān)鍵字，而HashMap的源代碼中則連 synchronized 的影子都沒有
2、Hashtable不允許 null 值(key 和 value 都不可以)，HashMap允許 null 值(key和value都可以)。
3、兩者的遍歷方式大同小異，Hashtable僅僅比HashMap多一個elements方法。
Hashtable table = new Hashtable();
table.put("key", "value");
Enumeration em = table.elements();
while (em.hasMoreElements()) {
String obj = (String) em.nextElement();
System.out.println(obj);
}
4、HashTable使用Enumeration，HashMap使用Iterator
Q:HashMap與LinkedHashMap,和TreeMap的區(qū)別。
共同點(diǎn)：
HashMap,LinkedHashMap,TreeMap都屬于Map的實(shí)現(xiàn)類.
不同點(diǎn):
1.HashMap不保證順序，即為無序的，具有很快的訪問速度，HashMap最多只允許一條記錄的鍵為Null，允許多條記錄的值為 Null。
2.TreeMap實(shí)現(xiàn)SortMap接口，能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器，當(dāng)用Iterator遍歷TreeMap時，得到的記錄是排過序的。TreeMap取出來的是排序后的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好。
3.LinkedHashMap 是HashMap的一個子類，LinkedHashMap可以保證HashMap集合有序，存入的順序和取出的順序一致,如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實(shí)現(xiàn)。
如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好。
如果需要輸出的順序和輸入的相同,那么用LinkedHashMap 可以實(shí)現(xiàn),它還可以按讀取順序來排列。
Q:HashMap和ConcurrentHashMap的區(qū)別
1、HashMap不是線程安全的，而ConcurrentHashMap是線程安全的。
2、ConcurrentHashMap采用鎖分段技術(shù)，將整個Hash桶進(jìn)行了分段segment，也就是將這個大的數(shù)組分成了幾個小的片段segment，而且每個小的片段segment上面都有鎖存在，那么在插入元素的時候就需要先找到應(yīng)該插入到哪一個片段segment，然后再在這個片段上面進(jìn)行插入，而且這里還需要獲取segment鎖。
3、ConcurrentHashMap讓鎖的粒度更精細(xì)一些，并發(fā)性能更好。
Q:get原理
通過hash獲得對應(yīng)數(shù)組位置，遍歷該數(shù)組所在鏈表（key.equals（））
Q:hashcode相同，沖突怎么辦？
“頭插法”，放到對應(yīng)的鏈表的頭部。
為什么是頭插法（其設(shè)計(jì)原理是什么）？
因?yàn)镠ashMap的發(fā)明者認(rèn)為，后插入的Entry被查找的可能性更大（因?yàn)間et查詢的時候會遍歷整個鏈表）。
Q:JDK1.7的hashmap和JDK1.8的hashmap的區(qū)別（即1.8做了哪些優(yōu)化）？
為了加快查詢效率，java8的hashmap引入了紅黑樹結(jié)構(gòu)，當(dāng)數(shù)組長度大于默認(rèn)閾值64時，且當(dāng)某一鏈表的元素>8時，該鏈表就會轉(zhuǎn)成紅黑樹結(jié)構(gòu)，查詢效率更高。（問題來了，什么是紅黑樹？什么是B+樹？（mysql索引有B+樹索引）什么是B樹？什么是二叉查找樹？）
這里只簡單的介紹一下：紅黑樹是一種自平衡二叉樹，擁有優(yōu)秀的查詢和插入/刪除性能，廣泛應(yīng)用于關(guān)聯(lián)數(shù)組。
