本文是在閱讀知乎老劉作品后的整理。內(nèi)容基于JDK1.7進行分析，1.8做的改動文章末尾進行講解。

1. 基本要義

1.1 概述

Hashmap在Map派生中的位置

HashMap基于Map接口實現(xiàn)，元素以鍵值對的方式存儲，并且允許使用null鍵和null值，因為key不允許重復(fù)，因此只能有一個鍵為null,另外HashMap不能保證放入元素的順序，是無序的。此外，HashMap是線程不安全的。

1.2 繼承關(guān)系

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable

1.3 基本屬性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默認(rèn)初始化大小 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; //負(fù)載因子0.75 static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默認(rèn)數(shù)組 transient int size; //HashMap中元素的數(shù)量 int threshold; //判斷是否需要調(diào)整HashMap的容量

HashMap的擴容操作是一項很耗時的任務(wù)，所以如果能估算Map的容量，最好給它一個默認(rèn)初始值，避免進行多次擴容。HashMap的線程是不安全的，多線程環(huán)境中推薦是ConcurrentHashMap。

2.?HashMap和Hashtable的區(qū)別

2.1 線程安全

兩者最主要的區(qū)別在于Hashtable是線程安全，而HashMap則非線程安全。

Hashtable的實現(xiàn)方法里面都添加了synchronized關(guān)鍵字來確保線程同步。因此，相對而言HashMap性能會高一些，我們平時使用時若無特殊需求建議使用HashMap，在多線程環(huán)境下若使用HashMap需要使用Collections.synchronizedMap()方法來獲取一個線程安全的集合。

Note：Collections.synchronizedMap()實現(xiàn)原理是Collections定義了一個SynchronizedMap的內(nèi)部類，這個類實現(xiàn)了Map接口，在調(diào)用方法時使用synchronized來保證線程同步,當(dāng)然了實際上操作的還是我們傳入的HashMap實例，簡單的說就是Collections.synchronizedMap()方法幫我們在操作HashMap時自動添加了synchronized來實現(xiàn)線程同步，類似的其它Collections.synchronizedXX方法也是類似原理。

2.2?針對null的不同

HashMap可以使用null作為key，而Hashtable則不允許null作為key。雖說HashMap支持null值作為key，不過建議還是盡量避免這樣使用，因為一旦不小心使用了，若因此引發(fā)一些問題，排查起來很是費事。

Note：HashMap以null作為key時，總是存儲在table數(shù)組的第一個節(jié)點上（index=0）。

2.3 繼承結(jié)構(gòu)

HashMap是對Map接口的實現(xiàn)，HashTable實現(xiàn)了Map接口和Dictionary抽象類。

2.4?初始容量與擴容

HashMap的初始容量為16，Hashtable初始容量為11，兩者的填充因子默認(rèn)都是0.75。HashMap擴容時是當(dāng)前容量翻倍即:capacity*2，Hashtable擴容時是容量翻倍+1即:capacity*2+1。

2.5?計算hash的方法不同

Hashtable計算hash是直接使用key的hashcode對table數(shù)組的長度直接進行取模.

int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap計算hash對key的hashcode進行了二次hash，以獲得更好的散列值，然后對table數(shù)組長度取摸。

int hash = hash(key.hashCode()); int i = indexFor(hash, table.length);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); // &是為了保證處理效率；數(shù)組的長度為2的冪次也是為了保證散列值更好

3. Java1.7 ：?HashMap的數(shù)據(jù)存儲結(jié)構(gòu)

3.1?HashMap由數(shù)組和鏈表來實現(xiàn)對數(shù)據(jù)的存儲

HashMap采用Entry數(shù)組來存儲key-value對，每一個鍵值對組成了一個Entry實體，Entry類實際上是一個單向的鏈表結(jié)構(gòu)，它具有Next指針，可以連接下一個Entry實體，以此來解決Hash沖突的問題（這也決定了，新加入hashmap的key-value，首先根據(jù)key的hashcode計算數(shù)組索引，然后在該索引下，采用頭插法存儲entry，entry的屬性自然就包括了hash,key,value,next; next指向之前的entry鏈表表頭）。

