---

歡迎支持筆者新作：《深入理解Kafka:核心設計與實踐原理》和《RabbitMQ實戰指南》，同時歡迎關注筆者的微信公眾號：朱小廝的博客。

---

歡迎跳轉到本文的原文鏈接：https://honeypps.com/java/java-collection-hashmap/

Java集合框架概述

??Java集合框架無論是在工作、學習、面試中都會經常涉及到，相信各位也并不陌生，其強大也不用多說，博主最近翻閱java集合框架的源碼以及搜索一些相關資料整理出Java集合框架的系列。一方面是做一個總結，方便以后查閱，另一方面希望各位小伙伴能夠提出不足之處，我會及時更新修改。

??博主從網上摳了一張圖，覺得畫得還是比較形象的，給大家參考一下。
??上述類圖中，實線邊框的是實現類，比如ArrayList，LinkedList，HashMap等，折線邊框的是抽象類，比如AbstractCollection，AbstractList，AbstractMap等，而點線邊框的是接口，比如Collection，Iterator，List等。
??發現一個特點，上述所有的集合類，都實現了Iterator接口，這是一個用于遍歷集合中元素的接口，主要包含hasNext(), next(), remove()三種方法。它的一個子接口LinkedIterator在它的基礎上又添加了三種方法，分別是add(),previous(),hasPrevious()。也就是說如果是先Iterator接口，那么在遍歷集合中元素的時候，只能往后遍歷，被遍歷后的元素不會在遍歷到，通常無序集合實現的都是這個接口，比如HashSet，HashMap；而那些元素有序的集合，實現的一般都是LinkedIterator接口，實現這個接口的集合可以雙向遍歷，既可以通過next()訪問下一個元素，又可以通過previous()訪問前一個元素，比如ArrayList。
??本篇首先對HashMap進行詳解，后續內容慢慢跟進。

---

HashMap定義

??如無特殊說明，本文以jdk7為準進行說明。

package java.util; import java.io.*; public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable{ }

---

HashMap概述

??工作原理：通過hash的方法，通過put和get存儲和獲取對象。存儲對象時，我們將K/V傳給put方法時，它調用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據當前bucket的占用情況自動調整容量(超過Load Factor則resize為原來的2倍)。獲取對象時，我們將K傳給get，它調用hashCode計算hash從而得到bucket位置，并進一步調用equals()方法確定鍵值對。如果發生碰撞的時候，Hashmap通過鏈表將產生碰撞沖突的元素組織起來，在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表，從而提高速度。
??以Entry[]數組實現的哈希桶數組，用Key的哈希值取模桶數組的大小可得到數組下標。

static final Entry<?,?>[] EMPTY_TABLE = {}; transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

??基于Map接口實現、允許null鍵/值、非同步、不保證有序(比如插入的順序)、也不保證序不隨時間變化。HashMap存儲著Entry(hash, key, value, next)對象。
??當key==null時，存在table[0]即第一個桶中，hash值為0。HashMap對key==null的鍵值對會做單獨處理，譬如：

private V getForNullKey()；private V putForNullKey(V value)；

??這兩個方法。
??在HashMap中有兩個很重要的參數，容量(Capacity)和負載因子(Load factor)。
??Capacity的默認值為16：
??static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
?? 負載因子的默認值為0.75：
??static final float DEFAULT_LOAD_FACTOR = 0.75f;
??簡單的說，Capacity就是bucket的大小，Load factor就是bucket填滿程度的最大比例。如果對迭代性能要求很高的話不要把Capacity設置過大，也不要把load factor設置過小。當bucket中的entries的數目大于capacity*load factor時就需要調整bucket的大小為當前的2倍。
??可以設置初始容量Capacity，但是在HashMap處理過程中，是會把Capacity擴充成2的倍數，怎么理解？比如你設置的初始值17，但是17不是2的整數倍，會擴容成32，再比如你初始設置的是15，會擴容成16，具體的實現在下面：

private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}

??HashMap中有一個成員變量modCount，這個用來實現“fast-fail”機制（也就是快速失敗）。所謂快速失敗就是在并發集合中，其進行迭代操作時，若有其他線程對其結構性的修改，這是迭代器會立馬感知到，并且立刻拋出ConcurrentModificationException異常，而不是等待迭代完成之后才告訴你已經出錯。

