上節(jié)聊到「Map接口和實現(xiàn)類」，今天我們深入探討其實現(xiàn)類中的HashMap如何進行底層實現(xiàn)。
Hashmap基本結(jié)構(gòu)講解
哈希表的基本結(jié)構(gòu)就是“數(shù)組+鏈表”。我們打開HashMap源碼，發(fā)現(xiàn)有如下兩個核心內(nèi)容：
public?class?? HashMap<K,V>
????extends?? AbstractMap<K,V>
????implements?? Map<K,V>, Cloneable, Serializable {
????/**
???? * The default initial capacity?-?? MUST be a power of two.
???? ? *?核心數(shù)組默認初始化的大小為16（數(shù)組大小必須為2的整數(shù)冪）
???? */
????static?final?int?DEFAULT_INITIAL_CAPACITY?= ? 16;
????/**
???? * The load factor used when none ? specified in constructor.
?? ??*??負載因子（核心數(shù)組被占用超過0.75，則開始啟動擴容）
???? */
????static?final?float?DEFAULT_LOAD_FACTOR?= ? 0.75f;
????/**
???? * The table, resized as necessary. ? Length MUST Always be a power of two.?? ??核心數(shù)組（根據(jù)需要可以擴容）。數(shù)組長度必須始終為2的整數(shù)冪。
???? */
????transient?? Entry[]?table;
????/**
???? * The number of key-value ? mappings contained in this map.
???? *? ??存儲的鍵值對的數(shù)量
???? */
????transient?int?size;
????/**
???? * The next size value at which to resize ? (capacity * load factor).
???? *??擴容后新數(shù)組的大小???? ?
???? */
????int?threshold;
其中的，Entry[] table?就是HashMap的核心數(shù)組結(jié)構(gòu)，我們也稱之為“位桶數(shù)組”。我們再繼續(xù)看Entry是什么，源碼如下：
????static?class?Entry<K,V>?implements?? Map.Entry<K,V> {
????????final?K?key;
??????? V?value;
????????Entry<K,V>?next;
????????final?int?hash;
????????/**
???????? * Creates new entry.
??????? ?*/
??????? Entry(int?h, ? K k, V v,?Entry<K,V> ? n) {
????????????value?= ? v;
????????????next?= ? n;
????????????key?= ? k;
????????????hash?= ? h;
??????? }
??? //其余代碼省略
}
一個Entry對象存儲了：
key：鍵對象??????????????
value：值對象
next:下一個節(jié)點
hash:?鍵對象的hash值?
顯然就是一個單向鏈表結(jié)構(gòu)，我們使用圖形表示一個Entry的典型示意：
然后，我們畫出Entry[]數(shù)組的結(jié)構(gòu)（這也是HashMap的結(jié)構(gòu)）：
存儲數(shù)據(jù)過程put(key,value)
明白了HashMap的基本結(jié)構(gòu)后，我們繼續(xù)深入學(xué)習(xí)HashMap如何存儲數(shù)據(jù)。此處的核心是如何產(chǎn)生hash值，該值用來對應(yīng)數(shù)組的存儲位置。
我們的目的是將”key-value兩個對象”成對存放到HashMap的Entry[]數(shù)組中。
第一步：獲得key對象的hashcode
首先調(diào)用key對象的hashcode()方法，獲得hashcode。
第二步：根據(jù)hashcode計算出hash值(要求在[0, 數(shù)組長度-1]區(qū)間)
hashcode是一個整數(shù)，我們需要將它轉(zhuǎn)化成范圍在[0, 數(shù)組長度-1]的范圍。我們要求轉(zhuǎn)化后的hash值盡量均勻的分布在[0,數(shù)組長度-1]這個區(qū)間，減少“hash沖突”。?
一種極端簡單和低下的算法是：
hash值 = hashcode/hashcode; ?
也就是說，hash值總是1。意味著，鍵值對對象都會存儲到數(shù)組索引1位置，這樣就形成一個非常長的鏈表。相當(dāng)于每存儲一個對象都會發(fā)生“hash沖突”，HashMap也退化成了一個“鏈表”。
一種簡單和常用的算法是（相除取余算法）：
ash值 =? hashcode%數(shù)組長度
這種算法可以讓hash值均勻的分布在[0,數(shù)組長度-1]的區(qū)間。 早期的HashTable就是采用這種算法。但是，這種算法由于使用了“除法”，效率低下。JDK后來改進了算法。
首先約定數(shù)組長度必須為2的整數(shù)冪，這樣采用位運算即可實現(xiàn)取余的效果：
hash值 = hashcode&(數(shù)組長度-1)
如下為我們自己測試簡單的hash算法：
public?class?? Test {
????public?static?void?? main(String[] args) {
???????int?h ? = 25860399;
???????int?? length = 16;?????//length為2的整數(shù)次冪,則h&(length-1)就相當(dāng)于對length取模
???????myHash(h, length);
??? }
????/**
??? ?*
??? ?*?@param?? h??任意整數(shù)
??? ?*?@param?? length??長度必須為2的整數(shù)冪
??? ?*?@return
??? ?*/
????public?static??int?? myHash(int?h,int?? length){
?????? System.out.println(h&(length-1));
????//length為2的整數(shù)冪情況下，和取余的值一樣
?????? System.out.println(h%length);??????//取余數(shù)
???????return?? h&(length-1);
??? }
}
運行如上程序，我們就能發(fā)現(xiàn)直接取余(h%length)和位運算(h&(length-1))結(jié)果是一致的。
事實上，為了獲得更好的散列效果，JDK對hashcode進行了兩次散列處理（核心目標(biāo)就是為了分布更散更均勻），源碼如下：
static?int?? hash(int?h) {
????// This function ensures ? that hashCodes that differ only by
????// constant multiples at ? each bit position have a bounded
????// number of collisions ? (approximately 8 at default load factor).
??? h ^= (h >>> 20) ^ (h >>> ? 12);
????return?h ? ^ (h >>> 7) ^ (h >>> 4);
}
static?int?? indexFor(int?h,?int?? length) {
????return?h ? & (length-1);
}
第三步：生成Entry對象
一個Entry對象包含4部分：key對象、value對象、hash值、下一個Entry對象。我們現(xiàn)在算出了hash值。下一個Entry對象為null等。
第四步：將Entry對象放到table數(shù)組中
如果本Entry對象對應(yīng)的數(shù)組索引位置還沒有放Entry對象，則直接將Entry對象存儲進數(shù)組。
如果對應(yīng)索引位置已經(jīng)有Entry對象，則將已有Entry對象的next指向本Entry對象，形成鏈表。
總結(jié)如上過程：
當(dāng)添加一個元素（key-value）時，首先計算key的hash值，以此確定插入數(shù)組中的位置，但是可能存在同一hash值的元素已經(jīng)被放在數(shù)組同一位置了，這時就添加到同一hash值的元素的后面，他們在數(shù)組的同一位置，就形成了鏈表，同一個鏈表上的Hash值是相同的，所以說數(shù)組存放的是鏈表。 JDK8中，當(dāng)鏈表長度大于8時，鏈表就轉(zhuǎn)換為紅黑樹，這樣又大大提高了查找的效率。
取數(shù)據(jù)過程get(key)
我們需要通過key對象獲得“鍵值對”對象，進而返回value對象。明白了存儲數(shù)據(jù)過程，取數(shù)據(jù)就比較簡單了。
第一步：獲得key的hashcode，通過hash()散列算法得到hash值，進而定位到數(shù)組的位置。
第二步：在鏈表上挨個比較key對象。 調(diào)用equals()方法，將key對象和鏈表上所有節(jié)點的key對象進行比較，直到碰到返回true的節(jié)點對象為止。
第三步：返回equals()為true的節(jié)點對象的value對象。
明白了存取數(shù)據(jù)的過程，我們再來看一下hashcode()和equals方法的關(guān)系：
? Java中規(guī)定，兩個內(nèi)容相同(equals()為true)的對象必須具有相等的 hashCode
如果equals()為true，兩個對象的hashcode不同；那在整個存儲過程中就發(fā)生了悖論。?
擴容問題
HashMap的位桶數(shù)組，初始大小為16。實際使用時，顯然大小是可變。如果位桶數(shù)組中的元素達到（0.75*數(shù)組 length）， 就重新調(diào)整數(shù)組大小變?yōu)樵瓉?倍大小。
擴容很耗時。擴容本質(zhì)就是定義新的更大的數(shù)組，并將舊數(shù)組內(nèi)容挨個拷貝到新數(shù)組中。
JDK8將鏈表在大于8情況下變?yōu)榧t黑二叉樹
JDK8中，HashMap在存儲一個元素時，當(dāng)對應(yīng)鏈表長度大于8時，鏈表就轉(zhuǎn)換為紅黑樹，這樣又大大提高了查找的效率。
下一節(jié)，我們簡單介紹一個二叉樹。同時，也便于大家理解TreeMap的底層結(jié)構(gòu)。
「全棧Java筆記」是一部能幫大家從零到一成長為全棧Java工程師系列筆記。筆者江湖人稱 Mr. G，10年Java研發(fā)經(jīng)驗，曾在神州數(shù)碼、航天院某所研發(fā)中心從事軟件設(shè)計及研發(fā)工作，從小白逐漸做到工程師、高級工程師、架構(gòu)師。精通Java平臺軟件開發(fā)，精通JAVAEE，熟悉各種流行開發(fā)框架。
? 筆記包含從淺入深的六大部分：
? A-Java入門階段
? B-數(shù)據(jù)庫從入門到精通
? C-手刃移動前端和Web前端
? D-J2EE從了解到實戰(zhàn)
? E-Java高級框架精解
? F-Linux和Hadoop?