• 數(shù)組存儲區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故空間復(fù)雜的很大。但數(shù)組的二分查找時間復(fù)雜度小，為O(1)；數(shù)組的特點是：尋址容易，插入和刪除困難；
• 鏈表存儲區(qū)間離散，占用內(nèi)存比較寬松，故空間復(fù)雜度很小，但時間復(fù)雜度很大，達O（N）。鏈表的特點是：尋址困難，插入和刪除容易。

Java1.7 HashMap使用的列表+鏈表結(jié)構(gòu)

?

Java 1.7 詳細(xì)的列表+鏈表結(jié)構(gòu)；新數(shù)據(jù)采用頭插法放入鏈表

?

Java1.7 數(shù)據(jù)存儲到hashmap中演示示例

從上圖可以發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)由數(shù)組+鏈表組成，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢。在Java1.4中，采用hash(key.hashCode())%len獲得，在Java1.7中使用hash(key.hashCode())&（len-1）并經(jīng)過一些列右移和異或運算獲得。

HashMap里面實現(xiàn)一個靜態(tài)內(nèi)部類Entry，其重要的屬性有 hash，key，value，next。HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個概念。上面提到過Entry類里面有一個next屬性，作用是指向下一個Entry。打個比方， 第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:Entry[0] = A。一會后又進來一個鍵值對B，通過計算其index也等于0，現(xiàn)在怎么辦？HashMap會這樣做:B.next = A,Entry[0] = B,如果又進來C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發(fā)現(xiàn)index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起（新數(shù)據(jù)，頭插法）。所以疑問不用擔(dān)心。也就是說數(shù)組中存儲的是最后插入的元素。