---

HashMap的遍歷

??舉個例子來表述下Map的遍歷，具體的可以參考《 Java中如何遍歷Map對象》

Map<String,Integer> map = new HashMap<>();map.put("s1", 1);map.put("s2", 2);map.put("s3", 3);map.put("s4", 4);map.put("s5", 5);map.put(null, 9);map.put("s6", 6);map.put("s7", 7);map.put("s8", 8);for(Map.Entry<String,Integer> entry:map.entrySet()){System.out.println(entry.getKey()+":"+entry.getValue());}

??輸出結果：

null:9 s2:2 s1:1 s7:7 s8:8 s5:5 s6:6 s3:3 s4:4

??存儲結構如圖（ppt畫的圖，比較簡陋~）：

put函數大致的思路為：

先判斷table(存放bullet的數組，初始類定義：transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;)是否為空，如果為空則擴充table，其中包括確保table的大小為2的整數倍。

如果key值為null，則特殊處理，調用putForNullKey(V value)，hash值為0，存入table中，返回。

如果key值不為null，則計算key的hash值；

然后計算key在table中的索引index;

遍歷table[index]的鏈表，如果發現鏈表中有bullet中的鍵的hash值與key相等，并且調用equals()方法也返回true，則替換舊值（oldValue），保證key的唯一性；

如果沒有，在插入之前先判斷table中閾值的大小，如果table中的bullet個數size超過閾值（threshold）則擴容（resize）兩倍；注意擴容的順序，擴容之前old1->old2->old3，擴容之后old3->old2->old1，擴展之前和擴容之后的table的index不一定相同，對于原bullet中的鏈表中的數據在擴容之后也不一定還在一個鏈表中。

插入新的bullet。注意插入的順序，原先table[index]的鏈表比如 old1->old2->old3，插入新值之后為new1->old1->old2->old3.

public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);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);return null;}void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}

注：在jdk8中，新增默認為8的閥值（TREEIFY_THRESHOLD），當一個桶里的Entry超過閥值，就不以單向鏈表而以紅黑樹來存放以加快Key的查找速度。

get函數的大致思路為：

判斷key值是否為null，如果是則特殊處理（在table[0]的鏈表中尋找）

否則計算hash值，進而獲得table中的index值

在table[index]的鏈表中尋找，根據hash值和equals()方法獲得相應的value。

public V get(Object key) {if (key == null)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;}

hash和indexFor方法:

final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}public native int hashCode();static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);}

看懂沒？還是實地檢驗下比較形象~
譬如key==“key”,那么key的hashCode為（十進制數為106079）：
0000 0000 0000 0001 1001 1110 0101 1111
執行h ^= (h >>> 20) ^ (h >>> 12);的時候
h>>>20:
0000 0000 0000 0000 0000 0000 0000 0000
h>>>12:
0000 0000 0000 0000 0000 0000 0001 1001
h ^= (h >>> 20) ^ (h >>> 12):
0000 0000 0000 0001 1001 1110 0100 0110
執行h ^ (h >>> 7) ^ (h >>> 4)的時候
h >>> 7：
0000 0000 0000 0000 0000 0011 0011 1100
h>>>4:
0000 0000 0000 0000 0001 1001 1110 0100
h ^ (h >>> 7) ^ (h >>> 4):
0000 0000 0000 0001 1000 0100 1001 1110（十進制表示為99486）
假設Capacity是默認16，那么
h&(length-1):
0000 0000 0000 0001 1000 0100 1001 1110 &
0000 0000 0000 0000 0000 0000 0000 1111 =
0000 0000 0000 0000 0000 0000 0000 1110 = 14
我們可以通過eclipse的debug工作中的Variables查看相關細節：

?? 可以看到key="key"果然在table[14]當中。
??h & (length-1)這種取模用位運算的方式比較快，這個需要數組的大小永遠是2的N次方來保證其有效性。
>jdk8中hash函數的實現：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

---

使用自定義的對象作為鍵

??可以使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經滿足了作為鍵的條件，因為當它創建之后就已經不能改變了。
??如下：

