講到HashMap不得不講到HashCode，百度HashCode，它的釋義如下
哈希碼并不是完全唯一的，它是一種算法，讓同一個類的對象按照自己不同的特征盡量的有不同的哈希碼，但不表示不同的對象哈希碼完全不同。也有相同的情況，看程序員如何寫哈希碼的算法。
HashCode是用來在散列存儲結(jié)構(gòu)中確定對象的存儲地址，HashMap正是利用HashCode來快速定位存儲對象的。
上面說過HashCode并不是唯一的，他取決于設(shè)計的哈希算法，所以在HashMap會出現(xiàn)Hash沖突的情況，那HashMap是怎么處理這種問題的呢？答案是在產(chǎn)生沖突的地方使用鏈表和紅黑樹。
在JDK1.8之前解決hash沖突使用的是鏈表，實際上初始化后的HashMap就是由長度為1的單向鏈表組成的數(shù)組，在發(fā)生hash沖突時，該節(jié)點的單向鏈表保存具有相同hashcode的對象。在JDK1.8之后，當(dāng)節(jié)點的單向鏈表長度大于8時，改為使用紅黑樹，提高查找效率。
HashMap是日常開發(fā)中非常常用的容器，HashMap實現(xiàn)了Map接口，底層的實現(xiàn)原理是哈希表，HashMap不是一個線程安全的容器，jdk8對HashMap做了一些改進，作為開發(fā)人員需要對HashMap的原理有所了解，現(xiàn)在就通過源碼來了解HashMap的實現(xiàn)原理。
首先看HashMap中的屬性
//Node數(shù)組
transient Node[] table;
//當(dāng)前哈希表中k-v對個數(shù)，實際就是node的個數(shù)
transient int size;
//修改次數(shù)
transient int modCount;
//元素閾值
int threshold;
//負載因子
final float loadFactor;
這里的threshold = loadFactor * table.length，hash表如果想要保持比較好的性能，數(shù)組的長度通常要大于元素個數(shù)，默認(rèn)的負載因子是0.75，用戶可以自行修改，不過最好使用默認(rèn)的負載因子。
Node是用來存儲KV的節(jié)點，每次put(k,v)的時候就會包裝成一個新的Node, Node定義
static class Node implements Map.Entry {
//hash值
final int hash;
final K key;
V value;
//hash & (capacity - 1) 相同的Node會形成一個鏈表
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
put操作
寫入操作是map中最常用的方法，這里看看hashmap的put方法代碼
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這里先計算key的hash值，然后調(diào)用putVal()方法，其中hash方法是內(nèi)部自帶的一個算法，會對key的hashcode再做一次hash操作

專注于為中小企業(yè)提供成都網(wǎng)站制作、成都做網(wǎng)站服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)龍?zhí)睹赓M做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
pubVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //如果數(shù)組為空，先初始化一下
if ((p = tab[i = (n - 1) & hash]) == null) //如果對應(yīng)的數(shù)組為空的話，那么就直接new一個node然后塞進去
tab[i] = newNode(hash, key, value, null);
else { //如果有值，說明發(fā)生了沖突，那么就先用拉鏈法來處理沖突
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果頭結(jié)點的key和要插入的key相同，那么就說明找到了之前插入的節(jié)點
else if (p instanceof TreeNode) //如果鏈表轉(zhuǎn)成了紅黑樹
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //如果之前沒有put過這個節(jié)點，那么就new一個新的節(jié)點
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//另外要檢查一下當(dāng)前鏈表的長度，如果超過8那么就將鏈表轉(zhuǎn)化成紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果找到了之前的節(jié)點，那么就跳出
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //在當(dāng)前類中NOOP
return oldValue;
}
}
++modCount;
//如果當(dāng)前元素數(shù)量大于門限值，就要resize整個hash表，實際上就是把數(shù)組擴大一倍，然后將所有元素重新塞到新的hash表中
if (++size > threshold)
resize();
afterNodeInsertion(evict); //在該類中NOOP
return null;
}
在hashtable中默認(rèn)的出現(xiàn)沖突的時候就會將沖突的元素形成一個鏈表，當(dāng)鏈表長度大于8的時候就會將鏈表變成一個二叉樹，這是java8中做出的改進，因為在使用hash表的時候在key特殊的情況下最壞的時候hash表會退化成一個鏈表，那么原有的O(1)的時間復(fù)雜度就變成了O(n)，性能就會大打折扣，但是引用了紅黑樹之后那么在最好的情況下時間復(fù)雜度就變成了O(log(n))。
resize方法
final Node [] resize() {
......
//去掉了一些代碼，只關(guān)注最核心的node遷移
//resize會新建一個數(shù)組，數(shù)組的長度是原來數(shù)組長度的兩倍
for (int j = 0; j < oldCap; ++j) {//遍歷原來的數(shù)組
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e; //如果沒有形成鏈表的話，就直接塞到新的hash表中
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap); //紅黑樹操作？？
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { //如果hash值小于oldCap的時候，那么就還在原來那個數(shù)組的位置，就把這個節(jié)點放到low鏈表中
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //否則的話就是因為擴展數(shù)組長度，就把原來的節(jié)點放到high鏈表中
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; //low鏈表還放在原來的位置
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; //high鏈表放到j(luò)+oldCap位置上
}
}
}
}
}
resize操作就是創(chuàng)建一個先的數(shù)組，然后把老的數(shù)組中的元素塞到新的數(shù)組中，注意java8中的hashMap中數(shù)組長度都是2的n次冪,2、4、、8、16….. 這樣的好處就是可以通過與操作來替代求余操作。當(dāng)數(shù)組擴大之后，那么每個元素所在的位置是可以預(yù)期的，就是要不就待在原來的位置，要不就是到j(luò)+oldCap位置上，舉個栗子，如果原來數(shù)組長度為4，那么hash為3和7 的元素都會放在index為3的位置上，當(dāng)數(shù)組長度變成8的時候，hash為3的元素還待在index為3的位置，hash為7的元素此時就要放到index為7的位置上。
resize操作是一個很重要的操作，resize會很消耗性能，因此在創(chuàng)建hashMap的時候最好先預(yù)估容量，防止重復(fù)創(chuàng)建拷貝。
另外hashmap也是非線程安全的，在多線程操作的時候可能會產(chǎn)生cpu100%的情況，主要的原因也是因為在多個線程resize的時候?qū)е骆湵懋a(chǎn)生了環(huán)，這樣下次get操作的時候就會容易進入死循環(huán)。
get方法（）
get的實現(xiàn)比較簡單
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) //如果節(jié)點不為空而且頭結(jié)點與查找的key相同就返回
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);//從紅黑樹中查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null); //遍歷鏈表查找key相同的node
}
}
return null;
}
HashMap的常量和構(gòu)造函數(shù)
//默認(rèn)初始容量，這個值必須是2的次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
//大容量，也必須設(shè)置成2的次冪
static final int MAXIMUM_CAPACITY = 1 << 30; // 1 073 741 824
//負載因子默認(rèn)大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//節(jié)點保存數(shù)據(jù)數(shù)量超過這個值，由鏈表轉(zhuǎn)為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//當(dāng)節(jié)點保存數(shù)據(jù)數(shù)量小于該值，紅黑樹轉(zhuǎn)為鏈表存儲
static final int UNTREEIFY_THRESHOLD = 6;
//紅黑樹最小長度
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap中實際就是用這樣一個元素類型為Node的數(shù)組來存儲數(shù)據(jù)，該數(shù)組長度必須為2的次冪
//每個Node本質(zhì)上就是一個單向鏈表
transient Node[] table;
//HashMap大小,它代表HashMap保存的鍵值對的多少
transient int size;
//HashMap被改變的次數(shù)
transient int modCount;
//HashMap擴容的閾值，保存鍵值對個數(shù)大于它就要擴容
int threshold;
//存儲負載因子的常量
final float loadFactor;
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(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
//根據(jù)loadFactor以及MAXIMUM_CAPACITY再次計算出新的threshold
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
//數(shù)量超過閾值擴容
else if (s > threshold)
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
HashMap中的元素單向鏈表Node是Map.Entry的實現(xiàn)，可以看到每一個Node只有next屬性，沒有pre屬性，是一個單向鏈表
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node 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;
}
}
HashMap中的紅黑樹也是自己實現(xiàn)的，這里就不詳細列出其實現(xiàn)
static final class TreeNode extends LinkedHashMap.Entry {
//省略...
}
HashMap主要常用API get和put方法
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//使用key參與hash運算后得出的hash，找出該位置的鏈表節(jié)點的第一個元素first
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//總是先檢查鏈表第一個元素first是否匹配，匹配上就返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//匹配不上，就使用first的next屬性找到下一個節(jié)點e
if ((e = first.next) != null) {
//先判斷第一個節(jié)點是否是紅黑樹節(jié)點,是則在紅黑樹中查找
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
//如果不是紅黑樹節(jié)點，再循環(huán)遍歷該位置單向鏈表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//以上都無法匹配就返回null
return null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果使用該hash計算出XM返傭www.fx61.com/brokerlist/xm.html的位置沒有元素，就把元素保存在這個位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
//如果該位置有數(shù)據(jù)，且該節(jié)點Node的hash和key都與傳入值相同或調(diào)用傳入鍵對象的equals方法與節(jié)點Node的key比較相同，則覆蓋該數(shù)據(jù)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果上面的if判斷不滿足，且該位置節(jié)點Node是紅黑樹類型，使用紅黑樹保存
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
//如果if滿足也不是紅黑樹類型節(jié)點，則找出該位置單向鏈表最后一個位置的元素，把它的next指向新傳入數(shù)據(jù)保存位置
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//添加完后，若該節(jié)點鏈表長度超過8，則轉(zhuǎn)換為紅黑樹
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;
//包含元素個數(shù)超過閾值，則擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
為什么HashMap的容量必須設(shè)置為2的次冪呢？
其實主要是為了在哈希算法中減少碰撞，使數(shù)據(jù)均勻分布。這里就不深究了。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

新聞標(biāo)題：Java基礎(chǔ)之HashMap的原理-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://weahome.cn/article/shjdh.html