摘要：那既然頻繁出，肯定不能是手撕紅黑樹(shù)我覺(jué)得面試官也多半撕不出來(lái)，不撕紅黑樹(shù)，那這道題還有點(diǎn)救，慢慢往下看。簡(jiǎn)單說(shuō)來(lái)說(shuō)，哈希表由兩個(gè)要素構(gòu)成桶數(shù)組和散列函數(shù)。所謂的哈希沖突，就是不同的經(jīng)過(guò)哈希函數(shù)計(jì)算，落到了同一個(gè)下標(biāo)。快手面試官真的嗎我不信。

手寫(xiě)HashMap？這么狠，面試都卷到這種程度了？

第一次見(jiàn)到這個(gè)面試題，是在某個(gè)不方便透露姓名的Offer收割機(jī)大佬的文章：

這……我當(dāng)時(shí)就麻了，我們都知道HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹(shù)，這是要手撕紅黑樹(shù)的節(jié)奏嗎？

后來(lái)，整理了一些面經(jīng)，發(fā)現(xiàn)這道題在快手的面試出現(xiàn)還比較頻繁，分析這道題應(yīng)該在快手的面試題庫(kù)。那既然頻繁出，肯定不能是手撕紅黑樹(shù)——我覺(jué)得面試官也多半撕不出來(lái)，不撕紅黑樹(shù)，那這道題還有點(diǎn)救，慢慢往下看。

認(rèn)識(shí)哈希表

HashMap其實(shí)是數(shù)據(jù)結(jié)構(gòu)中的哈希表在Java里的實(shí)現(xiàn)。

哈希表本質(zhì)

哈希表也叫散列表，我們先來(lái)看看哈希表的定義：

哈希表是根據(jù)關(guān)鍵碼的值而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。

就像有人到公司找老三，前臺(tái)小姐姐拿手一指，那個(gè)墻角的工位就是。

簡(jiǎn)單說(shuō)來(lái)說(shuō)，哈希表由兩個(gè)要素構(gòu)成：桶數(shù)組和散列函數(shù)。

• 桶數(shù)組：一排工位
• 散列函數(shù)：老三在墻角

桶數(shù)組

我們可能知道，有一類(lèi)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)線性表，而線性表又分兩種，數(shù)組和鏈表。

哈希表數(shù)據(jù)結(jié)構(gòu)里，存儲(chǔ)元素的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，數(shù)組里的每個(gè)單元都可以想象成一個(gè)桶（Bucket）。

假如給若干個(gè)程序員分配工位：蛋蛋、熊大、牛兒、張三，我們觀察到，這些名字比較有特色，最后一個(gè)字都是數(shù)字，我們可以把它提取出來(lái)作為關(guān)鍵碼，這些一來(lái)，就可以把他們分配到對(duì)應(yīng)編號(hào)的工位，沒(méi)分配到的工位就讓它先空著。

那么在這種情況下，我們查找/插入/刪除的時(shí)間復(fù)雜度是多少呢？很明顯，都是O(1)。

但咱們也不是葫蘆娃，名字不能都叫一二三四五六七之類(lèi)的，假如來(lái)的新人叫南宮大牛，那我們?cè)趺捶峙渌兀?/p>

這就引入了我們的第二個(gè)關(guān)鍵要素——散列函數(shù)。

散列函數(shù)

我們需要在元素和桶數(shù)組對(duì)應(yīng)位置建立一種映射映射關(guān)系，這種映射關(guān)系就是散列函數(shù)，也可以叫哈希函數(shù)。

例如，我們一堆無(wú)規(guī)律的名字諸葛鋼鐵、劉華強(qiáng)、王司徒、張全蛋……我們就需要通過(guò)散列函數(shù)，算出這些名字應(yīng)該分配到哪一號(hào)工位。

散列函數(shù)構(gòu)造

散列函數(shù)也叫哈希函數(shù)，假如我們數(shù)據(jù)元素的key是整數(shù)或者可以轉(zhuǎn)換為一個(gè)整數(shù)，可以通過(guò)這些常見(jiàn)方法來(lái)獲取映射地址。

• 直接定址法

  直接根據(jù)key來(lái)映射到對(duì)應(yīng)的數(shù)組位置，例如1232放到下標(biāo)1232的位置。

• 數(shù)字分析法

  取key的某些數(shù)字（例如十位和百位）作為映射的位置

• 平方取中法

  取key平方的中間幾位作為映射的位置

• 折疊法

  將key分割成位數(shù)相同的幾段，然后把它們的疊加和作為映射的位置

• 除留余數(shù)法

  H（key)=key%p（p<=N）,關(guān)鍵字除以一個(gè)不大于哈希表長(zhǎng)度的正整數(shù)p，所得余數(shù)為哈希地址，這是應(yīng)用最廣泛的散列函數(shù)構(gòu)造方法。

