Java集合篇：HashMap原理详解（JDK1.7及之前的版本）
（本文有關HashMap的源碼都是基于JDK1.6的）
摘要：
HashMap是Map族中最為常用的一種，也是 Java Collection Framework 的重要成員。本文首先給出了 HashMap 的實質并概述了其與 Map、HashSet 的關系，緊接著給出了 HashMap 在 JDK 中的定義，并結合源碼分析了其四種構造方式。最后，通過對 HashMap 的數據結構、實現原理、源碼實現三個方面的剖析，深入到它底層 Hash 存儲機制，解釋了其底層數組長度總是 2 的 n 次方的原因，也揭示了其快速存取、擴容及擴容后的重哈希的原理與實現。
一、HashMap概述：
Map 是 Key-Value 對映射的抽象接口，該映射不包括重復的鍵，即一個鍵對應一個值。HashMap 是 Java Collection Framework 的重要成員，也是Map族(如下圖所示)中我們最為常用的一種。簡單地說，HashMap 是基于哈希表的 Map 接口的實現，以 Key-Value 的形式存在，即存儲的對象是 Entry (同時包含了 Key 和 Value) 。在HashMap中，其會根據hash算法來計算key-value的存儲位置并進行快速存取。特別地，HashMap最多只允許一條Entry的鍵為Null(多條會覆蓋)，但允許多條Entry的值為Null。此外，HashMap 是 Map 的一個非同步的實現。?
同樣地，HashSet 也是 Java Collection Framework 的重要成員，是 Set 接口的常用實現類，但其與 HashMap 有很多相似之處。對于 HashSet 而言，其采用 Hash 算法決定元素在Set中的存儲位置，這樣可以保證元素的快速存取；對于 HashMap 而言，其將 key-value 當成一個整體(Entry 對象)來處理，其也采用同樣的 Hash 算法去決定 key-value 的存儲位置從而保證鍵值對的快速存取。雖然 HashMap 和 HashSet 實現的接口規范不同，但是它們底層的 Hash 存儲機制完全相同。實際上，HashSet 本身就是在 HashMap 的基礎上實現的。因此，通過對 HashMap 的數據結構、實現原理、源碼實現三個方面了解，我們不但可以進一步掌握其底層的 Hash 存儲機制，也有助于對 HashSet 的了解。
必須指出的是，雖然容器號稱存儲的是 Java 對象，但實際上并不會真正將 Java 對象放入容器中，只是在容器中保留這些對象的引用。也就是說，Java 容器實際上包含的是引用變量，而這些引用變量指向了我們要實際保存的 Java 對象。
二、HashMap在JDK中的定義：
HashMap實現了Map接口，并繼承 AbstractMap 抽象類，其中 Map 接口定義了鍵值映射規則。和 AbstractCollection抽象類在 Collection 族的作用類似， AbstractMap 抽象類提供了 Map 接口的骨干實現，以最大限度地減少實現Map接口所需的工作。HashMap 在JDK中的定義為：
public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable{ ... }三、HashMap的構造函數：
HashMap 一共提供了四個構造函數，其中 默認無參的構造函數 和 參數為Map的構造函數 為 Java Collection Framework 規范的推薦實現，其余兩個構造函數則是 HashMap 專門提供的。
1、HashMap()：
該構造函數意在構造一個具有? 默認初始容量 (16) 和 默認負載因子(0.75) 的空 HashMap，是 Java Collection Framework 規范推薦提供的，其源碼如下：
/*** Constructs an empty HashMap with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {//負載因子:用于衡量的是一個散列表的空間的使用程度this.loadFactor = DEFAULT_LOAD_FACTOR; //HashMap進行擴容的閾值，它的值等于 HashMap 的容量乘以負載因子threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);// HashMap的底層實現仍是數組，只是數組的每一項都是一條鏈table = new Entry[DEFAULT_INITIAL_CAPACITY];init();}2、HashMap(int initialCapacity, float loadFactor)：
該構造函數意在構造一個 指定初始容量 和 指定負載因子的空 HashMap，其源碼如下：
/*** Constructs an empty HashMap with the specified initial capacity and load factor.*/public HashMap(int initialCapacity, float loadFactor) {//初始容量不能小于 0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);//初始容量不能超過 2^30if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//負載因子不能小于 0 if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// HashMap 的容量必須是2的冪次方，超過 initialCapacity 的最小 2^n int capacity = 1;while (capacity < initialCapacity)capacity <<= 1; //負載因子this.loadFactor = loadFactor;//設置HashMap的容量極限，當HashMap的容量達到該極限時就會進行自動擴容操作threshold = (int)(capacity * loadFactor);// HashMap的底層實現仍是數組，只是數組的每一項都是一條鏈table = new Entry[capacity];init();}3、HashMap(int initialCapacity)：
該構造函數意在構造一個指定初始容量和默認負載因子 (0.75)的空 HashMap，其源碼如下：
// Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75)public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); // 直接調用上述構造函數}4、HashMap(Map<? extends K, ? extends V> m)
該構造函數意在構造一個與指定 Map 具有相同映射的 HashMap，其 初始容量不小于 16 (具體依賴于指定Map的大小)，負載因子是 0.75，是 Java Collection Framework 規范推薦提供的，其源碼如下：
// Constructs a new HashMap with the same mappings as the specified Map. // The HashMap is created with default load factor (0.75) and an initial capacity// sufficient to hold the mappings in the specified Map.public HashMap(Map<? extends K, ? extends V> m) {// 初始容量不小于 16 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);putAllForCreate(m);}在這里，我們提到了兩個非常重要的參數：初始容量 和 負載因子，這兩個參數是影響HashMap性能的重要參數。其中，容量表示哈希表中桶的數量 (table 數組的大小)，初始容量是創建哈希表時桶的數量；負載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。
對于使用 拉鏈法（下文會提到）的哈希表來說，查找一個元素的平均時間是 O(1+a)，a 指的是鏈的長度，是一個常數。特別地，若負載因子越大，那么對空間的利用更充分，但查找效率的也就越低；若負載因子越小，那么哈希表的數據將越稀疏，對空間造成的浪費也就越嚴重。系統默認負載因子為 0.75，這是時間和空間成本上一種折衷，一般情況下我們是無需修改的。
四、HashMap的數據結構：
1、哈希的相關概念：
Hash 就是把任意長度的輸入(又叫做預映射， pre-image)，通過哈希算法，變換成固定長度的輸出(通常是整型)，該輸出就是哈希值。這種轉換是一種 壓縮映射 ，也就是說，散列值的空間通常遠小于輸入的空間。不同的輸入可能會散列成相同的輸出，從而不可能從散列值來唯一的確定輸入值。簡單的說，就是一種將任意長度的消息壓縮到某一固定長度的息摘要函數。
2、哈希的應用：數據結構
我們知道，數組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入和刪除也容易的數據結構呢？答案是肯定的，這就是我們要提起的哈希表。事實上，哈希表有多種不同的實現方法，我們接下來解釋的是最經典的一種方法 —— 拉鏈法，我們可以將其理解為 鏈表的數組，如下圖所示：
我們可以從上圖看到，左邊很明顯是個數組，數組的每個成員是一個鏈表。該數據結構所容納的所有元素均包含一個指針，用于元素間的鏈接。我們根據元素的自身特征把元素分配到不同的鏈表中去，反過來我們也正是通過這些特征找到正確的鏈表，再從鏈表中找出正確的元素。其中，根據元素特征計算元素數組下標的方法就是 哈希算法。
總的來說，哈希表適合用作快速查找、刪除的基本數據結構，通常需要總數據量可以放入內存。在使用哈希表時，有以下幾個關鍵點：
- hash 函數（哈希算法）的選擇：針對不同的對象(字符串、整數等)具體的哈希方法；
- 碰撞處理：常用的有兩種方式，一種是open hashing，即 >拉鏈法；另一種就是 closed hashing，即開地址法(opened addressing)。
3、HashMap的數據結構：
我們知道，在Java中最常用的兩種結構是?數組?和?鏈表，幾乎所有的數據結構都可以利用這兩種來組合實現，HashMap 就是這種應用的一個典型。實際上，HashMap 就是一個?鏈表數組，如下是它數據結構：
從上圖中，我們可以形象地看出HashMap底層實現還是數組，只是數組的每一項都是一條鏈。其中參數initialCapacity 就代表了該數組的長度，也就是桶的個數。在第三節我們已經了解了HashMap 的默認構造函數的源碼：
/*** Constructs an empty HashMap with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {//負載因子:用于衡量的是一個散列表的空間的使用程度this.loadFactor = DEFAULT_LOAD_FACTOR; //HashMap進行擴容的閾值，它的值等于 HashMap 的容量乘以負載因子threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);// HashMap的底層實現仍是數組，只是數組的每一項都是一條鏈table = new Entry[DEFAULT_INITIAL_CAPACITY];init();}從上述源碼中我們可以看出，每次新建一個HashMap時，都會初始化一個Entry類型的table數組，其中 Entry類型的定義如下：
static class Entry<K,V> implements Map.Entry<K,V> {final K key; // 鍵值對的鍵V value; // 鍵值對的值Entry<K,V> next; // 下一個節點final int hash; // hash(key.hashCode())方法的返回值/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) { // Entry 的構造函數value = v;next = n;key = k;hash = h;}......}其中，Entry為HashMap的內部類，實現了 Map.Entry 接口，其包含了鍵key、值value、下一個節點next，以及hash值四個屬性。事實上，Entry 是構成哈希表的基石，是哈希表所存儲的元素的具體形式。
五、HashMap 的快速存取：
在HashMap中，我們最常用的兩個操作就是：put(Key,Value) 和 get(Key)。我們都知道，HashMap中的Key是唯一的，那它是如何保證唯一性的呢？我們首先想到的是用equals比較，沒錯，這樣可以實現，但隨著元素的增多，put 和 get 的效率將越來越低，這里的時間復雜度是O(n)。也就是說，假如 HashMap 有1000個元素，那么 put時就需要比較 1000 次，這是相當耗時的，遠達不到HashMap快速存取的目的。實際上，HashMap 很少會用到equals方法，因為其內通過一個哈希表管理所有元素，利用哈希算法可以快速的存取元素。當我們調用put方法存值時，HashMap首先會調用Key的hashCode方法，然后基于此獲取Key哈希碼，通過哈希碼快速找到某個桶，這個位置可以被稱之為 bucketIndex。通過hashCode的協定可以知道，如果兩個對象的hashCode不同，那么equals一定為 false；否則，如果其hashCode相同，equals也不一定為 true。所以，理論上，hashCode 可能存在碰撞的情況，當碰撞發生時，這時會取出bucketIndex桶內已存儲的元素，并通過hashCode() 和 equals() 來逐個比較以判斷Key是否已存在。如果已存在，則使用新Value值替換舊Value值，并返回舊Value值；如果不存在，則存放新的鍵值對<Key, Value>到桶中。因此，在 HashMap中，equals() 方法只有在哈希碼碰撞時才會被用到。
下面我們結合JDK源碼看HashMap 的存取實現。
1、HashMap的存儲實現：
在 HashMap 中，鍵值對的存儲是通過 put(key,vlaue) 方法來實現的，其源碼如下：
/*** Associates the specified value with the specified key in this map.* If the map previously contained a mapping for the key, the old* value is replaced.** @param key key with which the specified value is to be associated* @param value value to be associated with the specified key* @return the previous value associated with key, or null if there was no mapping for key.* Note that a null return can also indicate that the map previously associated null with key.*/public V put(K key, V value) {//當key為null時，調用putForNullKey方法，并將該鍵值對保存到table的第一個位置 if (key == null)return putForNullKey(value); //根據key的hashCode計算hash值int hash = hash(key.hashCode()); // ------- (1)//計算該鍵值對在數組中的存儲位置（哪個桶）int i = indexFor(hash, table.length); // ------- (2)//在table的第i個桶上進行迭代，尋找 key 保存的位置for (Entry<K,V> e = table[i]; e != null; e = e.next) { // ------- (3)Object k;//判斷該條鏈上是否存在hash值相同且key值相等的映射，若存在，則直接覆蓋 value，并返回舊valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue; // 返回舊值}}modCount++; //修改次數增加1，快速失敗機制//原HashMap中無該映射，將該添加至該鏈的鏈頭addEntry(hash, key, value, i); return null;}通過上述源碼我們可以清楚了解到HashMap保存數據的過程。首先，判斷key是否為null，若為null，則直接調用putForNullKey方法；若不為空，則先計算key的hash值，然后根據hash值搜索在table數組中的索引位置，如果table數組在該位置處有元素，則查找是否存在相同的key，若存在則覆蓋原來key的value，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。此外，若table在該處沒有元素，則直接保存。這個過程看似比較簡單，但其實有很多需要回味的地方，下面我們一一來看。
先看源碼中的 (3) 處，此處迭代原因就是為了防止存在相同的key值。如果發現兩個hash值（key）相同時，HashMap的處理方式是用新value替換舊value，這里并沒有處理key，這正好解釋了 HashMap 中沒有兩個相同的 key。
1). 對NULL鍵的特別處理：putForNullKey()
我們直接看其源碼：
/*** Offloaded version of put for null keys*/private V putForNullKey(V value) {// 若key==null，則將其放入table的第一個桶，即 table[0]for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { // 若已經存在key為null的鍵，則替換其值，并返回舊值V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++; // 快速失敗addEntry(0, null, value, 0); // 否則，將其添加到 table[0] 的桶中return null;}通過上述源碼我們可以清楚知到，HashMap 中可以保存鍵為NULL的鍵值對，且該鍵值對是唯一的。若再次向其中添加鍵為NULL的鍵值對，將覆蓋其原值。此外，如果HashMap中存在鍵為NULL的鍵值對，那么一定在第一個桶中。
2). HashMap 中的哈希策略（算法）
在上述的 put(key,vlaue) 方法的源碼中，我們標出了 HashMap 中的哈希策略（即(1)、(2)兩處），hash() 方法用于對Key的hashCode進行重新計算，而 indexFor() 方法用于生成這個Entry對象的插入位置。當計算出來的hash值與hashMap的(length-1)做了&運算后，會得到位于區間[0，length-1]的一個值。特別地，這個值分布的越均勻， HashMap 的空間利用率也就越高，存取效率也就越好。
我們首先看(1)處的 hash() 方法，該方法為一個純粹的數學計算，用于進一步計算key的hash值，源碼如下：
/*** Applies a supplemental hash function to a given hashCode, which* defends against poor quality hash functions. This is critical* because HashMap uses power-of-two length hash tables, that* otherwise encounter collisions for hashCodes that do not differ* in lower bits. * * Note: Null keys always map to hash 0, thus index 0.*/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);}正如JDK官方對該方法的描述那樣，使用hash()方法對一個對象的hashCode進行重新計算是為了防止質量低下的hashCode()函數實現。由于hashMap的支撐數組長度總是 2 的冪次，通過右移可以使低位的數據盡量的不同，從而使hash值的分布盡量均勻。
通過上述hash()方法計算得到 Key 的 hash值 后，怎么才能保證元素均勻分布到table的每個桶中呢？我們會想到取模，但是由于取模的效率較低，HashMap 是通過調用(2)處的indexFor()方法處理的，其不但簡單而且效率很高，對應源碼如下所示：
/*** Returns index for hash code h.*/static int indexFor(int h, int length) {return h & (length-1); // 作用等價于取模運算，但這種方式效率更高}我們知道，HashMap的底層數組長度總是2的n次方。當length為2的n次方時，h&(length - 1)就相當于對length取模，而且速度比直接取模要快得多，這是HashMap在速度上的一個優化。至于HashMap的底層數組長度為什么是2的n次方，下一節將給出解釋。
總而言之，上述的hash()方法和indexFor()方法的作用只有一個：保證元素均勻分布到table的每個桶中以便充分利用空間。
3). HashMap 中鍵值對的添加：addEntry()?
我們直接看其源碼：
通過上述源碼我們可以清楚地了解到 鏈的產生時機。HashMap 總是將新的Entry對象添加到bucketIndex處，若bucketIndex處已經有了Entry對象，那么新添加的Entry對象將指向原有的Entry對象，并形成一條新的以它為鏈頭的Entry鏈；但是，若bucketIndex處原先沒有Entry對象，那么新添加的Entry對象將指向 null，也就生成了一條長度為 1 的全新的Entry鏈了。HashMap 永遠都是在鏈表的表頭添加新元素。此外，若HashMap中元素的個數超過極限值 threshold，其將進行擴容操作，一般情況下，容量將擴大至原來的兩倍。
4). HashMap 的擴容：resize()
隨著HashMap中元素的數量越來越多，發生碰撞的概率將越來越大，所產生的子鏈長度就會越來越長，這樣勢必會影響HashMap的存取速度。為了保證HashMap的效率，系統必須要在某個臨界點進行擴容處理，該臨界點就是HashMap中元素的數量在數值上等于threshold（table數組長度*加載因子）。但是，不得不說，擴容是一個非常耗時的過程，因為它需要重新計算這些元素在新table數組中的位置并進行復制處理。所以，如果我們能夠提前預知HashMap 中元素的個數，那么在構造HashMap時預設元素的個數能夠有效的提高HashMap的性能。我們直接看其源碼：
?
? ? ? 該方法的作用及觸發動機如下：
Rehashes the contents of this map into a new array with a larger capacity. This method is called automatically when the number of keys in this map reaches its threshold.
5). HashMap 的重哈希：transfer()
重哈希的主要是一個重新計算原HashMap中的元素在新table數組中的位置并進行復制處理的過程，我們直接看其源碼：
/*** Transfers all entries from current table to newTable.*/void transfer(Entry[] newTable) {// 將原數組 table 賦給數組 srcEntry[] src = table;int newCapacity = newTable.length;// 將數組 src 中的每條鏈重新添加到 newTable 中for (int j = 0; j < src.length; j++) {Entry<K,V> e = src[j];if (e != null) {src[j] = null; // src 回收// 將每條鏈的每個元素依次添加到 newTable 中相應的桶中do {Entry<K,V> next = e.next;// e.hash指的是 hash(key.hashCode())的返回值;// 計算在newTable中的位置，注意原來在同一條子鏈上的元素可能被分配到不同的子鏈int i = indexFor(e.hash, newCapacity); e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);}}}特別需要注意的是，在重哈希的過程中，原屬于一個桶中的Entry對象可能被分到不同的桶，因為HashMap 的容量發生了變化，那么 h&(length - 1) 的值也會發生相應的變化。極端地說，如果重哈希后，原屬于一個桶中的Entry對象仍屬于同一桶，那么重哈希也就失去了意義。
2、HashMap 的讀取實現：
相對于HashMap的存儲而言，讀取就顯得比較簡單了。因為，HashMap只需通過key的hash值定位到table數組的某個特定的桶，然后查找并返回該key對應的value即可，源碼如下：
/*** Returns the value to which the specified key is mapped,* or {@code null} if this map contains no mapping for the key.** <p>More formally, if this map contains a mapping from a key* {@code k} to a value {@code v} such that {@code (key==null ? k==null :* key.equals(k))}, then this method returns {@code v}; otherwise* it returns {@code null}. (There can be at most one such mapping.)** <p>A return value of {@code null} does not <i>necessarily</i>* indicate that the map contains no mapping for the key; it's also* possible that the map explicitly maps the key to {@code null}.* The {@link #containsKey containsKey} operation may be used to* distinguish these two cases.** @see #put(Object, Object)*/public V get(Object key) {// 若為null，調用getForNullKey方法返回相對應的valueif (key == null)// 從table的第一個桶中尋找 key 為 null 的映射；若不存在，直接返回nullreturn getForNullKey(); // 根據該 key 的 hashCode 值計算它的 hash 碼 int hash = hash(key.hashCode());// 找出 table 數組中對應的桶for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;//若搜索的key與查找的key相同，則返回相對應的valueif (e.hash == hash && ((k = e.key) == key || key.equals(k)))return e.value;}return null;}在這里能夠根據key快速的取到value，除了和HashMap的數據結構密不可分外，還和Entry有莫大的關系。在前面就已經提到過，HashMap在存儲過程中并沒有將key，value分開來存儲，而是當做一個整體key-value來處理的，這個整體就是Entry對象。特別地，在Entry對象中，value的地位要比key低一些，相當于是 key 的附屬。
其中，針對鍵為NULL的鍵值對，HashMap 提供了專門的處理：getForNullKey()，其源碼如下：
/*** Offloaded version of get() to look up null keys. Null keys map* to index 0. This null case is split out into separate methods* for the sake of performance in the two most commonly used* operations (get and put), but incorporated with conditionals in* others.*/private V getForNullKey() {// 鍵為NULL的鍵值對若存在，則必定在第一個桶中for (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null)return e.value;}// 鍵為NULL的鍵值對若不存在，則直接返回 nullreturn null;}因此，調用HashMap的get(Object key)方法后，若返回值是 NULL，則存在如下兩種可能：
- 該 key 對應的值就是 null;
- HashMap 中不存在該 key。
3、HashMap 存取小結
在存儲的過程中，系統根據key的hash值來定位Entry在table數組中的哪個桶，并且將其放到對應的鏈表的鏈頭；在取的過程中，同樣根據key的hash值來定位Entry在table數組中的哪個桶，然后在該桶中查找并返回。
六、HashMap 的底層數組長度為何總是2的n次方？
我們知道，HashMap的底層數組長度總是2的n次方，原因是 HashMap 在其構造函數 HashMap(int initialCapacity, float loadFactor) 中作了特別的處理，如下面的代碼所示。當底層數組的length為2的n次方時， h&(length - 1) 就相當于對length取模，其效率要比直接取模高得多，這是HashMap在效率上的一個優化。
?
在上文已經提到過，HashMap 中的數據結構是一個數組鏈表，我們希望的是元素存放的越均勻越好。最理想的效果是，Entry數組中每個位置都只有一個元素，這樣，查詢的時候效率最高，不需要遍歷單鏈表，也不需要通過equals去比較Key，而且空間利用率最大。
那如何計算才會分布最均勻呢？正如上一節提到的，HashMap采用了一個分兩步走的哈希策略：
使用 hash() 方法用于對Key的hashCode進行重新計算，以防止質量低下的hashCode()函數實現。由于hashMap的支撐數組長度總是 2 的倍數，通過右移可以使低位的數據盡量的不同，從而使Key的hash值的分布盡量均勻；
使用 indexFor() 方法進行取余運算，以使Entry對象的插入位置盡量分布均勻(下文將專門對此闡述)。
對于取余運算，我們首先想到的是：哈希值%length = bucketIndex。但當底層數組的length為2的n次方時， h&(length - 1) 就相當于對length取模，而且速度比直接取模快得多，這是HashMap在速度上的一個優化。除此之外，HashMap 的底層數組長度總是2的n次方的主要原因是什么呢？
這里，我們假設length分別為16(2^4) 和 15，h 分別為 5、6、7。
我們可以看到，當n=15時，6和7的結果一樣，即它們位于table的同一個桶中，也就是產生了碰撞，6、7就會在這個桶中形成鏈表，這樣就會導致查詢速度降低。誠然這里只分析三個數字不是很多，那么我們再看 h 分別取 0-15時的情況。
從上面的圖表中我們可以看到，當 length 為15時總共發生了8次碰撞，同時發現空間浪費非常大，因為在 1、3、5、7、9、11、13、15 這八處沒有存放數據。這是因為hash值在與14（即 1110）進行&運算時，得到的結果最后一位永遠都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置處是不可能存儲數據的。這樣，空間的減少會導致碰撞幾率的進一步增加，從而就會導致查詢速度慢。
而當length為16時，length – 1 = 15， 即 1111，那么，在進行低位&運算時，值總是與原來hash值相同，而進行高位運算時，其值等于其低位值。所以，當 length=2^n 時，不同的hash值發生碰撞的概率比較小，這樣就會使得數據在table數組中分布較均勻，查詢速度也較快。
因此，總的來說，HashMap 的底層數組長度總是2的n次方的原因有兩個，即當 length=2^n 時：
- 不同的hash值發生碰撞的概率比較小，這樣就會使得數據在table數組中分布較均勻，空間利用率較高，查詢速度也較快；
- h&(length - 1) 就相當于對length取模，而且在速度、效率上比直接取模要快得多，即二者是等價不等效的，這是HashMap在速度和效率上的一個優化。
總結
以上是生活随笔為你收集整理的Java集合篇：HashMap原理详解（JDK1.7及之前的版本）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java集合篇：LinkedList源码
- 下一篇： Java集合篇：ConcurrentHa