『數(shù)據(jù)結(jié)構(gòu)與算法』散列表（哈希表）

GitHub源碼分享

微信搜索：碼農(nóng)StayUp
主頁地址：https://gozhuyinglong.github.io
源碼分享：https://github.com/gozhuyinglong/blog-demos

1. 什么是散列表

散列表（Hash Table）也叫哈希表，是根據(jù)給定關(guān)鍵字（Key）來計(jì)算出該關(guān)鍵字在表中存儲(chǔ)地址的數(shù)據(jù)結(jié)構(gòu)植锉。也就是說部逮，散列表建立了關(guān)鍵字與存儲(chǔ)地址之間的一種直接映射關(guān)系，將關(guān)鍵字映射到表中記錄的地址花盐，這加快了查找速度。

使用函數(shù)表達(dá)式來表示，應(yīng)為：hash(key)=v逗嫡，其中key為關(guān)鍵字育瓜，hash()為散列函數(shù)葫隙，v為散列地址。

1.1 相關(guān)術(shù)語

關(guān)鍵字（Key）：關(guān)鍵字是散列表的查找對象躏仇，也是散列函數(shù)的參數(shù)恋脚。其可以是記錄本身腺办，也可以是記錄的唯一索引，這取決于散列表的設(shè)計(jì)糟描。
散列函數(shù)（Hash Function）：將關(guān)鍵字映射為散列表中適當(dāng)存儲(chǔ)地址的函數(shù)稱為散列函數(shù)怀喉，也叫做哈希函數(shù)。
散列地址（Hash Address）：將關(guān)鍵字通過散列函數(shù)計(jì)算出的地址稱為散列地址船响，也叫做散列值躬拢、哈希值。
散列表（Hash Table）：這種使用散列技術(shù)來存儲(chǔ)數(shù)據(jù)記錄的表稱為散列表见间。
散列沖突（Hash Collision）：當(dāng)不同的關(guān)鍵字具有相同的散列地址聊闯，這種現(xiàn)象稱為沖突，也叫做哈希沖突米诉。而這些關(guān)鍵字對該散列函數(shù)來說是同義詞菱蔬。
表長：散列表的大小，即能夠存儲(chǔ)散列地址的數(shù)量史侣。用m表示拴泌。

1.2 舉個(gè)例子

一個(gè)比較通俗的例子，就是我們手機(jī)中的通訊錄惊橱。通訊錄用于存儲(chǔ)聯(lián)系人的姓名及電話號碼信息弛针，它是一個(gè)按照姓名首字母進(jìn)行順序排列的表。比如我們找“嬴政”就可以通過字母“Y”進(jìn)行快速定位李皇，并找到“嬴政”削茁。

散列表：通訊錄

在該例子中，姓名“嬴政”便是關(guān)鍵字掉房。
取姓名的首字母的算法便是散列函數(shù)茧跋。即：hash(嬴政) = Y。
通過
當(dāng)我們定位到“Y”地址后卓囚，不僅有“贏政”瘾杭，還有“贏異人”，也就是說哪亿，通過關(guān)鍵字“贏異人”也能找到“Y”的地址粥烁，這種現(xiàn)象便是沖突。即：hash(嬴政) = hash(嬴異人) = Y蝇棉。
而“贏政”與“贏異人”對該散列函數(shù)來說是同義詞讨阻。
這個(gè)用于存儲(chǔ)聯(lián)系人的通訊錄便是散列表。

1.3 小結(jié)

本章節(jié)介紹了散列表的概念及相關(guān)術(shù)語篡殷，并以一個(gè)通訊錄的例子來加深對散列表的了解钝吮。但還有一些問題等待我們解決，那就是“散列沖突”。我們一方面可以通過精心設(shè)計(jì)散列函數(shù)來盡量減少?zèng)_突的次數(shù)奇瘦，另一方面仍需要提供解決沖突的方法棘催。后面章節(jié)會(huì)詳細(xì)介紹散列函數(shù)的設(shè)計(jì)和解決沖突的方法。

2. 散列函數(shù)的設(shè)計(jì)

散列函數(shù)的設(shè)計(jì)原則應(yīng)該遵循計(jì)算簡單耳标、散列地址分布均勻醇坝。下面我們介紹幾種常用的散列函數(shù)的構(gòu)造方法。

