目錄

1 哈希表的含義與結構特點

1.1 哈希（Hash）即無序

1.2 從數組看哈希表的結構特點

2?哈希函數（Hash Function）與哈希沖突（Hash Collision）

2.1 哈希函數及其設計方法

2.2 哈希沖突及其解決方案（含Java模擬）

2.2.1 開放地址法

2.2.2 鏈表法

1 哈希表的含義與結構特點

1.1 哈希（Hash）即無序

哈希表（Hash Table）更直觀的中文名字是散列表，存儲在里面的元素不是單個的，而是成對的，這就是我們熟悉的鍵值對（key-value pair）。Java中的Map（映射）、Python中的Dictionary（字典）以及NoSQL（非關系型數據庫）采用的都是這種存儲方式。

“數據結構學習筆記”系列的前6篇文章介紹的線性表型結構（鏈表、棧、隊列）、數組型結構（數組、基于數組的字符串）和樹型結構（二叉樹）都有一個共同的特點，就是它們都要保證存儲在里面的數據是有序的。哈希表則與之相反，存儲在其中的元素是散列的，也就是無序的。?

出于好奇，筆者去有道詞典查了查hash這個單詞的意思，《牛津詞典》的解釋是：“a hot dish of cooked meat and potatoes that are cut into small pieces and mixed together?”，就是用切成碎末的肉和馬鈴薯做成的熱菜，由此就引申除了“零碎、雜亂”的意思，到數據結構領域就成了“散列”。

順便提一下，還有一個很有趣的短語：make a hash of sth，意思是把某事弄糟。

1.2 從數組看哈希表的結構特點

我們認為，數組型結構和樹型結構都可以看成線性表型結構的推廣，而哈希表的散列型結構又是數組型結構的推廣。為什么這么說呢？

在線性表中，無論是鏈表、棧還是隊列，每一個元素在空間位置上與其前后的元素構成關聯；在數組中，每一個數據在空間位置上都與首元素構成關聯，索引的本質含義是元素與首元素的偏移量；在樹結構中，每一個數據在空間位置上都與其上下層的元素構成關聯。

因此，與線性表相比，數組將所有元素相互依賴的遞歸結構轉換為所有元素具有相同基準的結構，從而實現了基于索引的快速隨機訪問；樹將元素間一對一的關系推廣為一對多的關系，從而實現了數據結構的層級。

上述有序結構中，能夠衍生出無序結構的只有數組。在本系列講解數組的文章中，提到了我們會基于日常經驗將“索引”理解為“編號”的問題，這實際上就是散列的思想。因為元素一旦具有唯一的“編號”，我們定位元素時的思考角度就不再是誰在誰的前面或后面，而是那個元素的“編號”是多少。

“編號”與元素之間是映射(Map)的關系，這很像字典(Dictionary)的檢字法。正因為數組中索引與元素具有映射關系，所以把索引看成編號是沒有毛病的。編號可以有序，也可以無序。比如下面的Python代碼定義的列表（相當于數組）和字典（相當于哈希表）：

# 定義一個 列表（數組） list_1 = ['趙', '錢', '孫', '李']# 定義一個 字典（哈希表）， 鍵-值 為上述列表的 索引-元素 dict_1 = {0:'趙', 1:'錢', 2:'孫', 3:'李'}# 再定義一個 字典（哈希表），鍵-值 為 拼音首字母-漢字 dict_2 = {'z':'趙', 'q':'錢', 's':'孫', 'l':'李'}

2?哈希函數（Hash Function）與哈希沖突（Hash Collision）

2.1 哈希函數及其設計方法

數組是順序存儲，可以順序訪問（即遍歷），也可以隨機訪問；而哈希表則實現了隨機存取，無論是存儲還是取出數據都與數據所在的位置無關。實現隨機存取依靠的是哈希函數（Hash Function）。

哈希函數的格式是：addr?= f(key)。其中addr指的是數據的內存地址，key指的是數據值有關的關鍵字。存儲時，通過關鍵字分配得一個內存空間；取出時，通過關鍵字定位到內存地址，從而得到數據值。

鍵值對為“索引-元素”的哈希表，哈希函數應寫為：addr = f(index) = index。其實就是一個一元一次函數：y=x，這是一個線性函數，因此數組既能順序訪問，也能隨機訪問。但是數組的隨機訪問是有局限性的，訪問元素只有基于順序的索引這一個選擇，不能根據數值本身包含的信息查找數據。我們來看下面的兩個存儲姓氏的哈希表，代碼語言為Python：

family_name_1 = {1:'趙', 2:'錢', 3:'孫', 4:'李'}family_name_2 = {'z':'趙', 'q':'錢', 's':'孫', 'l':'李'}

第一個哈希表（字典）的關鍵字是姓氏在《百家姓》中的次序，第二個哈希表（字典）的關鍵字是姓氏的拼音首字母，如何定義關鍵字是根據需求來的。

哈希函數的設計是為了讓“鍵值對”中的“鍵”具有唯一性，且符合數據檢索的需求。設計哈希函數的常用方法包括：直接定制法、數字分析法、平方取中法、折疊法和除留取余法。

直接定制：比如上面姓氏哈希表的“鍵”就是根據某種規則直接定制的；

