資料：
HashMap和HashTable到底哪不同痕慢？
Java集合——HashMap念搬、HashTable以及ConCurrentHashMap異同比較
簡介
版本：HashTable產(chǎn)生于JDK 1.1抑堡，而HashMap產(chǎn)生于JDK 1.2
HashMap和HashTable的相同點：
HashMap和HashTable都是基于哈希表來實現(xiàn)鍵值映射的工具類，HashTable和HashMap采用相同的存儲機制朗徊，二者的實現(xiàn)基本一致
HashMap和HashTable的區(qū)別：
（1）HashMap是非線程安全的首妖，HashTable是線程安全的。
（2）HashMap的鍵和值都允許有null存在爷恳，而HashTable則都不行有缆。
（3）因為線程安全、哈希效率的問題温亲，HashMap效率比HashTable的要高棚壁。
擴容方式：
HashMap的擴容方式是：默認大小是16，擴容規(guī)則：2的指數(shù)倍
HashMap的哈希算法：采用位運算栈虚，比取模運算效率更高袖外，同樣能達到使其分布均勻的目的HashTable的擴容方式是：默認大小是11，擴容規(guī)則：n*2+1
即就是：hash() * (length - 1)來定位數(shù)組下標
在保證數(shù)組長度為2的冪次方的時候魂务，使用hash()運算之后的值與運算（&）（數(shù)組長度 - 1）來獲取數(shù)組下標的方式進行存儲曼验，這樣一來是比取余操作更加有效率泌射，二來也是因為只有當數(shù)組長度為2的冪次方時，h&(length-1)才等價于h%length鬓照，三來解決了“哈希值與數(shù)組大小范圍不匹配”的問題熔酷；
???
HashTable和ConCurrentHashMap的對比：
ConcurrentHashMap它是線程安全的HashMap的實現(xiàn)。
HashTable里使用的是synchronized關鍵字颖杏，這其實是對對象加鎖纯陨，鎖住的都是對象整體，當Hashtable的大小增加到一定的時候留储，性能會急劇下降翼抠，因為迭代時需要被鎖定很長的時間。ConcurrentHashMap算是對上述問題的優(yōu)化获讳。
ConcurrentHashMap對整個桶數(shù)組進行了分割分段(Segment)阴颖，然后在每一個分段上都用lock鎖進行保護，相對于HashTable的syn關鍵字鎖的粒度更精細了一些丐膝，并發(fā)性能更好量愧，而HashMap沒有鎖機制，不是線程安全的帅矗。
在JDK1.8中偎肃，放棄了Segment臃腫的設計，取而代之的是采用Node + CAS + Synchronized來保證并發(fā)安全進行實現(xiàn)浑此，
對外的接口（API）
雖然都實現(xiàn)了Map累颂、Cloneable、Serializable三個接口凛俱。但是HashMap繼承自抽象類AbstractMap紊馏，而HashTable繼承自抽象類Dictionary（Dictionary已經(jīng)廢棄使用了）。
異同比較：
從公開的方法上來看蒲犬，這兩個類提供的朱监，是一樣的功能。都提供鍵值映射的服務原叮，可以增赫编、刪、查奋隶、改鍵值對沛慢，可以對建、值达布、鍵值對提供遍歷視圖。支持淺拷貝逾冬，支持序列化黍聂。
Null Key & Null Value
HashTable不支持null鍵和null值躺苦，當HashTable在遇到null時，會拋出NullPointerException異常产还。
##java.util.Hashtable
public synchronized V put(K key, V value) {
// 如果value為null匹厘，拋出NullPointerException
if (value == null) {
throw new NullPointerException();
}
// 如果key為null，在調(diào)用key.hashCode()時拋出NullPointerException
// ...
}
HashMap是允許key和value為空的脐区，這是因為HashMap在實現(xiàn)時對null做了特殊處理愈诚，將null的hashCode值定為了0，從而將其存放在哈希表的第0個bucket中牛隅。
以下代碼及注釋來自java.util.HasMap
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 當key為null時炕柔，調(diào)用putForNullKey特殊處理
if (key == null)
return putForNullKey(value);
// ...
}
private V putForNullKey(V value) {
// key為null時，放到table[0]也就是第0個bucket中
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
HashMap介紹
1 HashMap數(shù)據(jù)結(jié)構(gòu)
總述：
數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表 數(shù)組=桶 鏈表存Entry(鍵值對)
Java中的數(shù)據(jù)存儲方式有兩種結(jié)構(gòu)：
一種是數(shù)組：數(shù)組是空間連續(xù)媒佣，尋址迅速匕累，但是在增刪元素的時候會有較大幅度的移動，所以數(shù)組的特點是查詢速度快默伍，增刪慢欢嘿。
一種是鏈表：鏈表空間可以不連續(xù)，查詢需要順序查找也糊，增刪元素只需修改指針炼蹦；所以鏈表的特點是查詢速度慢、增刪快狸剃。
那么有沒有一種數(shù)據(jù)結(jié)構(gòu)來綜合一下數(shù)組和鏈表以便發(fā)揮他們各自的優(yōu)勢掐隐？答案就是哈希表。哈希表的存儲結(jié)構(gòu)如下圖所示：
上圖畫出的是一個桶數(shù)量為8捕捂，存有5個鍵值對的HashMap/HashTable的內(nèi)存布局情況瑟枫。可以看到HashMap/HashTable內(nèi)部創(chuàng)建有一個Entry類型的引用數(shù)組指攒，用來表示哈希表慷妙，數(shù)組的長度，即是哈希桶的數(shù)量允悦。而數(shù)組的每一個元素都是一個Entry引用膝擂，從Entry對象的屬性里，也可以看出其是鏈表的節(jié)點隙弛，每一個Entry對象內(nèi)部又含有另一個Entry對象的引用架馋。
這樣就可以得出結(jié)論，HashMap/HashTable內(nèi)部用Entry數(shù)組實現(xiàn)哈希表全闷，而對于映射到同一個哈希桶（數(shù)組的同一個位置）的鍵值對叉寂，使用Entry鏈表來存儲(解決hash沖突)。
Entry對象源碼
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash; //鍵對象的hash值
final K key; 鍵對象
V value;
Entry<K,V> next;
/*
* Entry對象唯一表示一個鍵值對总珠，有四個屬性
* hash ：鍵對象的hash值
* key： 鍵對象
* value：值對象
* next：指向鏈表中下一個Entry對象屏鳍，可為null勘纯，表示當前Entry對象在鏈表尾部
*/
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
....
}
2 HashMap擴容方式
總述
HashMap的擴容方式是：默認大小是16，擴容規(guī)則：2的指數(shù)倍
HashMap的哈希算法：采用位運算钓瞭，比取模運算效率更高驳遵，同樣能達到使其分布均勻的目的
HashMap和HashTable源碼
resize()
HashMap存在擴容的情況，對應的方法為HashMap中的resize方法：
//Node<K, V>[] java.util.HashMap.resize()
/**
* 該函數(shù)有2中使用情況：1.初始化哈希表山涡；2.當前數(shù)組容量過小堤结，需要擴容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;// 擴容前的數(shù)組（當前數(shù)組）
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 擴容前的數(shù)組容量（數(shù)組長度）
int oldThr = threshold;// 擴容前數(shù)組的閾值
int newCap, newThr = 0;
if (oldCap > 0) {
// 針對情況2：若擴容前的數(shù)組容量超過最大值，則不再擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 針對情況2：若沒有超過最大值鸭丛，就擴容為原來的2倍（左移1位）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 針對情況1：初始化哈希表（采用指定或者使用默認值的方式）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize上限
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];
table = newTab;
if (oldTab != null) {
// 把每一個bucket都移動到新的bucket中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
hash()函數(shù)
上面提到的問題竞穷，主要是因為如果使用hashCode取余，那么相當于參與運算的只有hashCode的低位系吩，高位是沒有起到任何作用的来庭，所以我們的思路就是讓hashCode取值出的高位也參與運算，進一步降低hash碰撞的概率穿挨，使得數(shù)據(jù)分布更平均月弛，我們把這樣的操作稱為擾動，在JDK 1.8中的hash()函數(shù)如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這比在JDK 1.7中科盛，更為簡潔帽衙，相比在1.7中的4次位運算，5次異或運算（9次擾動）;
在1.8中贞绵，只進行了1次位運算和1次異或運算（2次擾動）厉萝；
總結(jié)
簡單總結(jié)一下HashMap是使用了哪些方法來有效解決哈希沖突的：
- 使用鏈地址法（使用散列表）來鏈接擁有相同hash值的數(shù)據(jù)；
- 使用2次擾動函數(shù)（hash函數(shù)）來降低哈希沖突的概率榨崩，使得數(shù)據(jù)分布更平均谴垫；
- 引入紅黑樹進一步降低遍歷的時間復雜度，使得遍歷更快母蛛；
