手寫HashMap，快手面試官直呼內行！
手寫HashMap？這麼狠，面試都卷到這種程度了？
第一次見到這個面試題，是在某個不方便透露姓名的Offer收割機大佬的文章：
這……我當時就麻了，我們都知道HashMap的數據結構是數組+鏈表+紅黑樹，這是要手撕紅黑樹的節奏嗎？
後來，整理了一些面經，發現這道題在快手的面試出現還比較頻繁，分析這道題應該在快手的面試題庫。那既然頻繁出，肯定不能是手撕紅黑樹——我覺得面試官也多半撕不出來，不撕紅黑樹，那這道題還有點救，慢慢往下看。
認識哈希表
HashMap其實是數據結構中的哈希表在Java里的實現。
哈希表本質
哈希表也叫散列表，我們先來看看哈希表的定義：
哈希表是根據關鍵碼的值而直接進行訪問的數據結構。
就像有人到公司找老三，前台小姐姐拿手一指，那個牆角的工位就是。
簡單說來說，哈希表由兩個要素構成：桶數組和散列函數。
- 桶數組：一排工位
- 散列函數：老三在牆角
桶數組
我們可能知道，有一類基礎的數據結構線性表，而線性表又分兩種，數組和鏈表。
哈希表數據結構里，存儲元素的數據結構就是數組，數組裡的每個單元都可以想像成一個桶（Bucket）。
假如給若干個程式設計師分配工位：蛋蛋、熊大、牛兒、張三，我們觀察到，這些名字比較有特色，最後一個字都是數字，我們可以把它提取出來作為關鍵碼，這些一來，就可以把他們分配到對應編號的工位，沒分配到的工位就讓它先空著。
那麼在這種情況下，我們查找/插入/刪除的時間複雜度是多少呢？很明顯，都是O(1)。
但咱們也不是葫蘆娃，名字不能都叫一二三四五六七之類的，假如來的新人叫南宮大牛，那我們怎麼分配他呢？
這就引入了我們的第二個關鍵要素——散列函數。
散列函數
我們需要在元素和桶數組對應位置建立一種映射映射關係，這種映射關係就是散列函數，也可以叫哈希函數。
例如，我們一堆無規律的名字諸葛鋼鐵、劉華強、王司徒、張全蛋……我們就需要通過散列函數，算出這些名字應該分配到哪一號工位。
散列函數構造
散列函數也叫哈希函數，假如我們數據元素的key是整數或者可以轉換為一個整數，可以通過這些常見方法來獲取映射地址。
-
直接定址法
直接根據
key來映射到對應的數組位置，例如1232放到下標1232的位置。 -
數字分析法
取
key的某些數字（例如十位和百位）作為映射的位置 -
平方取中法
取
key平方的中間幾位作為映射的位置 -
摺疊法
將
key分割成位數相同的幾段，然後把它們的疊加和作為映射的位置 -
除留餘數法
H（key)=key%p（p<=N）,關鍵字除以一個不大於哈希表長度的正整數p，所得餘數為哈希地址，這是應用最廣泛的散列函數構造方法。
在Java里，Object類里提供了一個默認的hashCode()方法，它返回的是一個32位int形整數，其實也就是對象在記憶體里的存儲地址。
但是，這個整數肯定是要經過處理的，上面幾種方法里直接定址法可以排除，因為我們不可能建那麼大的桶數組。
而且我們最後計算出來的散列地址，儘可能要在桶數組長度範圍之內，所以我們選擇除留取余法。
哈希衝突
理想的情況，是每個數據元素經過哈希函數的計算，落在它獨屬的桶數組的位置。
但是現實通常不如人意，我們的空間是有限的，設計再好的哈希函數也不能完全避免哈希衝突。所謂的哈希衝突，就是不同的key經過哈希函數計算，落到了同一個下標。
既然有了衝突，就得想辦法解決衝突，常見的解決哈希衝突的辦法有：
鏈地址法
也叫拉鏈法，看起來，像在桶數組上再拉一個鏈表出來，把發生哈希衝突的元素放到一個鏈表裡，查找的時候，從前往後遍歷鏈表，找到對應的key就行了。
開放地址法
開放地址法，簡單來說就是給衝突的元素再在桶數組裡找到一個空閑的位置。
找到空閑位置的方法有很多種：
- 線行探查法: 從衝突的位置開始，依次判斷下一個位置是否空閑，直至找到空閑位置
- 平方探查法: 從衝突的位置x開始，第一次增加
1^2個位置，第二次增加2^2…，直至找到空閑的位置 - 雙散列函數探查法
……
再哈希法
構造多個哈希函數，發生衝突時，更換哈希函數，直至找到空閑位置。
建立公共溢出區
建立公共溢出區，把發生衝突的數據元素存儲到公共溢出區。
很明顯，接下來我們解決衝突，會使用鏈地址法。
好了，哈希表的介紹就到這，相信你已經對哈希表的本質有了深刻的理解，接下來，進入coding時間。
HashMap實現
我們實現的簡單的HashMap命名為ThirdHashMap，先確定整體的設計：
- 散列函數：hashCode()+除留餘數法
- 衝突解決：鏈地址法
整體結構如下：
內部節點類
我們需要定義一個節點來作為具體數據的載體，它不僅要承載鍵值對，同樣還得作為單鏈表的節點：
/**
* 節點類
*
* @param <K>
* @param <V>
*/
class Node<K, V> {
//鍵值對
private K key;
private V value;
//鏈表，後繼
private Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
public Node(K key, V value, Node<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
成員變數
主要有四個成員變數，其中桶數組作為裝載數據元素的結構：
//默認容量
final int DEFAULT_CAPACITY = 16;
//負載因子
final float LOAD_FACTOR = 0.75f;
//HashMap的大小
private int size;
//桶數組
Node<K, V>[] buckets;
構造方法
構造方法有兩個，無參構造方法，桶數組默認容量，有參指定桶數組容量。
/**
* 無參構造器，設置桶數組默認容量
*/
public ThirdHashMap() {
buckets = new Node[DEFAULT_CAPACITY];
size = 0;
}
/**
* 有參構造器，指定桶數組容量
*
* @param capacity
*/
public ThirdHashMap(int capacity) {
buckets = new Node[capacity];
size = 0;
}
散列函數
散列函數，就是我們前面說的hashCode()和數組長度取余。
/**
* 哈希函數，獲取地址
*
* @param key
* @return
*/
private int getIndex(K key, int length) {
//獲取hash code
int hashCode = key.hashCode();
//和桶數組長度取余
int index = hashCode % length;
return Math.abs(index);
}
put方法
我用了一個putval方法來完成實際的邏輯，這是因為擴容也會用到這個方法。
大概的邏輯：
- 獲取元素插入位置
- 當前位置為空，直接插入
- 位置不為空，發生衝突，遍歷鏈表
- 如果元素key和節點相同，覆蓋，否則新建節點插入鏈表頭部
/**
* put方法
*
* @param key
* @param value
* @return
*/
public void put(K key, V value) {
//判斷是否需要進行擴容
if (size >= buckets.length * LOAD_FACTOR) resize();
putVal(key, value, buckets);
}
/**
* 將元素存入指定的node數組
*
* @param key
* @param value
* @param table
*/
private void putVal(K key, V value, Node<K, V>[] table) {
//獲取位置
int index = getIndex(key, table.length);
Node node = table[index];
//插入的位置為空
if (node == null) {
table[index] = new Node<>(key, value);
size++;
return;
}
//插入位置不為空，說明發生衝突，使用鏈地址法,遍歷鏈表
while (node != null) {
//如果key相同，就覆蓋掉
if ((node.key.hashCode() == key.hashCode())
&& (node.key == key || node.key.equals(key))) {
node.value = value;
return;
}
node = node.next;
}
//當前key不在鏈表中，插入鏈表頭部
Node newNode = new Node(key, value, table[index]);
table[index] = newNode;
size++;
}
擴容方法
擴容的大概過程：
- 創建兩倍容量的新數組
- 將當前桶數組的元素重新散列到新的數組
- 新數組置為map的桶數組
/**
* 擴容
*/
private void resize() {
//創建一個兩倍容量的桶數組
Node<K, V>[] newBuckets = new Node[buckets.length * 2];
//將當前元素重新散列到新的桶數組
rehash(newBuckets);
buckets = newBuckets;
}
/**
* 重新散列當前元素
*
* @param newBuckets
*/
private void rehash(Node<K, V>[] newBuckets) {
//map大小重新計算
size = 0;
//將舊的桶數組的元素全部刷到新的桶數組裡
for (int i = 0; i < buckets.length; i++) {
//為空，跳過
if (buckets[i] == null) {
continue;
}
Node<K, V> node = buckets[i];
while (node != null) {
//將元素放入新數組
putVal(node.key, node.value, newBuckets);
node = node.next;
}
}
}
get方法
get方法就比較簡單，通過散列函數獲取地址，這裡我省去了有沒有成鏈表的判斷，直接查找鏈表。
/**
* 獲取元素
*
* @param key
* @return
*/
public V get(K key) {
//獲取key對應的地址
int index = getIndex(key, buckets.length);
if (buckets[index] == null) return null;
Node<K, V> node = buckets[index];
//查找鏈表
while (node != null) {
if ((node.key.hashCode() == key.hashCode())
&& (node.key == key || node.key.equals(key))) {
return node.value;
}
node = node.next;
}
return null;
}
完整程式碼：
測試
測試程式碼如下：
@Test
void test0() {
ThirdHashMap map = new ThirdHashMap();
for (int i = 0; i < 100; i++) {
map.put("劉華強" + i, "你這瓜保熟嗎？" + i);
}
System.out.println(map.size());
for (int i = 0; i < 100; i++) {
System.out.println(map.get("劉華強" + i));
}
}
@Test
void test1() {
ThirdHashMap map = new ThirdHashMap();
map.put("劉華強1","哥們，你這瓜保熟嗎？");
map.put("劉華強1","你這瓜熟我肯定要啊！");
System.out.println(map.get("劉華強1"));
}
大家可以自行跑一下看看結果。
總結
好了，到這，我們一個簡單的HashMap就實現了，這下，面試快手再也不怕手寫HashMap了。
快手面試官：真的嗎？我不信。我就要你手寫個紅黑樹版的……
當然了，我們也發現，HashMap的O(1)時間複雜度操作是在衝突比較少的情況下，簡單的哈希取余肯定不是最優的散列函數；衝突之後，鏈表拉的太長，同樣影響性能；我們的擴容和put其實也存在執行緒安全的問題……
但是，現實里我們不用考慮那麼多，因為李老爺已經幫我們寫好了，我們只管調用就完了。
下一篇，會以面試對線的形式來走進李老爺操刀的HashMap！
點贊、關注不迷路，咱們下期見！
參考：
[1].《數據結構與演算法》
[2].構造哈希函數方法