數字分析：比如存儲個人信息的表中，取身份證后六位，因為這幾位不容易重復；

平方取中：即取平方再取中間的若干位，適用于重復位較多的數據，平方為了擴大差異；

分段疊加：比如將18位身份證號三等分，再將三個六位數值疊加（舍去進位）；

除留取余：將關鍵字與長度短于關鍵字的數字做除法，取余數為地址；

隨機數法：比如快遞柜的六位取件碼就是隨機生成的。

從以上方法中不難看不出，對原數據值哈希函數可以起到化長為短的作用。比如18位的身份證號經過數字分析法后就變成了6位。?如果作為關鍵字的數據占空間很大，直接拿來用是很浪費內存的。

2.2 哈希沖突及其解決方案（含Java模擬）

任何一種哈希函數都很難保證得到的哈希值不會重復，一旦重復就會產生沖突。解決哈希沖突有兩種常用的方法：開放地址法（openning addressing）和鏈表法（chaining）。

2.2.1 開放地址法

開放地址法的思路很好理解，如果出現哈希沖突，就采用某種探測方法從發生沖突的位置依照某種探測順序依次查找，直到找到哈希表中的空位，將關鍵字存入。探測方法包括線性探測（Linear Probing）、二次探測（Quadratic Probing）、雙重哈希（Double hashing）等。最常用的是線性探測。

比如我們要存入一組關鍵字{10,12,13,14,22,21}，哈希函數采用除留取余法，除數為7，余數分別是{3,5,6,0,1,0}，我們發現有兩個0，存在沖突，先進入的14占據了0位置，21不能再用這個位置。線性探測的過程如下圖所示：

可以用Java簡單地模擬一下這個過程，數組模擬哈希表，數組的索引模擬地址。

package com.notes.data_structure7;public class LinearProbing {public static void main(String[] args) {// 模擬 哈希表 的數組int[] table = new int[7];// 要存入的關鍵字int[] keys = {10,12,13,14,22,21};for(int i=0;i<keys.length;i++) {int key = keys[i];int addr = get_addr(key);if(table[addr]==0) { // 無哈希沖突table[addr] = key;}else { // 有哈希沖突int current_addr = addr;a:for(int j=0;j<table.length;j++) {current_addr++;if(current_addr==table.length) {current_addr=0;}if(table[current_addr]==0) { // 無哈希沖突table[current_addr] = key;break a;}}}}// 打印表for(int i=0;i<table.length;i++) {System.out.println("addr:"+i+",key:"+table[i]);}}// 哈希函數static public int get_addr(int key) {return key%7;}}

打印結果下，key值為0表示位置為空。

addr:0,key:14 addr:1,key:22 addr:2,key:21 addr:3,key:10 addr:4,key:0 addr:5,key:12 addr:6,key:13

線性探測也是有局限性的，加入的值越多，發生哈希沖突的可能性就越大，哈希表的性能就越差。比如上面的關鍵字21因為哈希沖突被調到了地址2的位置，如果再加一個關鍵字為23，經哈希函數計算地址為2，又與21發生哈希沖突，不得不再次線性探測。

為了彌補上述缺陷，又出現了二次探測、雙重哈希等改進方法。二次探測在線性探測基礎上增加了地址跳轉的跨度，那上面的代碼來說，線性探測的次序是current_addr+1,+2,+3，二次探測次序是current_addr+1,+4,+9。雙重哈希是預設多個的哈希函數，一個發生沖突，就換一個，直到不沖突為止。

2.2.2 鏈表法

鏈表法的思路是，哈希表的每一個槽(slot)都是一個鏈表，哈希函數計算的是槽位，將值根據相應的槽位存入對應的鏈表，這種解決方法比開放地址法要更加方便。

同樣用Java模擬這個方法，該方法相比于開放地址法，省去判斷是否有哈希沖突和遍歷尋址的操作。鏈表的代碼復用“數據結構學習筆記”系列的第一篇文章“鏈表”的代碼，鏈接貼在下面：

https://blog.csdn.net/weixin_45370422/article/details/116573863

Java代碼模擬的結果呈現方式是：由于鏈表里定義的打印結點的方法是不換行打印，因此不同的槽位用空行隔開，空位直接打印“空槽”兩個字。

package com.notes.data_structure7;public class Chaining {public static void main(String[] args) {// 模擬 哈希表 的數組，表槽（slot）的數據類型是鏈表MyLink[] table = new MyLink[7];// 要存入的關鍵字int[] keys = {10,12,13,14,22,21};for(int i=0;i<keys.length;i++) {int key = keys[i];int addr = get_addr(key);if(table[addr]==null) {table[addr] = new MyLink();}table[addr].addNode(key);}// 打印表（鏈表的結點值打印不換行，不同的表槽用空行隔開，空位直接打印空槽）for(int i=0;i<table.length;i++) {MyLink link = table[i];try {link.printLink();System.out.println();} catch(NullPointerException e) {System.out.println("空槽");System.out.println();}}}// 哈希函數static public int get_addr(int key) {return key%7;}}

打印結果：

14 2122空槽10空槽1213

總結

以上是生活随笔為你收集整理的数据结构学习笔记（七）：哈希表（Hash Table）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。