2.1 直接定址法

取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址次坡。即hash(key) = key 或 hash(key) = a * key + b纲仍，其中a、b 為常數(shù)贸毕。這種散列函數(shù)也叫做自身函數(shù)。

如下圖中夜赵，我們要獲取某個(gè)崗位級別的信息明棍，就可以使用級別減去1來作為地址，即：hash(key) = key - 1

直接定址法

直接定址法的優(yōu)點(diǎn)是簡單寇僧、均勻也不會(huì)產(chǎn)生沖突摊腋。但由于這是一種拿空間換時(shí)間的方式，所以適合查找表較小且連續(xù)的情況嘁傀。比如年齡兴蒸、崗位級別等。

2.2 數(shù)字分析法

通過分析一組數(shù)據(jù)细办，這些數(shù)據(jù)中可能出現(xiàn)的關(guān)鍵字都是事先知道的橙凳，則可以取關(guān)鍵字的若干數(shù)位組成散列地址。取出的這部分?jǐn)?shù)據(jù)要在其數(shù)位上出現(xiàn)的頻率小笑撞，這樣出現(xiàn)沖突的幾率就會(huì)很小岛啸。

比如手機(jī)號碼，其前3位為網(wǎng)絡(luò)識別號茴肥，中間4位為地區(qū)編碼坚踩，而后4位才是真正的用戶號碼。那么在某個(gè)公司中瓤狐，其員工的手機(jī)號碼前7位出現(xiàn)沖突的概率會(huì)很大瞬铸，而后4位出現(xiàn)沖突的概率會(huì)很小，則可以取后四位做為散列地址础锐。

數(shù)字分析法

2.3 平方取中法

取關(guān)鍵字平方后的中間幾位作為散列地址嗓节。該方法是一個(gè)產(chǎn)生偽隨機(jī)數(shù)的方法，由馮·諾伊曼在1946年提出皆警。

平方取中法

2.4 折疊法

將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）赦政，然后取這幾部分的疊加和（舍去進(jìn)位）作為散列地址。這種方法比較適用于關(guān)鍵字位數(shù)很多的情況。

比如關(guān)鍵字為 1234567890恢着，散列表的表長為3位：
（1）將關(guān)鍵字分為4組： 123|456|789|0
（2）將它們疊加求和：123 + 456 + 789 + 0 = 1368
（3）舍去進(jìn)位桐愉，得：368 ，即為最終散列地址

2.5 除留余數(shù)法

假定散列表的表長為m掰派，取一個(gè)不大于m但最接近或等于m的質(zhì)數(shù)p从诲，通過關(guān)鍵字對p取模運(yùn)算來轉(zhuǎn)換為散列地址。散列函數(shù)為：hash(key) = key % p靡羡，其中p $\leq$ m系洛。

不僅可以對關(guān)鍵字直接取模，也可以在折疊法略步、平方取中法等運(yùn)算后取模描扯。對p的選擇很重要，若選擇不好很容易產(chǎn)生沖突趟薄。

除留余數(shù)法

3. 散列沖突的處理方法

解決沖突的方法有幾種绽诚，這里我們將討論其中最簡單的兩種：開放定址法和鏈地址法（拉鏈法）。

3.1 開放定址法

將產(chǎn)生沖突的散列地址做為自變量杭煎，通過某種沖突解決函數(shù)得到一個(gè)新的空閑散列地址恩够。即當(dāng)產(chǎn)生沖突后，尋找下一個(gè)空閑的散列地址羡铲。根據(jù)尋找的方式不同又分為幾種方法蜂桶，下面來介紹。

3.1.1 線性探測法

當(dāng)產(chǎn)生沖突時(shí)也切，順序探測表中下一地址扑媚，直探測到一個(gè)空閑（自由）的地址，將記錄插入雷恃。若一直探測到表尾地址m-1,則下一探測地址為表首地址0钦购。當(dāng)表滿的時(shí)候，則探測失敗褂萧。

比如下圖散列表的散列函數(shù)使用除留余數(shù)法（m=10, p=10）押桃。那么我們順序插入12、13导犹、24時(shí)順利插入到對應(yīng)地址中唱凯，再插入34、44時(shí)會(huì)產(chǎn)生沖突谎痢，使用線性探測法磕昼，繼續(xù)探測下一地址，將插入到空閑地址上节猿。