package collections;public class StringOther {private String name;public StringOther(String name){this.name = name;}@Overridepublic int hashCode(){return name.hashCode();}@Overridepublic boolean equals(Object obj){if(obj == this)return true;if(!(obj instanceof StringOther))return false;StringOther so = (StringOther)obj;return so.getName().equals(name);}public String getName(){return this.name;}@Overridepublic String toString(){return "["+this.name+":"+this.hashCode()+"]";} }

??測試代碼：

Map<StringOther,String> maps = new HashMap<>(16);StringOther so1 = new StringOther("so1");StringOther so2 = new StringOther("so2");maps.put(so1,"1");maps.put(so2,"2");System.out.println(maps);

??輸出結果：{[so1:114005]=1, [so2:114006]=2}
??注意重寫equals方法的時候一定要寫成:

@Override public boolean equals(Object obj)

的形式，注意注解Override和參數類型Object obj，如寫成@Override public boolean equals(StringOther obj)這樣會出現意想不到的錯誤，如果對其不解，可在下方留言。
??并且在每個覆蓋了equals方法的類中也必須覆蓋hashCode方法，如果不這樣做的話，就會違反Object.hashCode的通用約定，從而導致該類無法結合所有基于散列的集合一起正常運轉，這樣的集合包括HashMap, HashSet和Hashtable.

---

序列化

??細心的朋友可能注意到HashMap實現了Serializable接口，但是對table的定義（transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;）卻是transient的。然后又自己實現了writeObject()和readObject()兩個方法。
>假設我們已經知道的事實：聲明為transient的變量不再是對象持久化的一部分。如果不清楚java序列化相關細節，可以參考《JAVA序列化》。

??那么這是為什么呢？原因有兩點：

HashMap的put與get基于hashCode的實現，而hashCode是native方法，對每一個不同的java環境來說，同一個key所計算的hashCode是不相同的，所以反序列化后table的index會發生變化，無法還原

HashMap默認size到達閾值threshold之后進行擴容，很明顯HashMap不可能保證每一個bullet都有數據，很多都為null，如果對這部分數據進行序列化則造成不必要的資源浪費。

??由于Java自身的序列化有明顯的缺點：占用空間大以及低效，博主建議采用其他的方法進行序列化，譬如json或者protobuff等，詳細可以參考《淺析若干Java序列化工具》

---

與Hashtable的區別

??由于Hashtable逐漸退出歷史舞臺，故不會另起一篇進行重點解析，只在這里與HashMap區別一下。
??HashMap和Hashtable都實現了Map接口，但決定用哪一個之前先要弄清楚它們之間的分別。

HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable的key和value都不能為null，否則會報NullPointException)。

HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。

由于Hashtable是線程安全的也是synchronized，所以在單線程環境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過Hashtable。

HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

Hashtable和HashMap它們兩個內部實現方式的數組的初始大小和擴容的方式。HashTable中hash數組默認大小是11，增加的方式是 old*2+1。HashMap中hash數組的默認大小是16，而且一定是2的指數。

??HashMap可以通過下面的語句進行同步：Map m = Collections.synchronizeMap(hashMap);
??Hashtable和HashMap有幾個主要的不同：線程安全以及速度。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用Java 5或以上的話，請使用ConcurrentHashMap吧。

---

HashMap常見問題總結

HashMap的工作原理?(見開篇)

你知道get和put的原理嗎？equals()和hashCode()的都有什么作用？
答：通過對key的hashCode()進行hashing，并計算下標( n-1 & hash)，從而獲得buckets的位置。如果產生碰撞，則利用key.equals()方法去鏈表或樹中去查找對應的節點。

為什么String, Interger這樣的wrapper類適合作為鍵？
String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。

---

參考資料：

《Java HashMap工作原理及實現》

《關于Java集合的小抄》

《HashMap和Hashtable的區別》

《Java 集合類詳解》

《Effective Java(Second Edition)》. Joshua Bloch.

歡迎跳轉到本文的原文鏈接：https://honeypps.com/java/java-collection-hashmap/

---

歡迎支持筆者新作：《深入理解Kafka:核心設計與實踐原理》和《RabbitMQ實戰指南》，同時歡迎關注筆者的微信公眾號：朱小廝的博客。

---

總結

以上是生活随笔為你收集整理的Java集合框架：HashMap的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。