1. HashMap概述：
HashMap是基于哈希表的Map接口的非同步實作（Hashtable跟HashMap很像，唯一的差別是Hashtalbe中的方法是線程安全的，也就是同步的）。此實作提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特别是它不保證該順序恒久不變。
四大關注點
| 關注點 | 結論 |
|---|---|
| 是否允許為空 | key和value都允許 |
| 是否允許資料重複 | key重複會覆寫，value可以重複 |
| 是否無序 | 無序，特别說明這個無序指的是周遊HashMap的時候，得到的元素的順序基本不可能是put的順序 |
| 線程是否安全 | 線程不安全 |
2.為什麼用HashMap？
· HashMap是一個散列桶（數組和連結清單），它存儲的内容是鍵值對(key-value)映射
· HashMap采用了數組和連結清單的資料結構，能在查詢和修改友善繼承了數組的線性查找和連結清單的尋址修改
· HashMap是非synchronized，是以HashMap很快
· HashMap可以接受null鍵和值，而Hashtable則不能（原因就是equlas()方法需要對象，因為HashMap是後出的API經過處理才可以）
3. HashMap的資料結構：
在java程式設計語言中，最基本的結構就是兩種，一個是數組，另外一個是模拟指針（引用），所有的資料結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“連結清單的數組”的資料結構，每個元素存放連結清單頭結點的數組，即數組和連結清單的結合體。
從上圖中可以看出，HashMap底層就是一個數組結構，數組中的每一項又是一個連結清單。當建立一個HashMap的時候，就會初始化一個數組。源碼如下：
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
可以看出，Entry就是數組中的元素，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用，這就構成了連結清單。
HashMap的底層主要是基于數組和連結清單來實作的，它之是以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。HashMap中主要是通過key的hashCode來計算hash值的，隻要hashCode相同，計算出來的hash值就一樣。如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的，這就出現了所謂的hash沖突。學過資料結構的同學都知道，解決hash沖突的方法有很多，HashMap底層是通過連結清單來解決hash沖突的。
圖中，紫色部分即代表哈希表，也稱為哈希數組，數組的每個元素都是一個單連結清單的頭節點，連結清單是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就将其放入單連結清單中。
對于 HashMap 及其子類而言，它們采用 Hash 算法來決定集合中元素的存儲位置。當系統開始初始化 HashMap 時，系統會建立一個長度為 capacity 的 Entry 數組，這個數組裡可以存儲元素的位置被稱為“桶（bucket）”，每個 bucket 都有其指定索引，系統可以根據其索引快速通路該 bucket 裡存儲的元素。
無論何時，HashMap 的每個“桶”隻存儲一個元素（也就是一個 Entry），由于 Entry 對象可以包含一個引用變量（就是 Entry 構造器的的最後一個參數）用于指向下一個 Entry，是以可能出現的情況是：HashMap 的 bucket 中隻有一個 Entry，但這個 Entry 指向另一個 Entry ——這就形成了一個 Entry 鍊
4. HashMap的構造函數：
4.1 HashMap()
// 1.無參構造方法、
// 構造一個空的HashMap，初始容量為16，負載因子為0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
4.2 HashMap(int initialCapacity)
// 2.構造一個初始容量為initialCapacity，負載因子為0.75的空的HashMap，
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
4.3 HashMap(int initialCapacity, float loadFactor)
// 3.構造一個空的初始容量為initialCapacity，負載因子為loadFactor的HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//最大容量
//static final int MAXIMUM_CAPACITY = 1 << 30;
在這裡提到了兩個參數：初始容量，加載因子。這兩個參數是影響HashMap性能的重要參數，其中容量表示哈希表中桶的數量，初始容量是建立哈希表時的容量，加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散清單的空間的使用程度，負載因子越大表示散清單的裝填程度越高，反之愈小。
當指定的初始容量< 0時抛出IllegalArgumentException異常，當指定的初始容量> MAXIMUM_CAPACITY時，就讓初始容量 = MAXIMUM_CAPACITY。當負載因子小于0或者不是數字時，抛出IllegalArgumentException異常。
設定threshold。 這個threshold = capacity * load factor 。當HashMap的size到了threshold時，就要進行resize，也就是擴容。
tableSizeFor()的主要功能是傳回一個比給定整數大且最接近的2的幂次方整數，如給定10，傳回2的4次方16.
我們進入tableSizeFor(int cap)的源碼中看看：
//Returns a power of two size for the given target capacity.
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
注意：HashMap要求容量必須是2的幂。
5.HashMap的存取實作
（1）存儲
public V put(K key, V value) {
//當key為null，調用putForNullKey方法，儲存null與table第一個位置中，這是HashMap允許為null的原因
if (key == null)
return putForNullKey(value);
//計算key的hash值
int hash = hash(key.hashCode()); ------(1)
//計算key hash 值在 table 數組中的位置
int i = indexFor(hash, table.length); ------(2)
//從i出開始疊代 e,找到 key 儲存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鍊上是否存在相同的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; //傳回舊值
}
}
//修改次數增加1
modCount++;
//将key、value添加至i位置處
addEntry(hash, key, value, i);
return null;
}
通過源碼我們可以清晰看到HashMap儲存資料的過程為：首先判斷key是否為null，若為null，則直接調用putForNullKey方法，将value放置在數組第一個位置上。若不為空則根據key的hashCode重新計算hash值，然後根據hash值得到這個元素在table數組中的位置（即下标），如果table數組在該位置處已經存放有其他元素了，則通過比較是否存在相同的key，若存在則覆寫原來key的value，否則将該元素儲存在鍊頭（最先儲存的元素放在鍊尾）。若table在該處沒有元素，就直接将該元素放到此數組中的該位置上。這個過程看似比較簡單，其實深有内幕。有如下幾點：
1、先看疊代處。此處疊代原因就是為了防止存在相同的key值，若發現兩個key值相同時，HashMap的處理方式是用新value替換舊value，這裡并沒有處理key，這就解釋了HashMap中沒有兩個相同的key。另外，注意一點，對比Key是否相同，是先比HashCode是否相同，HashCode相同再判斷equals是否為true，這樣大大增加了HashMap的效率(hash值看是否相同，是以效率高，equals依次對比，效率低)。
2、在看（1）、（2）處。這裡是HashMap的精華所在。首先是hash方法，該方法為一個純粹的數學計算，就是計算h的hash值。此算法加入了高位計算，防止低位不變，高位變化時，造成的hash沖突。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
為什麼要經過這樣的運算呢？這就是HashMap的高明之處。先看個例子，一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之後的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什麼，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓“1”變的均勻一點，散列的本意就是要盡量均勻分布。
我們知道對于HashMap的table而言，資料分布需要均勻（最好每項都隻有一個元素，這樣就可以直接找到），不能太緊也不能太松，太緊會導緻查詢速度慢，太松則浪費空間。計算hash值後，怎麼才能保證table元素分布均與呢？我們會想到取模，但是由于取模的消耗較大，HashMap是這樣處理的：調用indexFor方法。
static int indexFor(int h, int length) {
return h & (length-1);
}
HashMap的底層數組長度總是2的n次方，在構造函數中存在：capacity <<= 1;這樣做總是能夠保證HashMap的底層數組長度為2的n次方。當length為2的n次方時，h&(length - 1)就相當于對length取模，也就是h%length，但是&比%具有更高的效率，速度比直接取模快得多，這是HashMap在速度上的一個優化。至于為什麼是2的n次方下面解釋。
我們回到indexFor方法，該方法僅有一條語句：h&(length - 1)，這句話除了上面的取模運算外還有一個非常重要的責任：均勻分布table資料和充分利用空間。這裡我們假設length為16(2^n)和15，h為5、6、7。
這裡我們再來複習put的流程：當我們想一個HashMap中添加一對key-value時，系統首先會計算key的hash值，然後根據hash值确認在table中存儲的位置。若該位置沒有元素，則直接插入。否則疊代該處元素連結清單并依此比較其key的hash值。如果兩個hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆寫原來節點的value。如果兩個hash值相等但key值不等 ，則将該節點插入該連結清單的鍊頭。具體的實作過程見addEntry方法，如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//擷取bucketIndex處的Entry
Entry<K, V> e = table[bucketIndex];
//将新建立的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
//若HashMap中元素的個數超過極限了，則容量擴大兩倍
if (size++ >= threshold)
resize(2 * table.length);
}
這個方法中有兩點需要注意：
一是鍊的産生。
這是一個非常優雅的設計。系統總是将新的Entry對象添加到bucketIndex處。如果bucketIndex處已經有了對象，那麼新添加的Entry對象将指向原有的Entry對象，形成一條Entry鍊，但是若bucketIndex處沒有Entry對象，也就是e==null,那麼新添加的Entry對象指向null，也就不會産生Entry鍊了。
二、擴容問題。
随着HashMap中元素的數量越來越多，發生碰撞的機率就越來越大，所産生的連結清單長度就會越來越長，這樣勢必會影響HashMap的速度，為了保證HashMap的效率，系統必須要在某個臨界點進行擴容處理。該臨界點在當HashMap中元素的數量等于table數組長度*加載因子。但是擴容是一個非常耗時的過程，因為它需要重新計算這些資料在新table數組中的位置并進行複制處理。是以如果我們已經預知HashMap中元素的個數，那麼預設元素的個數能夠有效的提高HashMap的性能。
根據上面 put 方法的源代碼可以看出，當程式試圖将一個 key-value 對放入 HashMap 中時，程式首先根據該 key 的 hashCode() 傳回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 傳回值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較傳回 true，新添加 Entry 的 value 将覆寫集合中原有 Entry 的 value，但 key 不會覆寫。如果這兩個 Entry 的 key 通過 equals 比較傳回 false，新添加的 Entry 将與集合中原有 Entry 形成 Entry 鍊，而且新添加的 Entry 位于 Entry 鍊的頭部。
（2）讀取
相對于HashMap的存而言，取就顯得比較簡單了。通過key的hash值找到在table數組中的索引處的Entry，然後傳回該key對應的value即可。
public V get(Object key) {
// 若為null，調用getForNullKey方法傳回相對應的value
if (key == null)
return 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相同，則傳回相對應的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
有了上面存儲時的hash算法作為基礎，了解起來這段代碼就很容易了。從上面的源代碼中可以看出：從HashMap中get元素時，首先計算key的hashCode，找到數組中對應位置的某一進制素，然後通過key的equals方法在對應位置的連結清單中找到需要的元素。
當 HashMap 的每個 bucket 裡存儲的 Entry 隻是單個 Entry ——也就是沒有通過指針産生 Entry 鍊時，此時的 HashMap 具有最好的性能：當程式通過 key 取出對應 value 時，系統隻要先計算出該 key 的 hashCode() 傳回值，在根據該 hashCode 傳回值找出該 key 在 table 數組中的索引，然後取出該索引處的 Entry，最後傳回該 key 對應的 value 即可。
歸納起來簡單地說，HashMap 在底層将 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數組來儲存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的連結清單中的存儲位置；當需要取出一個Entry時，也會根據hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的連結清單中取出該Entry。
6.HashCode的重要性
前面講到了，HashMap中對Key的HashCode要做一次rehash，防止一些糟糕的Hash算法生成的糟糕的HashCode，那麼為什麼要防止糟糕的HashCode？
糟糕的HashCode意味着的是Hash沖突，即多個不同的Key可能得到的是同一個HashCode，糟糕的Hash算法意味着的就是Hash沖突的機率增大，這意味着HashMap的性能将下降，表現在兩方面：
(1)、有10個Key，可能6個Key的HashCode都相同，另外四個Key所在的Entry均勻分布在table的位置上，而某一個位置上卻連接配接了6個Entry。這就失去了HashMap的意義，HashMap這種資料結構性高性能的前提是，Entry均勻地分布在table位置上，但現在确是1 1 1 1 6的分布。是以，我們要求HashCode有很強的随機性，這樣就盡可能地可以保證了Entry分布的随機性，提升了HashMap的效率。
(2)、HashMap在一個某個table位置上周遊連結清單的時候的代碼
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
看到，由于采用了"&&"運算符，是以先比較HashCode，HashCode都不相同就直接pass了，不會再進行equals比較了。HashCode因為是int值，比較速度非常快，而equals方法往往會對比一系列的内容，速度會慢一些。Hash沖突的機率大，意味着equals比較的次數勢必增多，必然降低了HashMap的效率了。