線性探測法

線性探測法會(huì)造成大量元素在相鄰的散列地址上“聚集”起來票从，使得我們要不斷處理沖突漫雕，這大大降低查找和存入效率。

3.1.2 平方探測法

平方探測法是消除線性探測法中的聚集問題的一種沖突解決方法峰鄙。設(shè)發(fā)生沖突的地址為d浸间，那么使用平方探測法得到的新的地址序列為d $\pm$ 1^2、d $\pm$ $2^2$ 吟榴、d $\pm$ $3^2$ ...d $\pm$ $key^2$ （key $\leq$ m/2）魁蒜。

還是剛才那個(gè)例子，當(dāng)插入34時(shí)吩翻，在下標(biāo)為4的位置產(chǎn)生沖突兜看，我們先計(jì)算一下在該位置探測的序列： 4 + $1^2$ = 5、4 - $1^2$ = 3狭瞎、4 + $2^2$ = 8细移、4 - $2^2$ = 0，即：5熊锭、2弧轧、8、0球涛，所以34應(yīng)該被放到5的位置。而44應(yīng)該放到8的位置校镐。

平方探測法

平方探測法的缺點(diǎn)是不能探測到散列表上所有的地址亿扁，但至少能探測到一半地址。

3.1.3 偽隨機(jī)探測法

偽隨機(jī)探測法是當(dāng)發(fā)生地址沖突時(shí)鸟廓，地址增量為偽隨機(jī)數(shù)序列从祝。

偽隨機(jī)數(shù)是說，如果我們設(shè)置隨機(jī)種子相同引谜，則不斷調(diào)用隨機(jī)函數(shù)可以生成不會(huì)重復(fù)的數(shù)列牍陌，我們在查找時(shí)，用同樣的隨機(jī)種子员咽，它每次得到的數(shù)列是相同的毒涧，相同的地址當(dāng)然可以得到相同的散列地址。

3.1.4 雙散列

雙散列顧名思義是使用了兩個(gè)散列函數(shù)贝室，當(dāng)執(zhí)行第一個(gè)散列函數(shù)得到的地址發(fā)生沖突時(shí)契讲，則執(zhí)行第二個(gè)散列函數(shù)來計(jì)算該關(guān)鍵字的地址增量。

一種常見的算法是：(hash1(key) + i * hash2(key)) mod m滑频，其中i為沖突次數(shù)捡偏，hash1()為第一個(gè)散列函數(shù)，hash2()為第二個(gè)散列函數(shù)峡迷，m為散列表大小银伟。當(dāng)發(fā)生沖突后，我們通過重復(fù)增加步長i來尋址。

還是以上面的例子為例彤避。第一個(gè)散列函數(shù)為hash1(key) = key mod 10傅物，第二個(gè)散列函數(shù)設(shè)為hash2(key) = key mod 3。

通過上面公式忠藤，可以計(jì)算出關(guān)鍵字34的散列地址： (34 mod 10 + 1 * (34 mod 3)) mod 10 = (4 + 1 * 1) mod 10 = 5挟伙。而關(guān)鍵字44的散列地址為：(44 mod 10 + 2 * (44 mod 3)) mod 10 = (4 + 2 * 2) mod 10 = 8

雙散列

3.2 鏈地址法

鏈地址法又稱拉鏈法，是利用鏈表來解決沖突的一種方法模孩，即把具有相同散列地址的關(guān)鍵字記錄存入到同一個(gè)單鏈表中尖阔，該鏈表稱為同義詞鏈表。每一個(gè)散列地址都有一個(gè)對應(yīng)的鏈表榨咐。

還是上面的例子介却，使用鏈地址法的存儲(chǔ)模型如下圖所示。

鏈地址法

4. 代碼實(shí)現(xiàn)

我們使用鏈地址法來實(shí)現(xiàn)上例中散列表块茁，其散列函數(shù)使用除留余數(shù)法齿坷。

4.1 節(jié)點(diǎn)類

因?yàn)殒湵聿皇潜酒攸c(diǎn)，所以這里設(shè)計(jì)一個(gè)簡單的節(jié)點(diǎn)類数焊。關(guān)于鏈表的相關(guān)知識請參閱：《鏈表（單鏈表永淌、雙鏈表、環(huán)形鏈表）》

