HashMap是Java集合框架（Java Collection Framework， JCF）中一個基礎類，它在1998年12月，加入到Java 2版本中。在此之後，Map接口本身除了在Java 5中引入了泛型以外，再沒有發生過明顯變化。然而HashMap的實現，則為了提升性能，不斷地在改變。
在正式學習HashMap源碼之前，先復習一下hash表的實現。
哈希表（Hash table，也叫散列表），是根據關鍵字值（key,value）直接進行訪問的數據結構。也就是說，它通過把關鍵字映射到表中一個位置來訪問的紀錄，以加快查找的速度。這個映射函數叫做散列函數，存放紀錄的數組叫散列表。
取關鍵字或關鍵字的某個線性函數值為哈希地址。
H(key) = key 或 H(key) = a*key+b 取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址。對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞.
H(key) = key % p （p<=m）當無法確定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然後按需要取平方值的中間幾位作為哈希地址。這是因為：平方後中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的概率產生不同的哈希地址。
H(key) = ((key * Key) >> X) << Y和平方散列法類似，此種方法使用斐波那契數列的值作為乘數而不是自己。
對於16位整數而言，這個乘數是40503。
對於32位整數而言，這個乘數是2654435769。
對於64位整數而言，這個乘數是11400714819323198485。
H(key) = ((key * 2654435769) >> X) << Y開放尋址法把所有的元素都存放在散列表中，也就是每個表項包含動態集合的一個元素（元素可以為NULL）。
1.在開放尋址法中，當要插入一個元素時，可以連續地檢查散列表的個各項（連續檢查是可以通過不同的算法獲得偏移位），直到找到一個空槽來放置這個元素為止。
2.當查找一個元素時，要檢查所有的表項，直到找到所需的元素，或者最終發現元素不在表中。
3.在開放尋址法中，對散列表元素的刪除操作執行起來比較困難。當我們從槽i中刪除關鍵字時，不能僅將此位置元素置空。因為這樣做的話，會導致在無法判斷此位置是否有元素。應該用個特殊的值表示該元素已經刪除。
Hi=(H(key) + di) MOD m , [i=1,2，…，k(k<=m-1)]其中H(key）為散列函數，m為散列表長，di為增量序列，可有下列三種取法:
di=1,2,3，…，m-1，稱線性探測再散列。
di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）稱二次探測再散列。
di=偽隨機數序列，稱偽隨機探測再散列。
產生碰撞時，再使用另一個散列函數計算地址，直到碰撞不再發生，這種方法不易產生“聚集”，但增加了計算時間（一個地址的產生可能會經過多個散列函數的計算）
Hi=Hn(key), [n=1,2 ...,]有一個包含一組哈希函數 H1…Hn 的集合。當需要從哈希表中添加或獲取元素時，首先使用哈希函數 H1。如果導致碰撞，則嘗試使用 H2，以此類推，直到 Hn。所有的哈希函數都與 H1 十分相似，不同的是它們選用的乘法因子。
產生碰撞時，把哈希到同一個槽中的所有元素都放到一個鏈表中。拉鏈法采用額外的數據結構來處理碰撞，其將哈希表中每個位置（slot）都映射到了一個鏈表。
建立一個公共溢出區，當發生碰撞時，把碰撞元素放到緩沖區。
負載因子(load factor)，它用來衡量哈希表的 空/滿 程度，一定程度上也可以體現查詢的效率，
計算公式為:
負載因子 = 總鍵值對數 / 箱子個數負載因子越大，意味著哈希表越滿，越容易導致沖突，性能也就越低。因此，一般來說，當負載因子大於某個常數(可能是 1，或者 0.75 等)時，哈希表將自動擴容。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable, Serializable {
/**
默認的哈希表的負載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
hashMap的最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
hashMap的默認容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
HashMap要調整的下一個容量大小
*/
int threshold;
/**
hashMap容量的變量
*/
int threshold;
/**
哈希表負載因子的變量
*/
final float loadFactor;
/**
構造一個具有默認初始容量 (16) 和默認加載因子 (0.75) 的 HashMap
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
構造一個帶指定初始容量和默認加載因子 (0.75) 的 HashMap。
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
構造一個帶指定初始容量和加載因子的 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;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
返回給定容量大小的下一個容量。
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
構造map的結構或者將map的內容全部賦值
evict 初始化hashMap時是false，其余的情況為true。
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size 初始化空間
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold) //重新調整空間
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
}HashMap實現了Map接口，繼承AbstractMap。其中Map接口定義了鍵映射到值的規則，而AbstractMap類提供 Map 接口的骨干實現，以最大限度地減少實現此接口所需的工作。
在這裡提到了兩個參數：初始容量，加載因子。這兩個參數是影響HashMap性能的重要參數，其中容量表示哈希表中桶的數量，初始容量是創建哈希表時的容量，加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。對於使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)，因此如果負載因子越大，對空間的利用更充分，然而後果是查找效率的降低；如果負載因子太小，那麼散列表的數據將過於稀疏，對空間造成嚴重浪費。系統默認負載因子為0.75，一般情況下我們是無需修改的。
HashMap是基於哈希表存儲“Key－Value”對象應用的數據結構。存入HashMap的鍵必須具備兩個關鍵函數：
（1）equals()：判斷兩個Key是否相同，用來保證存入的Key的唯一性；
（2）hashCode()：genj key-value對象的Key來計算其引用在散列表中存放的位置。
transient Node<K,V>[] table; static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
總結：
1.HashMap中有一個叫table的Node數組。
2.這個數組存儲了Node類的對象。HashMap類有一個叫做Node的內部類。這個Node類包含了key-value作為實例變量。
3.每當往Hashmap裡面存放key-value對的時候，都會為它們實例化一個Node對象，這個Node對象就會存儲在前面提到的Node數組table中。根據key的hashcode()方法計算出來的hash值來決定。 hash值用來計算key在Entry數組的索引。
//不使用紅黑樹的閥值
static final int UNTREEIFY_THRESHOLD = 6;
//使用紅黑樹的閥值
static final int TREEIFY_THRESHOLD = 8;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//hash表達到最大時，返回舊的hash表。
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
//初始化帶指定容量因子和碰撞因子的hashmap。
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//默認初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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) {
//循環遍歷，將舊的hash表中的數據復制到新的hash表中。
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;
//用(e.hash & oldCap)規則切割鏈表，為零在loHead，否則在hiHead
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;
}
//拆分紅黑樹
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//UNTREEIFY_THRESHOLD 使用紅黑樹的閥值
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
//鏈表構造法
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
//紅黑樹的構造方法
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
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);
}當哈希表的容量超過默認容量時，必須調整table的大小。當容量已經達到最大可能值時，那麼該方法就將容量調整到Integer.MAX_VALUE返回，這時，需要創建一張新表，將原表的映射到新表中。
http://www.cnblogs.com/huaizuo/p/5371099.html 紅黑樹hash的計算方法。
/**
對外暴露的方法。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
對key進行散列
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
objec 中hashcode的實現，native關鍵字這裡代表了有操作系統進行實現。
*/
public native int hashCode();
/**
hash -->key對應的hash值
value-->對應的值
onlyIfAbsent-->true，不改變已經存在的值
evict-->false,該表再創建模式
*/
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
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);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}put方法的基本過程如下：
（1）對key的hashcode進行hash計算，獲取應該保存到數組中的index。
（2）判斷index所指向的數組元素是否為空，如果為空則直接插入。
（3）如果不為空，則依次查找entry中next所指定的元素，判讀key是否相等，如果相等，則替換舊的值，返回。
（4）如果都不相等，則將此鏈表頭元素賦值給待插入Node的next變量，讓後將待插入元素插入到Node數組中去。
(5)Java 8 在沒有降低哈希沖突的度的情況下，使用紅黑書代替鏈表，
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
```
展示了Java 8的HashMap在使用樹和使用鏈表之間切換的阈值。當沖突的元素數增加到8時，鏈表變為樹；當減少至6時，樹切換為鏈表。中間有2個緩沖值的原因是避免頻繁的切換浪費計算機資源。
Java 8 HashMap使用的樹是紅黑樹，它的實現基本與JCF中的TreeMap相同。通常，樹的有序性通過兩個或更多對象比較大小來保證。Java 8 HashMap中的樹也通過對象的Hash值（這個hash值與哈希桶索引值不同，索引值在這個hash值的基礎上對桶大小M取模，譯者注）作為對象的排序鍵。因為使用Hash值作為排序鍵打破了Total Ordering（可以理解為數學中的小於等於關系，譯者注），因此這裡有一個tieBreakOrder()方法來處理這個問題。
###2.2.5 get 方法public V get(Object key) {
Node
從上面的代碼以及注釋中可以看出，get操作還是比較簡單的，先是根據key進行hash映射，得到其在table中的index，然後遍歷真個Entry[index]鏈表。
##3.java 關鍵字
###3.1 transient的作用及使用方法
一個對象只要實現了Serilizable接口，這個對象就可以被序列化。將不需要序列化的屬性前添加關鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目的地中。
1）一旦變量被transient修飾，變量將不再是對象持久化的一部分，該變量內容在序列化後無法獲得訪問。
2）transient關鍵字只能修飾變量，而不能修飾方法和類。注意，本地變量是不能被transient關鍵字修飾的。變量如果是用戶自定義類變量，則該類需要實現Serializable接口。
3）被transient關鍵字修飾的變量不再能被序列化，一個靜態變量不管是否被transient修飾，均不能被序列化。
例外情況：
對象的序列化可以通過實現兩種接口來實現，若實現的是Serializable接口，則所有的序列化將會自動進行，若實現的是Externalizable接口，則沒有任何東西可以自動序列化，需要在writeExternal方法中進行手工指定所要序列化的變量，這與是否被transient修飾無關。
###3.2 native關鍵字
1。native 是用做java 和其他語言（如c++）進行協作時用的也就是native 後的函數的實現不是用java寫的。
2。既然都不是java，那就別管它的源代碼了
##4.hashMap與hashSet的區別public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable
{
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
}
由上面源程序可以看出，HashSet 的實現其實非常簡單，它只是封裝了一個 HashMap 對象來存儲所有的集合元素，所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存，而 HashMap 的 value 則存儲了一個 PRESENT，它是一個靜態的 Object 對象。
##5.HashMap與HashTablepublic class Hashtable
1.HashTable是一個線程安全的API，它的方法通過synchronized關鍵字進行修飾。盡管並不推薦使用HashTable來開發一個高性能的應用，但是它確實能夠保證你的應用線程安全。相反，HashMap並不保證線程安全。因此當你構建一個多線程應用時，請使用ConcurrentHashMap。
2.關聯數組與數組最大的不同，就是對於每一個數據，關聯數組會有一個key與之關聯，當使用關聯數組時，每個數據都可以通過對應的Key來獲取。關聯數組有許多別名，比如Map（映射）、Dictionary（字典）和Symbol-Table（符號表）。盡管名字不同，他們的含義都是相同的。
3.字典和符號表都是非常直觀的術語，無須解釋它們的行為。映射來自於數學領域。在函數中，一個域（集合）中的值被與另一個域（集合）中的值關聯，這種關聯關系叫做映射。
##6 HashMap與線程安全
HashMap底層的數據結構是一個Entry數組，通過對key值進行hash映射，確定key-value對的存放位置。當多個不同key映射到同一個hash值時，它們在Entry數組中以鏈表的形式存在，新加入的元素會放在鏈表的頭部。
可見HashMap的線程不安全的主要原因是HashMap的結構發生了變化，而從上一篇文章中可以知道，HashMap的結構變化發生在數組容量變更時，即當數組元素個數超過了阈值threshold=capacity*loadFactor時，HashMap將resize()
#####2.2.3.1單線程下單擴容
#####2.2.3.2多線程下單擴容
#####2.2.3.3線程不安全的表現
1、多線程put操作後，get操作導致死循環。
2、多線程put非NULL元素後，get操作得到NULL值。
3、多線程put操作，導致元素丟失。
###如何安全的使用HashMap
1.Hashtable
2.ConcurrentHashMap
3.Synchronized Map
###Hashtable
HashMap是Java 1.2引進的Map接口的一個實現。HashMap是新框架中用來代替Hashtable的類，也就是說建議使用HashMap，不要使用Hashtable。
Hashtable的方法是同步的，HashMap未經同步，所以在多線程場合要手動同步HashMap這個區別就像Vector和ArrayList一樣。查看Hashtable的源代碼就可以發現，除構造函數外，Hashtable的所有 public 方法聲明中都有 synchronized 關鍵字，而HashMap的源代碼中則連 synchronized 的影子都沒有，當然，注釋除外。HashTable源碼中是使用synchronized來保證線程安全的，
###ConcurrentHashMap
多線程操作要格外小心。知道JDK 1.5引入了ConcurrentHashMap才使得Map重新能夠安全的在多線程下操作了。
ConcurrentHashMap具體是怎麼實現線程安全的呢，肯定不可能是每個方法加synchronized，那樣就變成了HashTable。
從ConcurrentHashMap代碼中可以看出，它引入了一個“分段鎖”的概念，具體可以理解為把一個大的Map拆分成N個小的HashTable，根據key.hashCode()來決定把key放到哪個HashTable中。
在ConcurrentHashMap中，就是把Map分成了N個Segment，put和get的時候，都是現根據key.hashCode()算出放到哪個Segment中：
###SynchronizedMap
/**
*性能對比例程
*/
public class CrunchifyConcurrentHashMapVsSynchronizedMap {
public final static int THREAD_POOL_SIZE = 5;
public static Map<String, Integer> crunchifyHashTableObject = null;
public static Map<String, Integer> crunchifySynchronizedMapObject = null;
public static Map<String, Integer> crunchifyConcurrentHashMapObject = null;
public static void main(String[] args) throws InterruptedException {
// Test with Hashtable Object
crunchifyHashTableObject = new Hashtable<>();
crunchifyPerformTest(crunchifyHashTableObject);
// Test with synchronizedMap Object
crunchifySynchronizedMapObject = Collections.synchronizedMap(new HashMap<String, Integer>());
crunchifyPerformTest(crunchifySynchronizedMapObject);
// Test with ConcurrentHashMap Object
crunchifyConcurrentHashMapObject = new ConcurrentHashMap<>();
crunchifyPerformTest(crunchifyConcurrentHashMapObject);
}
public static void crunchifyPerformTest(final Map<String, Integer> crunchifyThreads) throws InterruptedException {
System.out.println("Test started for: " + crunchifyThreads.getClass());
long averageTime = 0;
for (int i = 0; i < 5; i++) {
long startTime = System.nanoTime();
ExecutorService crunchifyExServer = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
for (int j = 0; j < THREAD_POOL_SIZE; j++) {
crunchifyExServer.execute(new Runnable() {
@SuppressWarnings("unused")
@Override
public void run() {
for (int i = 0; i < 500000; i++) {
Integer crunchifyRandomNumber = (int) Math.ceil(Math.random() * 550000);
// Retrieve value. We are not using it anywhere
Integer crunchifyValue = crunchifyThreads.get(String.valueOf(crunchifyRandomNumber));
// Put value
crunchifyThreads.put(String.valueOf(crunchifyRandomNumber), crunchifyRandomNumber);
}
}
});
}
// Make sure executor stops
crunchifyExServer.shutdown();
// Blocks until all tasks have completed execution after a shutdown request
crunchifyExServer.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
long entTime = System.nanoTime();
long totalTime = (entTime - startTime) / 1000000L;
averageTime += totalTime;
System.out.println("2500K entried added/retrieved in " + totalTime + " ms");
}
System.out.println("For " + crunchifyThreads.getClass() + " the average time is " + averageTime / 5 + " ms\n");
}
}
##Redis
Redis 是一個高效的 key-value 緩存系統，也可以理解為基於鍵值對的數據庫。它對哈希表的設計有非常多值得學習的地方，在不影響源代碼邏輯的前提下我會盡可能簡化，突出重點。
數據結構
在 Redis 中，字典是一個 dict 類型的結構體，定義在 src/dict.h 中:
typedef struct dict {
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
這裡的 dictht 是用於存儲數據的結構體。注意到我們定義了一個長度為 2 的數組，它是為了解決擴容時速度較慢而引入的，其原理後面會詳細介紹，rehashidx 也是在擴容時需要用到。先看一下 dictht 的定義:
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long used;
} dictht;
可見結構體中有一個二維數組 table，元素類型是 dictEntry，對應著存儲的一個鍵值對:
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
從 next 指針以及二維數組可以看出，Redis 的哈希表采用拉鏈法解決沖突。
添加元素
向字典中添加鍵值對的底層實現如下:
dictEntry *dictAddRaw(dict *d, void *key) {
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
dictSetKey(d, entry, key);
return entry;
}
dictIsRehashing 函數用來判斷哈希表是否正在重新哈希。所謂的重新哈希是指在擴容時，原來的鍵值對需要改變位置。為了優化重哈希的體驗，Redis 每次只會移動一個箱子中的內容，下一節會做詳細解釋。
仔細閱讀指針操作部分就會發現，新插入的鍵值對會放在箱子中鏈表的頭部，而不是在尾部繼續插入。這個細節上的改動至少帶來兩個好處:
找到鏈表尾部的時間復雜度是 O(n)，或者需要使用額外的內存地址來保存鏈表尾部的位置。頭插法可以節省插入耗時。
對於一個數據庫系統來說，最新插入的數據往往更有可能頻繁的被獲取。頭插法可以節省查找耗時。
增量式擴容
所謂的增量式擴容是指，當需要重哈希時，每次只遷移一個箱子裡的鏈表，這樣擴容時不會出現性能的大幅度下降。
為了標記哈希表正處於擴容階段，我們在 dict 結構體中使用 rehashidx 來表示當前正在遷移哪個箱子裡的數據。由於在結構體中實際上有兩個哈希表，如果添加新的鍵值對時哈希表正在擴容，我們首先從第一個哈希表中遷移一個箱子的數據到第二個哈希表中，然後鍵值對會被插入到第二個哈希表中。
在上面給出的 dictAddRaw 方法的實現中，有兩句代碼:
if (dictIsRehashing(d)) _dictRehashStep(d);
// …
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
第二句就是用來選擇插入到哪個哈希表中，第一句話則是遷移 rehashidx 位置上的鏈表。它實際上會調用 dictRehash(d,1)，也就是說是單步長的遷移。dictRehash 函數的實現如下:
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
unsigned int h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
return 1;
}
這段代碼比較長，但是並不難理解。它由一個 while 循環和 if 語句組成。在單步遷移的情況下，最外層的 while 循環沒有意義，而它內部又可以分為兩個 while 循環。
第一個循環用來更新 rehashidx 的值，因為有些箱子為空，所以 rehashidx 並非每次都比原來前進一個位置，而是有可能前進幾個位置，但最多不超過 10。第二個循環則用來復制鏈表數據。
最外面的 if 判斷中，如果發現舊哈希表已經全部完成遷移，就會釋放舊哈希表的內存，同時把新的哈希表賦值給舊的哈希表，最後把 rehashidx 重新設置為 -1，表示重哈希過程結束。
默認哈希函數
與 Java 不同的是，Redis 提供了 void * 類型 key 的哈希函數，也就是通過任何類型的 key 的指針都可以求出哈希值。具體算法定義在 dictGenHashFunction 函數中，由於代碼過長，而且都是一些位運算，就不展示了。
它的實現原理是根據指針地址和這一塊內存的長度，獲取內存中的值，並且放入到一個數組當中，可見這個數組僅由 0 和 1 構成。然後再對這些數字做哈希運算。因此即使兩個指針指向的地址不同，但只要其中內容相同，就可以得到相同的哈希值。
歸納對比
首先我們回顧一下 Java 和 Redis 的解決方案。
Java 的長處在於當哈希函數不合理導致鏈表過長時，會使用紅黑樹來保證插入和查找的效率。缺點是當哈希表比較大時，如果擴容會導致瞬時效率降低。
Redis 通過增量式擴容解決了這個缺點，同時拉鏈法的實現(放在鏈表頭部)值得我們學習。Redis 還提供了一個經過嚴格測試，表現良好的默認哈希函數，避免了鏈表過長的問題。
Objective-C 的實現和 Java 比較類似，當我們需要重寫 isEqual() 方法時，還需要重寫 hash 方法。這兩種語言並沒有提供一個通用的、默認的哈希函數，主要是考慮到 isEqual() 方法可能會被重寫，兩個內存數據不同的對象可能在語義上被認為是相同的。如果使用默認的哈希函數就會得到不同的哈希值，這兩個對象就會同時被添加到 NSSet 集合中，這可能違背我們的期望結果。
根據我的了解，Redis 並不支持重寫哈希方法，難道 Redis 就沒有考慮到這個問題麼？實際上還要從 Redis 的定位說起。由於它是一個高效的，Key-Value 存儲系統，它的 key 並不會是一個對象，而是一個用來唯一確定對象的標記。
一般情況下，如果要存儲某個用戶的信息，key 的值可能是這樣: user:100001。Redis 只關心 key 的內存中的數據，因此只要是可以用二進制表示的內容都可以作為 key，比如一張圖片。Redis 支持的數據結構包括哈希表和集合(Set)，但是其中的數據類型只能是字符串。因此 Redis 並不存在對象等同性的考慮，也就可以提供默認的哈希函數了。
Redis、Java、Objective-C 之間的異同再次證明了一點:
“`
總結：
1.HashMap線程不安全，主要是多線程put，get是會出現同步問題；
2.多線程操作HashMap是容易出現循環鏈表，導致get方法調用時可能出現死循環；
3.安全的使用Map有三種方式：Hashtable，SynchronizedMap，ConcurrentHashMap。其中Hashtable不推薦使用，ConcurrentHashMap效率最高。