該篇文章主要對(duì)HashMap進(jìn)行深入探索，主要探索內(nèi)容為
一、HashMap介紹
二、HashMap構(gòu)造方法（初始容量，負(fù)載因子）；
三、HashMap數(shù)據(jù)結(jié)構(gòu)；
四、HashMap put方法(hash算法，index算法，擴(kuò)容，重哈希)；
五、HashMap get方法；
六、簡(jiǎn)單舉例hash算法和indexFor算法
一、HashMap介紹
HashMap是Map族中最為常用的一種，也是 Java Collection Framework 的重要成員。
HashMap是基于哈希表實(shí)現(xiàn)的，每一個(gè)元素都是一個(gè)key-value對(duì)，其內(nèi)部通過(guò)單鏈表解決沖突問(wèn)題，容量不足（超過(guò)了閾值）時(shí)，同樣會(huì)自動(dòng)增長(zhǎng)。
HashMap是非線程安全的，只是用于單線程環(huán)境下，多線程環(huán)境下可以采用concurrent并發(fā)包下的concurrentHashMap。
HashMap實(shí)現(xiàn)了Serializable接口，因此它支持序列化，實(shí)現(xiàn)了Cloneable接口，能被克隆。
HashMap最多只允許一條Entry的鍵為Null(多條會(huì)覆蓋)，但允許多條Entry的值為Null。
二、HashMap構(gòu)造方法
HashMap 一共提供了四個(gè)構(gòu)造函數(shù)，其中 默認(rèn)無(wú)參的構(gòu)造函數(shù) 和 參數(shù)為Map的構(gòu)造函數(shù) 為 Java Collection Framework 規(guī)范的推薦實(shí)現(xiàn)，其余兩個(gè)構(gòu)造函數(shù)則是 HashMap 專門提供的。
1、HashMap()
該構(gòu)造函數(shù)意在構(gòu)造一個(gè)具有默認(rèn)初始容量 (16) 和 默認(rèn)負(fù)載因子(0.75) 的空 HashMap，是 Java Collection Framework 規(guī)范推薦提供的，其源碼如下：
/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap(){
//負(fù)載因子:用于衡量的是一個(gè)散列表的空間的使用程度
this.loadFactor=DEFAULT_LOAD_FACTOR;
//HashMap進(jìn)行擴(kuò)容的閾值，它的值等于 HashMap 的容量乘以負(fù)載因子
threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
// HashMap的底層實(shí)現(xiàn)仍是數(shù)組，只是數(shù)組的每一項(xiàng)都是一條鏈
table=newEntry[DEFAULT_INITIAL_CAPACITY];
init();
}
2、HashMap(int initialCapacity, float loadFactor)
該構(gòu)造函數(shù)意在構(gòu)造一個(gè) 指定初始容量 和 指定負(fù)載因子的空 HashMap，其源碼如下：
/**
* Constructs an empty HashMap with the specified initial capacity and load factor.
*/
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于 0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//初始容量不能超過(guò) 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負(fù)載因子不能小于 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
// HashMap 的容量必須是2的冪次方，超過(guò) initialCapacity 的最小 2^n
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
//負(fù)載因子
this.loadFactor = loadFactor;
//設(shè)置HashMap的容量極限，當(dāng)HashMap的容量達(dá)到該極限時(shí)就會(huì)進(jìn)行自動(dòng)擴(kuò)容操作
threshold = (int)(capacity * loadFactor);
// HashMap的底層實(shí)現(xiàn)仍是數(shù)組，只是數(shù)組的每一項(xiàng)都是一條鏈
table = new Entry[capacity];
init();
}
3、HashMap(int initialCapacity)
該構(gòu)造函數(shù)意在構(gòu)造一個(gè)指定初始容量和默認(rèn)負(fù)載因子 (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); // 直接調(diào)用上述構(gòu)造函數(shù)
}
4、HashMap(Map<? extends K, ? extends V> m)
該構(gòu)造函數(shù)意在構(gòu)造一個(gè)與指定 Map 具有相同映射的 HashMap，其 初始容量不小于 16 (具體依賴于指定Map的大小)，負(fù)載因子是 0.75，是 Java Collection Framework 規(guī)范推薦提供的，其源碼如下：
// 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);
}
在這里，我們提到了兩個(gè)非常重要的參數(shù)：初始容量 和 負(fù)載因子，這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)。其中，容量表示哈希表中桶的數(shù)量 (table 數(shù)組的大小)，初始容量是創(chuàng)建哈希表時(shí)桶的數(shù)量；負(fù)載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度，它衡量的是一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。
在這里先留下一個(gè)疑問(wèn)：
為什么達(dá)到閥值擴(kuò)容呢，而不是容量滿了再擴(kuò)容呢
三、HashMap的數(shù)據(jù)結(jié)構(gòu)
哈希的相關(guān)概念
Hash 就是把任意長(zhǎng)度的輸入(又叫做預(yù)映射， pre-image)，通過(guò)哈希算法，變換成固定長(zhǎng)度的輸出(通常是整型)，該輸出就是哈希值。這種轉(zhuǎn)換是一種 壓縮映射 ，也就是說(shuō)，散列值的空間通常遠(yuǎn)小于輸入的空間。不同的輸入可能會(huì)散列成相同的輸出，從而不可能從散列值來(lái)唯一的確定輸入值。簡(jiǎn)單的說(shuō)，就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的息摘要函數(shù)。
哈希的應(yīng)用：數(shù)據(jù)結(jié)構(gòu)
我們知道，數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入和刪除也容易的數(shù)據(jù)結(jié)構(gòu)呢？答案是肯定的，這就是我們要提起的哈希表。事實(shí)上，哈希表有多種不同的實(shí)現(xiàn)方法，我們接下來(lái)解釋的是最經(jīng)典的一種方法 —— 拉鏈法，我們可以將其理解為 鏈表的數(shù)組，如下圖所示：
我們可以從上圖看到，左邊很明顯是個(gè)數(shù)組，數(shù)組的每個(gè)成員是一個(gè)鏈表。該數(shù)據(jù)結(jié)構(gòu)所容納的所有元素均包含一個(gè)指針，用于元素間的鏈接。我們根據(jù)元素的自身特征把元素分配到不同的鏈表中去，反過(guò)來(lái)我們也正是通過(guò)這些特征找到正確的鏈表，再?gòu)逆湵碇姓页稣_的元素。其中，根據(jù)元素特征計(jì)算元素?cái)?shù)組下標(biāo)的方法就是哈希算法。
總的來(lái)說(shuō)，哈希表適合用作快速查找、刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存。在使用哈希表時(shí)，有以下幾個(gè)關(guān)鍵點(diǎn)：
- hash 函數(shù)（哈希算法）的選擇：針對(duì)不同的對(duì)象(字符串、整數(shù)等)具體的哈希方法；
- 碰撞處理：常用的有兩種方式，一種是open hashing，即 >拉鏈法；
- 另一種就是 closed hashing，即開(kāi)地址法(opened addressing)。
HashMap 的數(shù)據(jù)結(jié)構(gòu)
我們知道，在Java中最常用的兩種結(jié)構(gòu)是 數(shù)組 和 鏈表，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來(lái)組合實(shí)現(xiàn)，HashMap 就是這種應(yīng)用的一個(gè)典型。實(shí)際上，HashMap 就是一個(gè) 鏈表數(shù)組，如下是它數(shù)據(jù)結(jié)構(gòu)：
從上圖中，我們可以形象地看出HashMap底層實(shí)現(xiàn)還是數(shù)組，只是數(shù)組的每一項(xiàng)都是一條鏈。其中參數(shù)initialCapacity 就代表了該數(shù)組的長(zhǎng)度，也就是桶的個(gè)數(shù)。在第三節(jié)我們已經(jīng)了解了HashMap 的默認(rèn)構(gòu)造函數(shù)的源碼：
/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
//負(fù)載因子:用于衡量的是一個(gè)散列表的空間的使用程度
this.loadFactor = DEFAULT_LOAD_FACTOR;
//HashMap進(jìn)行擴(kuò)容的閾值，它的值等于 HashMap 的容量乘以負(fù)載因子
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// HashMap的底層實(shí)現(xiàn)仍是數(shù)組，只是數(shù)組的每一項(xiàng)都是一條鏈
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
從上述源碼中我們可以看出，每次新建一個(gè)HashMap時(shí)，都會(huì)初始化一個(gè)Entry類型的table數(shù)組，其中 Entry類型的定義如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 鍵值對(duì)的鍵
V value; // 鍵值對(duì)的值
Entry<K,V> next; // 下一個(gè)節(jié)點(diǎn)
final int hash; // hash(key.hashCode())方法的返回值
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) { // Entry 的構(gòu)造函數(shù)
value = v;
next = n;
key = k;
hash = h;
}
......
}
其中，Entry為HashMap的內(nèi)部類，實(shí)現(xiàn)了 Map.Entry 接口，其包含了鍵key、值value、下一個(gè)節(jié)點(diǎn)next，以及hash值四個(gè)屬性。事實(shí)上，Entry 是構(gòu)成哈希表的基石，是哈希表所存儲(chǔ)的元素的具體形式。
四、HashMap put方法
下面我們結(jié)合JDK源碼看HashMap 的存取實(shí)現(xiàn)。
HashMap 的存儲(chǔ)實(shí)現(xiàn)
在 HashMap 中，鍵值對(duì)的存儲(chǔ)是通過(guò) put(key,vlaue) 方法來(lái)實(shí)現(xiàn)的，其源碼如下：
/**
* 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) {
//當(dāng)key為null時(shí)，調(diào)用putForNullKey方法，并將該鍵值對(duì)保存到table的第一個(gè)位置
if (key == null)
return putForNullKey(value);
//根據(jù)key的hashCode計(jì)算hash值
int hash = hash(key.hashCode()); // ------- (1)
//計(jì)算該鍵值對(duì)在數(shù)組中的存儲(chǔ)位置（哪個(gè)桶）
int i = indexFor(hash, table.length); // ------- (2)
//在table的第i個(gè)桶上進(jìn)行迭代，尋找 key 保存的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // ------- (3)
Object k;
//判斷該條鏈上是否存在hash值相同且key值相等的映射，若存在，則直接覆蓋 value，并返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue; // 返回舊值
}
}
modCount++; //修改次數(shù)增加1，快速失敗機(jī)制
//原HashMap中無(wú)該映射，將該添加至該鏈的鏈頭
addEntry(hash, key, value, i);
return null;
}
對(duì)NULL鍵的特別處理：putForNullKey()
我們直接看其源碼：
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
// 若key==null，則將其放入table的第一個(gè)桶，即 table[0]
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) { // 若已經(jīng)存在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 中的哈希策略（算法）
/**
* 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官方對(duì)該方法的描述那樣，使用hash()方法對(duì)一個(gè)對(duì)象的hashCode進(jìn)行重新計(jì)算是為了防止質(zhì)量低下的hashCode()函數(shù)實(shí)現(xiàn)。由于hashMap的支撐數(shù)組長(zhǎng)度總是 2 的冪次，通過(guò)右移可以使低位的數(shù)據(jù)盡量的不同，從而使hash值的分布盡量均勻。
通過(guò)上述hash()方法計(jì)算得到 Key 的 hash值 后，怎么才能保證元素均勻分布到table的每個(gè)桶中呢？我們會(huì)想到取模，但是由于取模的效率較低，HashMap 是通過(guò)調(diào)用上面的indexFor()方法處理的，其不但簡(jiǎn)單而且效率很高，對(duì)應(yīng)源碼如下所示：
/**
* Returns index for hash code h.
*/
static int indexFor( int h, int length )
{
return(h & (length - 1) ); /* 作用等價(jià)于取模運(yùn)算，但這種方式效率更高 */
}
HashMap 中鍵值對(duì)的添加：addEntry()
我們直接看其源碼：
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*
* 永遠(yuǎn)都是在鏈表的表頭添加新元素
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//獲取bucketIndex處的鏈表
Entry<K,V> e = table[bucketIndex];
//將新創(chuàng)建的 Entry 鏈入 bucketIndex處的鏈表的表頭
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//若HashMap中元素的個(gè)數(shù)超過(guò)極限值 threshold，則容量擴(kuò)大兩倍
if (size++ >= threshold)
resize(2 * table.length);
}
HashMap 的擴(kuò)容：resize()
隨著HashMap中元素的數(shù)量越來(lái)越多，發(fā)生碰撞的概率將越來(lái)越大，所產(chǎn)生的子鏈長(zhǎng)度就會(huì)越來(lái)越長(zhǎng)，這樣勢(shì)必會(huì)影響HashMap的存取速度。為了保證HashMap的效率，系統(tǒng)必須要在某個(gè)臨界點(diǎn)進(jìn)行擴(kuò)容處理，該臨界點(diǎn)就是HashMap中元素的數(shù)量在數(shù)值上等于threshold（table數(shù)組長(zhǎng)度乘以加載因子）。但是，不得不說(shuō)，擴(kuò)容是一個(gè)非常耗時(shí)的過(guò)程，因?yàn)樗枰匦掠?jì)算這些元素在新table數(shù)組中的位置并進(jìn)行復(fù)制處理。所以，如果我們能夠提前預(yù)知HashMap 中元素的個(gè)數(shù)，那么在構(gòu)造HashMap時(shí)預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能（已解答之前的疑問(wèn)：為什么閥值呢，而不是容量滿了再擴(kuò)容呢）。我們直接看其源碼：
/**
* 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.
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
*
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value is irrelevant).
*
*/
void resize( int newCapacity )
{
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
/* 若 oldCapacity 已達(dá)到最大值，直接將 threshold 設(shè)為 Integer.MAX_VALUE */
if ( oldCapacity == MAXIMUM_CAPACITY )
{
threshold = Integer.MAX_VALUE;
return; /* 直接返回 */
}
/* 否則，創(chuàng)建一個(gè)更大的數(shù)組 */
Entry[] newTable = new Entry[newCapacity];
/* 將每條Entry重新哈希到新的數(shù)組中 */
transfer( newTable );
table = newTable;
threshold = (int) (newCapacity * loadFactor); /* 重新設(shè)定 threshold */
}
HashMap 的重哈希：transfer()
重哈希的主要是一個(gè)重新計(jì)算原HashMap中的元素在新table數(shù)組中的位置并進(jìn)行復(fù)制處理的過(guò)程，我們直接看其源碼：
/**
*
* Transfers all entries from current table to newTable.
*
*/
void transfer( Entry[] newTable ){
/* 將原數(shù)組 table 賦給數(shù)組 src */
Entry[] src = table;
int newCapacity = newTable.length;
/* 將數(shù)組 src 中的每條鏈重新添加到 newTable 中 */
for ( int j = 0; j < src.length; j++ ){
Entry<K, V> e = src[j];
if ( e != null ){
src[j] = null; /* src 回收 */
/* 將每條鏈的每個(gè)元素依次添加到 newTable 中相應(yīng)的桶中 */
do {
Entry<K, V> next = e.next;
/* e.hash指的是 hash(key.hashCode())的返回值; */
/* 計(jì)算在newTable中的位置，注意原來(lái)在同一條子鏈上的元素可能被分配到不同的子鏈 */
int i = indexFor( e.hash, newCapacity );
e.next = newTable[i];
newTable[i] = e;
e = next;
}
while ( e != null );
}
}
}
特別需要注意的是，在重哈希的過(guò)程中，原屬于一個(gè)桶中的Entry對(duì)象可能被分到不同的桶，因?yàn)镠ashMap 的容量發(fā)生了變化，那么 h&(length - 1) 的值也會(huì)發(fā)生相應(yīng)的變化。極端地說(shuō)，如果重哈希后，原屬于一個(gè)桶中的Entry對(duì)象仍屬于同一桶，那么重哈希也就失去了意義。
HashMap get方法
相對(duì)于HashMap的存儲(chǔ)而言，讀取就顯得比較簡(jiǎn)單了。因?yàn)椋琀ashMap只需通過(guò)key的hash值定位到table數(shù)組的某個(gè)特定的桶，然后查找并返回該key對(duì)應(yīng)的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，調(diào)用getForNullKey方法返回相對(duì)應(yīng)的value */
if ( key == null )
/* 從table的第一個(gè)桶中尋找 key 為 null 的映射；若不存在，直接返回null */
return(getForNullKey() );
/* 根據(jù)該 key 的 hashCode 值計(jì)算它的 hash 碼 */
int hash = hash( key.hashCode() );
/* 找出 table 數(shù)組中對(duì)應(yīng)的桶 */
for ( Entry<K, V> e = table[indexFor( hash, table.length )];e != null;e = e.next ){
Object k;
/* 若搜索的key與查找的key相同，則返回相對(duì)應(yīng)的value */
if ( e.hash == hash && ( (k = e.key) == key || key.equals( k ) ) )
return(e.value);
}
return(null);
}
針對(duì)鍵為NULL的鍵值對(duì)，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的鍵值對(duì)若存在，則必定在第一個(gè)桶中 */
for ( Entry<K, V> e = table[0]; e != null; e = e.next )
{
if ( e.key == null )
return(e.value);
}
/* 鍵為NULL的鍵值對(duì)若不存在，則直接返回 null */
return(null);
}
因此，調(diào)用HashMap的get(Object key)方法后，若返回值是 NULL，則存在如下兩種可能：
1.該 key 對(duì)應(yīng)的值就是 null;
2.HashMap 中不存在該 key
六、簡(jiǎn)單舉例hash算法和indexFor算法
哈希函數(shù)是通過(guò)把key的hash值映射到數(shù)組中的一個(gè)位置來(lái)進(jìn)行訪問(wèn)。比如：
存在一組哈希值 10，13，7，5，4，20
存在一個(gè)長(zhǎng)度為10的數(shù)組 arrays
定義一個(gè)hash函數(shù) int index = h % arrays.length;
10 % 10 = 0 那么 哈希值為10的對(duì)象放在數(shù)組索引為0的位置上；
13 % 10 = 3 那么 哈希值為13的對(duì)象放在數(shù)組索引為3的位置上；
......
20 % 10 = 0 那么 哈希值為13的對(duì)象放在數(shù)組索引為0的位置上；
這時(shí)候大家看出了一個(gè)問(wèn)題，哈希值為10的對(duì)象和哈希值為20的對(duì)象，放在了一個(gè)索引上。發(fā)生了碰撞，那么怎么解決這樣碰撞呢，有很多種方式，這里不展開(kāi)敘述。HashMap中維護(hù)了一個(gè)鏈表組成的數(shù)組。如果沖突的話就添加到鏈表中，下面來(lái)看下hashmap中的hash算法，以Java8源碼為例（各Java版本的hash算法可能存在差異）。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
其中，key.hashCode（）是Key自帶的hashCode()方法，返回一個(gè)int類型的散列值。我們大家知道，32位帶符號(hào)的int表值范圍從-2147483648到2147483648。這樣只要hash函數(shù)松散的話，一般是很難發(fā)生碰撞的，因?yàn)镠ashMap的初始容量只有16。但是這樣的散列值我們是不能直接拿來(lái)用的。用之前需要對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算。得到余數(shù)才是索引值。我們來(lái)看下HashMap中怎么實(shí)現(xiàn)的。
int index = hash & (arrays.length-1);
那么這也就明白了為什么HashMap的數(shù)組長(zhǎng)度是2的整數(shù)冪。比如以初始長(zhǎng)度為16為例，16-1 = 15，15的二進(jìn)制數(shù)位00000000 00000000 00001111?？梢钥闯鲆粋€(gè)基數(shù)二進(jìn)制最后一位必然位1，當(dāng)與一個(gè)hash值進(jìn)行與運(yùn)算時(shí)，最后一位可能是0也可能是1。但偶數(shù)與一個(gè)hash值進(jìn)行與運(yùn)算最后一位必然為0，造成有些位置永遠(yuǎn)映射不上值。
但是這時(shí)，又出現(xiàn)了一個(gè)問(wèn)題，即使散列函數(shù)很松散，但只取最后幾位碰撞也會(huì)很嚴(yán)重。這時(shí)候hash算法的價(jià)值就體現(xiàn)出來(lái)了，
hashCode右移16位，正好是32bit的一半。與自己本身做異或操作（相同為0，不同為1）。就是為了混合哈希值的高位和地位，增加低位的隨機(jī)性。并且混合后的值也變相保持了高位的特征。
如果同一個(gè)格子里的key不超過(guò)8個(gè)，使用鏈表結(jié)構(gòu)存儲(chǔ)。如果超過(guò)了8個(gè)，那么會(huì)調(diào)用treeifyBin函數(shù)，將鏈表轉(zhuǎn)換為紅黑樹(shù)，可以自己查資料了解