public V put(K key, V value) {if (key == null)return putForNullKey(value); //null總是放在數(shù)組的第一個鏈表中int hash = hash(key.hashCode());int i = indexFor(hash, table.length);//遍歷鏈表for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;//如果key在鏈表中已存在，則替換為新valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i);return null;}void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //參數(shù)e, 是Entry.next//如果size超過threshold，則擴充table大小。再散列if (size++ >= threshold)resize(2 * table.length); }

4. hashmap對應(yīng)的方法

4.1 構(gòu)造方法

HashMap() //無參構(gòu)造方法 HashMap(int initialCapacity) //指定初始容量的構(gòu)造方法 HashMap(int initialCapacity, float loadFactor) //指定初始容量和負(fù)載因子 HashMap(Map<? extends K,? extends V> m) //指定集合，轉(zhuǎn)化為HashMap

HashMap提供了四個構(gòu)造方法，構(gòu)造方法中 ，依靠第三個方法來執(zhí)行的，但是前三個方法都沒有進行數(shù)組的初始化操作，即使調(diào)用了構(gòu)造方法此時存放HaspMap中數(shù)組元素的table表長度依舊為0?。在第四個構(gòu)造方法中調(diào)用了inflateTable()方法完成了table的初始化操作，并將m中的元素添加到HashMap中。

4.2 添加方法 : put

public V put(K key, V value) {if (table == EMPTY_TABLE) { //是否初始化inflateTable(threshold);}if (key == null) //放置在0號位置return putForNullKey(value);int hash = hash(key); //計算hash值int i = indexFor(hash, table.length); //計算在Entry[]中的存儲位置for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i); //添加到Map中return null; }

在該方法中，添加鍵值對時，首先進行table是否初始化的判斷，如果沒有進行初始化（分配空間，Entry[]數(shù)組的長度）。然后進行key是否為null的判斷，如果key==null ,放置在Entry[]的0號位置。計算在Entry[]數(shù)組的存儲位置，判斷該位置上是否已有元素，如果已經(jīng)有元素存在，則遍歷該Entry[]數(shù)組位置上的單鏈表。判斷key是否存在，如果key已經(jīng)存在，則用新的value值，替換點舊的value值，并將舊的value值返回。如果key不存在于HashMap中，程序繼續(xù)向下執(zhí)行。將key-vlaue, 生成Entry實體，添加到HashMap中的Entry[]數(shù)組中。

4.3?addEntry()

/** hash hash值* key 鍵值* value value值* bucketIndex Entry[]數(shù)組中的存儲索引* / void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length); //擴容操作，將數(shù)據(jù)元素重新計算位置后放入newTable中，鏈表的順序與之前的順序相反hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++; }

添加到方法的具體操作，在添加之前先進行容量的判斷，如果當(dāng)前容量達到了閾值，并且需要存儲到Entry[]數(shù)組中，先進性擴容操作，空充的容量為table長度的2倍。重新計算hash值，和數(shù)組存儲的位置，擴容后的鏈表順序與擴容前的鏈表順序相反。然后將新添加的Entry實體存放到當(dāng)前Entry[]位置鏈表的頭部。在1.8之前，新插入的元素都是放在了鏈表的頭部位置，但是這種操作在高并發(fā)的環(huán)境下容易導(dǎo)致死鎖，所以1.8之后，新插入的元素都放在了鏈表的尾部。

4.4 獲取方法 ： get

public V get(Object key) {if (key == null)//返回table[0] 的value值return getForNullKey();Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))return e;}return null; }

在get方法中，首先計算hash值，然后調(diào)用indexFor()方法得到該key在table中的存儲位置，得到該位置的單鏈表，遍歷列表找到key和指定key內(nèi)容相等的Entry，返回entry.value值。

4.5 刪除方法 ： delete

public V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);return (e == null ? null : e.value); } final Entry<K,V> removeEntryForKey(Object key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);int i = indexFor(hash, table.length);Entry<K,V> prev = table[i];Entry<K,V> e = prev;while (e != null) {Entry<K,V> next = e.next;Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++;size--;if (prev == e)table[i] = next;elseprev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e; }

刪除操作，先計算指定key的hash值，然后計算出table中的存儲位置，判斷當(dāng)前位置是否Entry實體存在，如果沒有直接返回，若當(dāng)前位置有Entry實體存在，則開始遍歷列表。定義了三個Entry引用，分別為pre, e ,next。 在循環(huán)遍歷的過程中，首先判斷pre 和 e 是否相等，若相等表明，table的當(dāng)前位置只有一個元素，直接將table[i] = next = null 。若形成了pre -> e -> next 的連接關(guān)系，判斷e的key是否和指定的key 相等，若相等則讓pre -> next ,e 失去引用。

4.6 包含key : containKey

public boolean containsKey(Object key) {return getEntry(key) != null;} final Entry<K,V> getEntry(Object key) {int hash = (key == null) ? 0 : hash(key.hashCode());for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}

containsKey方法是先計算hash然后使用hash和table.length得到index值，遍歷table[index]元素查找是否包含key相同的值。

4.7 包含value ：containsValue

public boolean containsValue(Object value) {if (value == null)return containsNullValue();Entry[] tab = table;for (int i = 0; i < tab.length ; i++)for (Entry e = tab[i] ; e != null ; e = e.next)if (value.equals(e.value))return true;return false;}

containsValue方法就比較粗暴了，就是直接遍歷所有元素直到找到value。

5. Java 1.8 中的變動

在Jdk1.8中HashMap的實現(xiàn)方式做了優(yōu)化。,數(shù)據(jù)結(jié)構(gòu)的存儲由數(shù)組+鏈表的方式，變化為數(shù)組+鏈表+紅黑樹的存儲方式，當(dāng)鏈表長度超過閾值（8）時，將鏈表轉(zhuǎn)換為紅黑樹。在性能上進一步得到提升。

Note：如果在鏈表長度為8時，進行反復(fù)的put和delete操作，是否會造成頻繁的建樹與頻繁的退化成列表？是否會造成時間開銷劇增？JDK1.8設(shè)計hashmap的時候就考慮到了這一點。當(dāng)鏈表長度大于8的時候，才會構(gòu)建紅黑樹進行存儲，此時的時間復(fù)雜度為log(n)；當(dāng)紅黑樹中的數(shù)據(jù)少于6個的時候，紅黑樹才會退化為鏈表。這是典型的margin技巧。

總結(jié)

以上是生活随笔為你收集整理的HashMap底层实现和原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。