class Node {
    private final int key; // 關(guān)鍵字
    private Node next; // 下一節(jié)點(diǎn)

    public Node(int key) {
        this.key = key;
    }

    public int getKey() {
        return key;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

4.2 散列表類

散列表類使用數(shù)組存儲(chǔ)表數(shù)據(jù)佩耳，其指向鏈表的頭節(jié)點(diǎn)遂蛀，其散列函數(shù)使用除留余數(shù)法。

本類主要實(shí)現(xiàn)了散列表的添加關(guān)鍵字干厚、刪除關(guān)鍵字和匹配關(guān)鍵字李滴。

class HashTable {

    private final int size; // 散列表大小
    private final Node[] table; // 散列表

    private HashTable(int size) {
        this.size = size;
        this.table = new Node[size];
    }

    /**
         * 散列函數(shù) - 除留余數(shù)法
         *
         * @param key
         * @return
         */
    private int hash(int key) {
        return key % size;
    }

    /**
         * 添加關(guān)鍵字
         *
         * @param key
         */
    public void add(int key) {
        int hashAddress = hash(key);
        if (table[hashAddress] == null) {
            table[hashAddress] = new Node(key);
            return;
        }
        add(table[hashAddress], key);
    }

    /**
         * 添加關(guān)鍵字 - 遞歸
         *
         * @param node
         * @param key
         */
    private void add(Node node, int key) {
        if (node.getNext() == null) {
            node.setNext(new Node(key));
            return;
        }
        add(node.getNext(), key);
    }

    /**
         * 匹配關(guān)鍵字
         *
         * @param key
         * @return
         */
    public boolean contains(int key) {
        int hashAddress = hash(key);
        Node headNode = table[hashAddress];
        if (headNode == null) {
            return false;
        }

        return contains(headNode, key);
    }

    /**
         * 匹配關(guān)鍵字 - 遞歸
         *
         * @param node
         * @param key
         * @return
         */
    private boolean contains(Node node, int key) {
        if (node == null) {
            return false;
        }
        if (node.getKey() == key) {
            return true;
        }
        return contains(node.getNext(), key);
    }

    /**
         * 移除關(guān)鍵字
         *
         * @param key
         */
    public void remove(int key) {
        int hashAddress = hash(key);
        Node headNode = table[hashAddress];
        if (headNode == null) {
            return;
        }
        if (headNode.getKey() == key) {
            table[hashAddress] = headNode.getNext();
            return;
        }
        remove(headNode, key);
    }

    /**
         * 移除關(guān)鍵字 - 遞歸
         *
         * @param node
         * @param key
         */
    private void remove(Node node, int key) {
        if (node.getNext() == null) {
            return;
        }
        if (node.getNext().getKey() == key) {
            node.setNext(node.getNext().getNext());
            return;
        }
        remove(node.getNext(), key);
    }

}

5. 完整代碼

完整代碼請?jiān)L問我的Github，若對你有幫助蛮瞄，歡迎給個(gè)Star所坯，謝謝！

https://github.com/gozhuyinglong/blog-demos/blob/main/java-data-structures/src/main/java/io/github/gozhuyinglong/datastructures/hashtable/HashTableDemo.java

『數(shù)據(jù)結(jié)構(gòu)與算法』散列表（哈希表）

『數(shù)據(jù)結(jié)構(gòu)與算法』散列表（哈希表）

GitHub源碼分享

1. 什么是散列表

1.1 相關(guān)術(shù)語

1.2 舉個(gè)例子

1.3 小結(jié)

2. 散列函數(shù)的設(shè)計(jì)

2.1 直接定址法

2.2 數(shù)字分析法

2.3 平方取中法

2.4 折疊法

2.5 除留余數(shù)法

3. 散列沖突的處理方法

3.1 開放定址法

3.1.1 線性探測法

3.1.2 平方探測法

3.1.3 偽隨機(jī)探測法

3.1.4 雙散列

3.2 鏈地址法

4. 代碼實(shí)現(xiàn)

4.1 節(jié)點(diǎn)類

4.2 散列表類

5. 完整代碼

推薦閱讀

推薦閱讀更多精彩內(nèi)容