在Java里，Object類(lèi)里提供了一個(gè)默認(rèn)的hashCode()方法，它返回的是一個(gè)32位int形整數(shù)，其實(shí)也就是對(duì)象在內(nèi)存里的存儲(chǔ)地址。

但是，這個(gè)整數(shù)肯定是要經(jīng)過(guò)處理的，上面幾種方法里直接定址法可以排除，因?yàn)槲覀儾豢赡芙敲创蟮耐皵?shù)組。

而且我們最后計(jì)算出來(lái)的散列地址，盡可能要在桶數(shù)組長(zhǎng)度范圍之內(nèi)，所以我們選擇除留取余法。

哈希沖突

理想的情況，是每個(gè)數(shù)據(jù)元素經(jīng)過(guò)哈希函數(shù)的計(jì)算，落在它獨(dú)屬的桶數(shù)組的位置。

但是現(xiàn)實(shí)通常不如人意，我們的空間是有限的，設(shè)計(jì)再好的哈希函數(shù)也不能完全避免哈希沖突。所謂的哈希沖突，就是不同的key經(jīng)過(guò)哈希函數(shù)計(jì)算，落到了同一個(gè)下標(biāo)。

既然有了沖突，就得想辦法解決沖突，常見(jiàn)的解決哈希沖突的辦法有：

鏈地址法

也叫拉鏈法，看起來(lái)，像在桶數(shù)組上再拉一個(gè)鏈表出來(lái)，把發(fā)生哈希沖突的元素放到一個(gè)鏈表里，查找的時(shí)候，從前往后遍歷鏈表，找到對(duì)應(yīng)的key就行了。

開(kāi)放地址法

開(kāi)放地址法，簡(jiǎn)單來(lái)說(shuō)就是給沖突的元素再在桶數(shù)組里找到一個(gè)空閑的位置。

找到空閑位置的方法有很多種：

• 線行探查法: 從沖突的位置開(kāi)始，依次判斷下一個(gè)位置是否空閑，直至找到空閑位置
• 平方探查法: 從沖突的位置x開(kāi)始，第一次增加1^2個(gè)位置，第二次增加2^2...，直至找到空閑的位置
• 雙散列函數(shù)探查法

……

再哈希法

構(gòu)造多個(gè)哈希函數(shù)，發(fā)生沖突時(shí)，更換哈希函數(shù)，直至找到空閑位置。

建立公共溢出區(qū)

建立公共溢出區(qū)，把發(fā)生沖突的數(shù)據(jù)元素存儲(chǔ)到公共溢出區(qū)。

很明顯，接下來(lái)我們解決沖突，會(huì)使用鏈地址法。

好了，哈希表的介紹就到這，相信你已經(jīng)對(duì)哈希表的本質(zhì)有了深刻的理解，接下來(lái)，進(jìn)入coding時(shí)間。

HashMap實(shí)現(xiàn)

我們實(shí)現(xiàn)的簡(jiǎn)單的HashMap命名為ThirdHashMap，先確定整體的設(shè)計(jì)：

• 散列函數(shù)：hashCode()+除留余數(shù)法
• 沖突解決：鏈地址法

整體結(jié)構(gòu)如下：

內(nèi)部節(jié)點(diǎn)類(lèi)

