摘要：那既然頻繁出，肯定不能是手撕紅黑樹我覺得面試官也多半撕不出來，不撕紅黑樹，那這道題還有點救，慢慢往下看。簡單說來說，哈希表由兩個要素構成桶數組和散列函數。所謂的哈希沖突，就是不同的經過哈希函數計算，落到了同一個下標。快手面試官真的嗎我不信。

手寫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      * @param      */    class Node {        //鍵值對        private K key;        private V value;        //鏈表，后繼        private Node next;        public Node(K key, V value) {            this.key = key;            this.value = value;        }        public Node(K key, V value, Node 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[] 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[] 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[] newBuckets = new Node[buckets.length * 2];        //將當前元素重新散列到新的桶數組        rehash(newBuckets);        buckets = newBuckets;    }    /**     * 重新散列當前元素     *     * @param newBuckets     */    private void rehash(Node[] newBuckets) {        //map大小重新計算        size = 0;        //將舊的桶數組的元素全部刷到新的桶數組里        for (int i = 0; i < buckets.length; i++) {            //為空，跳過            if (buckets[i] == null) {                continue;            }            Node 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 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].構造哈希函數方法

[3].ACM金牌選手講解LeetCode算法《哈?！?/a>