前面的博客中，我給大家分析過數組和鏈表兩種線性表數據結構。數組存儲區間連續，查找方便，但是插入和刪除效率低下；鏈表存儲區間離散，插入刪除方便，但是查找困難。大家肯定會問，有沒有一種結構，既能做到查找便捷，又能做到插入刪除方便呢？答案就是我們今天要跟大家說的主角：哈希表。
我們先來看一下哈希表的百度定義
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Keyvalue)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數f(key)為哈希(Hash)函數。
下圖是一個經典的哈希表實現方式圖，來自百度百科。
再看一張圖
這張圖更明顯的告訴我們哈希表采用的是一種“拉鏈法”實現的，關於拉鏈法，大家可以自行百度腦補。左邊是數組，右邊是鏈表，感覺十分像用數組把鏈表串起來，在一個長度為16的數組中，每個元素存儲的是一個鏈表的頭結點。接下來我們一起來分析一下HashMap的源碼實現。
HashMap的繼承關系
通過HashMap的繼承關系，我們可以得知HashMap繼承自抽象類AbstractMap，該Map又實現了Map接口，我們下來看一下Map接口包含哪些方法。
可以看出包含了我們常用的HashMap中的一些方法，接著我們來看HashMap的父類AbstractMap。
public abstract class AbstractMap implements Map {
// 用懶加載的方式定義了Set集合類型的鍵，表明HashMap鍵是不能重復的
Set keySet;
// 用懶加載的方式定義了Collection集合類型的值，表明HashMap值是可以重復的
Collection valuesCollection;
……
}
這裡重點要看明白一開始定義的鍵和值，鍵是不能重復的，值可以重復。
然後定義了兩個靜態的實體類
// 維護鍵和值的 Entry
static class AbstractMap.SimpleEntry
// 維護不可變的鍵和值的 Entry
static class AbstractMap.SimpleImmutableEntry
繼續下面實現了接口Map中的方法：clear、put、get、equals、size、hashCode等等。
HashMap源碼解析
現在我們開始分析HashMap的源碼，走起┏ (゜ω゜)=?
元素定義
private static final int MINIMUM_CAPACITY = 4;// HashMap最小容量為4
private static final int MAXIMUM_CAPACITY = 1 << 30;// HashMap最大容量1073741824，往右移除2，往左移是乘2
// 實體數組
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];// 一個空的鍵值對實體數組最小容量是2
static final float DEFAULT_LOAD_FACTOR = .75F;// 默認的容量擴展因子是0.75
transient HashMapEntry[] table;// 鍵值對的數組
transient HashMapEntry entryForNullKey;// 沒有鍵的鍵值對
transient int size;// 非空元素長度
transient int modCount;// 計數器
private transient int threshold;// 容量因子的極限
// Views - lazily initialized 父類繼承下來的
private transient Set keySet;
private transient Set> entrySet;
private transient Collection values;
構造方法
/**
* Constructs a new empty {@code HashMap} instance.
*/
@SuppressWarnings("unchecked")
public HashMap() {
table = (HashMapEntry[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
/**
* 指定初始容量的構造方法
*/
public HashMap(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity: " + capacity);
}
if (capacity == 0) {
@SuppressWarnings("unchecked")
HashMapEntry[] tab = (HashMapEntry[]) EMPTY_TABLE;
table = tab;
threshold = -1; // Forces first put() to replace EMPTY_TABLE
return;
}
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {
capacity = Collections.roundUpToPowerOfTwo(capacity);
}
makeTable(capacity);
}
/**
* 指定初始容量和擴展因子的構造方法
*/
public HashMap(int capacity, float loadFactor) {
this(capacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
}
/*
* Note that this implementation ignores loadFactor; it always uses
* a load factor of 3/4. This simplifies the code and generally
* improves performance.
*/
}
/**
* 構造一個映射關系與指定 Map 相同的新 HashMap。所創建的 HashMap 具有默認加載因子 (0.75) 和足 以容納指定 Map 中映射關系的初始容量。
*/
public HashMap(Map map) {
this(capacityForInitSize(map.size()));
constructorPutAll(map);
}
put方法
/**
* Maps the specified key to the specified value.
* @param key the key.
* @param value the value.
* @return the value of any previous mapping with the specified key or
* {@code null} if there was no such mapping.
*/
@Override
public V put(K key, V value) {
if (key == null) {// HashMap的key是可以為空的，如果為空，放一個NullKey
return putValueForNullKey(value);
}
// 定義一個int型的hash，將key的hashCode計算後再次得到Hash值賦予它，即二次哈希
int hash = Collections.secondaryHash(key);
HashMapEntry[] tab = table;// 存儲鍵值對的數組
// index是下標，tab數組長度-1即數組下標最大值，接著做&運算得到下標最大的長度，避免溢出
int index = hash & (tab.length - 1);
// 遍歷索引下面的整個鏈表，tab[index]整個鏈表的頭結點，如果index索引處的Entry不為 null，通過循環不斷遍歷e元素的下一個元素
for (HashMapEntry e = tab[index]; e != null; e = e.next) {
// 如果指定key與需要放入的key兩個鍵相同，進行覆蓋，新的覆蓋老的
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// 如果index索引處的Entry為null，表明此處還沒有 Entry
modCount++;// 計數器++
if (size++ > threshold) {// 尺寸++大於容量因子的極限，則擴容
tab = doubleCapacity();// 容量擴大兩倍，HashMap容量最小是4，然後兩倍兩倍的擴容
index = hash & (tab.length - 1);// 重新計算一遍
}
addNewEntry(key, value, hash, index);// 把新的鍵值對添加進來
return null;
}
Hash相同，Key不一定相同，如果Key相同，Hash值一定相同。
總結put方法的基本過程如下：
（1）對key的hashcode進行二次hash計算，獲取應該保存到數組中的index。
（2）判斷index所指向的數組元素是否為空，如果為空則直接插入。
（3）如果不為空，則依次查找e中next所指定的元素，判讀key是否相等，如果相等，則替換舊的值，並返回值。
（4）跳出循環，判斷容量是否超出，如果超出進行擴容
（5）執行addNewEntry()添加方法；
get方法
/**
* Returns the value of the mapping with the specified key.
* @param key the key.
* @return the value of the mapping with the specified key, or {@code null}
* if no mapping for the specified key is found.
*/
public V get(Object key) {
if (key == null) {// 如果key為空，把entryForNullKey賦值給e
HashMapEntry e = entryForNullKey;
return e == null ? null : e.value;
}
// 根據key的hashCode值計算它的hash碼
int hash = Collections.secondaryHash(key);
HashMapEntry[] tab = table;
// 直接取出tab數組中指定索引處的值
for (HashMapEntry e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
//拿到每一個鍵值對中的key
K eKey = e.key;
// 去比較，如果兩個key相等 或者 內存地址相等並且兩個哈希值相等，則找到並返回值
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
remove方法
/**
* Removes the mapping with the specified key from this map.
* @param key the key of the mapping to remove.
* @return the value of the removed mapping or {@code null} if no mapping
* for the specified key was found.
*/
@Override public V remove(Object key) {
if (key == null) {// 如果key等於空，則移除空鍵值對
return removeNullKey();
}
int hash = Collections.secondaryHash(key);
HashMapEntry[] tab = table;
int index = hash & (tab.length - 1);
// 遍歷全部結點
for (HashMapEntry e = tab[index], prev = null;
e != null; prev = e, e = e.next) {
// 找到結點，如果Hash相等，並且key相等，找到了我們要移除的結點
if (e.hash == hash && key.equals(e.key)) {
if (prev == null) {// 遍歷到最後結束時找到要刪除的結點
tab[index] = e.next;// 頭結點從第二個結點開始算起
} else {// 在中間任意地方找到了我們要刪除的元素
prev.next = e.next;// 這裡使用了鏈表刪除元素的套路
}
modCount++;
size--;
postRemove(e);
return e.value;
}
}
return null;
}