我們需要定義一個(gè)節(jié)點(diǎn)來(lái)作為具體數(shù)據(jù)的載體，它不僅要承載鍵值對(duì)，同樣還得作為單鏈表的節(jié)點(diǎn)：

    /**     * 節(jié)點(diǎn)類(lèi)     *     * @param      * @param      */    class Node {        //鍵值對(duì)        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;        }    }

成員變量

主要有四個(gè)成員變量，其中桶數(shù)組作為裝載數(shù)據(jù)元素的結(jié)構(gòu)：

    //默認(rèn)容量    final int DEFAULT_CAPACITY = 16;    //負(fù)載因子    final float LOAD_FACTOR = 0.75f;    //HashMap的大小    private int size;    //桶數(shù)組    Node[] buckets;

構(gòu)造方法

構(gòu)造方法有兩個(gè)，無(wú)參構(gòu)造方法，桶數(shù)組默認(rèn)容量，有參指定桶數(shù)組容量。

    /**     * 無(wú)參構(gòu)造器，設(shè)置桶數(shù)組默認(rèn)容量     */    public ThirdHashMap() {        buckets = new Node[DEFAULT_CAPACITY];        size = 0;    }    /**     * 有參構(gòu)造器，指定桶數(shù)組容量     *     * @param capacity     */    public ThirdHashMap(int capacity) {        buckets = new Node[capacity];        size = 0;    }

散列函數(shù)

散列函數(shù)，就是我們前面說(shuō)的hashCode()和數(shù)組長(zhǎng)度取余。

    /**     * 哈希函數(shù)，獲取地址     *     * @param key     * @return     */    private int getIndex(K key, int length) {        //獲取hash code        int hashCode = key.hashCode();        //和桶數(shù)組長(zhǎng)度取余        int index = hashCode % length;        return Math.abs(index);    }

put方法

我用了一個(gè)putval方法來(lái)完成實(shí)際的邏輯，這是因?yàn)閿U(kuò)容也會(huì)用到這個(gè)方法。

大概的邏輯：

• 獲取元素插入位置
• 當(dāng)前位置為空，直接插入
• 位置不為空，發(fā)生沖突，遍歷鏈表
• 如果元素key和節(jié)點(diǎn)相同，覆蓋，否則新建節(jié)點(diǎn)插入鏈表頭部

    /**     * put方法     *     * @param key     * @param value     * @return     */    public void put(K key, V value) {        //判斷是否需要進(jìn)行擴(kuò)容        if (size >= buckets.length * LOAD_FACTOR) resize();        putVal(key, value, buckets);    }    /**     * 將元素存入指定的node數(shù)組     *     * @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;        }        //插入位置不為空，說(shuō)明發(fā)生沖突，使用鏈地址法,遍歷鏈表        while (node != null) {            //如果key相同，就覆蓋掉            if ((node.key.hashCode() == key.hashCode())                    && (node.key == key || node.key.equals(key))) {                node.value = value;                return;            }            node = node.next;        }        //當(dāng)前key不在鏈表中，插入鏈表頭部        Node newNode = new Node(key, value, table[index]);        table[index] = newNode;        size++;    }

擴(kuò)容方法

擴(kuò)容的大概過(guò)程：

• 創(chuàng)建兩倍容量的新數(shù)組
• 將當(dāng)前桶數(shù)組的元素重新散列到新的數(shù)組
• 新數(shù)組置為map的桶數(shù)組

    /**     * 擴(kuò)容     */    private void resize() {        //創(chuàng)建一個(gè)兩倍容量的桶數(shù)組        Node[] newBuckets = new Node[buckets.length * 2];        //將當(dāng)前元素重新散列到新的桶數(shù)組        rehash(newBuckets);        buckets = newBuckets;    }    /**     * 重新散列當(dāng)前元素     *     * @param newBuckets     */    private void rehash(Node[] newBuckets) {        //map大小重新計(jì)算        size = 0;        //將舊的桶數(shù)組的元素全部刷到新的桶數(shù)組里        for (int i = 0; i < buckets.length; i++) {            //為空，跳過(guò)            if (buckets[i] == null) {                continue;            }            Node node = buckets[i];            while (node != null) {                //將元素放入新數(shù)組                putVal(node.key, node.value, newBuckets);                node = node.next;            }        }    }

get方法

get方法就比較簡(jiǎn)單，通過(guò)散列函數(shù)獲取地址，這里我省去了有沒(méi)有成鏈表的判斷，直接查找鏈表。

    /**     * 獲取元素     *     * @param key     * @return     */    public V get(K key) {        //獲取key對(duì)應(yīng)的地址        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;    }

完整代碼：

測(cè)試

測(cè)試代碼如下：

    @Test    void test0() {        ThirdHashMap map = new ThirdHashMap();        for (int i = 0; i < 100; i++) {            map.put("劉華強(qiáng)" + i, "你這瓜保熟嗎？" + i);        }        System.out.println(map.size());        for (int i = 0; i < 100; i++) {            System.out.println(map.get("劉華強(qiáng)" + i));        }    }    @Test    void test1() {        ThirdHashMap map = new ThirdHashMap();        map.put("劉華強(qiáng)1","哥們，你這瓜保熟嗎？");        map.put("劉華強(qiáng)1","你這瓜熟我肯定要啊！");        System.out.println(map.get("劉華強(qiáng)1"));    }

大家可以自行跑一下看看結(jié)果。

總結(jié)

好了，到這，我們一個(gè)簡(jiǎn)單的HashMap就實(shí)現(xiàn)了，這下，面試快手再也不怕手寫(xiě)HashMap了。

快手面試官：真的嗎？我不信。我就要你手寫(xiě)個(gè)紅黑樹(shù)版的……

當(dāng)然了，我們也發(fā)現(xiàn)，HashMap的O(1)時(shí)間復(fù)雜度操作是在沖突比較少的情況下，簡(jiǎn)單的哈希取余肯定不是最優(yōu)的散列函數(shù)；沖突之后，鏈表拉的太長(zhǎng)，同樣影響性能；我們的擴(kuò)容和put其實(shí)也存在線程安全的問(wèn)題……

但是，現(xiàn)實(shí)里我們不用考慮那么多，因?yàn)槔罾蠣斠呀?jīng)幫我們寫(xiě)好了，我們只管調(diào)用就完了。

下一篇，會(huì)以面試對(duì)線的形式來(lái)走進(jìn)李老爺操刀的HashMap！

點(diǎn)贊、關(guān)注不迷路，咱們下期見(jiàn)！

參考：

[1].《數(shù)據(jù)結(jié)構(gòu)與算法》

[2].構(gòu)造哈希函數(shù)方法

[3].ACM金牌選手講解LeetCode算法《哈希》