當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【数据结构-查找】3.散列表详解

發布時間：2025/3/20 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了【数据结构-查找】3.散列表详解小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

散列表的一些基本概念

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。

計算映射位置的函數叫做 散列函數。

存放記錄的數組叫做 散列表。

散列函數可能會把兩個或兩個以上的不同關鍵字映射到同一個散列表中的位置，這種情況叫做沖突。

一些散列函數計算的key值會使得大量元素出現在相鄰的散列地址上，從而大大降低了查找效率，這種現象叫做 “聚集”（或堆積）

裝填因子，定義為一個表的裝滿程度，公式為
$\frac{n}{散列表長度m}(n=表中的記錄數)$
散列表的平均查找長度依賴于散列表的裝填因子 α，而不直接依賴于 n 或 m。裝填因子有這樣的性質，直觀地看，α越大，表示裝填的記錄約 “滿”，發生沖突的可能性越大，反之發生沖突的可能性越小。

散列函數的構造方法

設計散列函數的幾個原則

函數的定義域必須包含全部關鍵字

計算出來的key應該是等概率、均勻的

盡量簡單

1. 直接定址法
$H (k e y) = a ? k e y + b (a, b \in R)$
特點：簡單不會產生沖突

適用：是和關鍵字的分布基本連續

缺點：若關鍵字分布不連續，會造成較多空位，從而浪費存儲空間

例如：

有表一數據如下，經過 直接定址法 處理后的hash表如表二所示

表一

地址A1A2……A99A100

年齡	1	2	……	99	100
人數	980	800	……	495	107

表二

地址A0A1……A99A100

年齡	1980	1981	……	1999	2000
人數	980	800	……	495	107

2. 除留余數法
$\% p (p≤m)$
特點：p是一個不大于散列表長度m且最接近或等于散列表長度的質數

適用：使得每個關鍵字通過該函數轉換后等概況地映射到散列空間上的任一地址，從而降低沖突

例如：

已知待散列元素為（18，75，60，43，54，90，46），表長m=10，p=7，則有

h(18)=18 % 7=4h(75)=75 % 7=5h(60)=60 % 7=4h(43)=43 % 7=1

h(54)=54 % 7=5

h(90)=90 % 7=6

h(46)=46 % 7=4

3. 數字分析法

特點：關鍵字在某些位上分布不均勻，只有某幾種數碼經常出現，此時應選取數碼分布較為均勻的若干位作為散列地址

適用：能預先估計出全體關鍵字的每一位上各種數字出現的頻度。若更換了關鍵字，則需要重新構造新的散列函數

例如：

K1K2K3K4K5K6K7K8

61317602

61326875

62739628

61343634

62706815

62774638

61381262

61394220

上述8個關鍵字可知，關鍵字從左到右的第1（6）、2（1）、3（3）、6（2）位取值比較集中，不宜作為哈希地址。剩余的第4、5、7、8位取值較均勻，可選取其中的兩位作為哈希地址。設選取最后兩位作為哈希地址，則這8個關鍵字的哈希地址分別為：2，75，28，34，15，38，62，20。

4. 平方取中法

特點：取關鍵字平方后的中間幾位為哈希地址。

適用：關鍵字中的每一位都有某些數字重復出現頻度很高的現象，這種散列地址分布比較均勻

例如：

若設哈希表長為1000則可取關鍵字平方值的中間三位，如圖所示：

關鍵字關鍵字的平方哈希函數值

1234	1522756	227
2143	4592449	924
4132	17073424	734
3214	10329796	297

5. 折疊法

特點：將關鍵字分割成位數相同的幾部分，然后取這幾部分的疊加和作為散列地址

適用：關鍵字的數字位數特別多

例如：

當哈希表長為1000時，關鍵字key=110108331119891，允許的地址空間為三位十進制數，則這兩種疊加情況如下：

移位疊加邊界疊加

	8 9 1	8 9 1	正讀
	1 1 9	9 1 1	逆讀
	3 3 1	3 3 1	正讀
	1 0 8	8 0 1	逆讀
	+ 1 1 0	+ 1 1 0	正讀
和	(1) 5 5 9	(3) 0 4 4

處理沖突的方法

1. 開放定址法

$H_i = (H(key) + d_i) \%m(i=1,2,……,k,m=散列表表長,d_i為增量序列)$

1. 線性探測再散列

$d_i=1, 2, 3,…,m-1$

這種方法的特點是：沖突發生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。

2. 平方探測法

$ d_i=1^2，-12，2^2，-22，…，k^2，-k2 ( k<=m/2 )$

這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。

3. 再散列法

這種方法是同時構造多個不同的哈希函數：

$ H_i=(H(key)+i*Hash_2(key))%m (i=1,2,…,k)$

這種方法的特點是：當哈希地址 $H_1=H_0（key）$ 發生沖突時，再計算 $H_2=H_1（key）$ ，…，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

4. 偽隨機序列法

$d_i=偽隨機序列$ 時

2.拉鏈法

首先對關鍵字集合用散列函數計算散列地址，具有相同地址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中。

代碼：

struct ListNode{int val;ListNode *next;ListNode(int x): val(x), next(NULL){} };// 哈希取余 int hash_func(int key, int table_len) {return key % table_len; } // 使用頭插法插入 void insert(ListNode *hash_table[], ListNode *node, int table_len) {int hash_key = hash_func(node->val, table_len);node->next = hash_table[hash_key];hash_table[hash_key] = node; } // 查找 bool search(ListNode *hash_table[], int value, int table_len) {int hash_key = hash_func(node->val, table_len);ListNode *head = hash_table[hash_key];while(head) {if(head->val == value) return true;head = head->next;}return false; }

散列查找及性能分析

查找成功公式
$ALS成功=∑(pi)m(pi=每個取余關鍵字查找到目標值的查找次數，m取余值的大小)ALS_{成功}= \frac{\sum(p_i)}{m}(p_i=每個取余關鍵字查找到目標值的查找次數，m取余值的大小)$
查找失敗公式
$ALS失敗=∑(qi)m=(qi=每個取余關鍵字查找散列表為空或者回到源rest的查找次數，m=取余值的大小)ALS_{失敗}= \frac{\sum(q_i)}{m}=(q_i=每個取余關鍵字查找散列表為空或者回到源rest的查找次數，m=取余值的大小)$
示例：

關鍵字序列：{ 7, 8, 30, 11, 18, 9, 14}

散列函數： $(key?3)%7(key*3)\%7$

key序列：{0, 3, 6, 5, 5, 6, 0}

0123456789

查找成功的情況：

關鍵字78301118914

比較次數

過程：（在hash表中查找，在關鍵字處記錄比較了多少次）

如果需要找到7，需要找pos=0，直接找到，比較1次；

如果需要找到8，需要找pos=3，直接找到，比較1次；

如果需要找到30，需要找pos=6，直接找到，比較1次；

如果需要找到11，需要找pos=5，直接找到，比較1次；

如果需要找到18，需要找pos=5，但發現hash[5] != 18，向后找；發現hash[6] != 18，繼續向后找；在pos=7時找到，比較3次；

如果需要找到9，需要找pos=6，但發現hash[6] != 9，向后找；發現hash[7] != 9，繼續向后找；在pos=8找到，比較3次；

如果需要找到14，需要找pos=0，但發現hash[0] != 14，向后找；在pos=1找到，比較2次；

套用公式，得

$ALS成功=1+1+1+1+3+3+27=127ALS_{成功}= \frac{1+1+1+1+3+3+2}{7}=\frac{12}{7}$

查找失敗的情況：

取余0123456

比較次數

過程：（依次假設key%7=rest，在hash表中查找，找到hash表中為空或者 回到原來的rest 處，比較次數記錄到rest列表中）

如果需要找到21(63%7=0)，需要找pos=0，但發現hash[0] != 21，向后找；發現hash[1] != 21，繼續向后找；在pos=2為空，比較3次；

如果需要找到5(15%7=1)，需要找pos=1，但發現hash[1] != 5，向后找；在pos=2為空，比較2次；

如果需要找到3(9%7=2)，需要找pos=2為空，比較1次；

如果需要找到17(51%7=3)，需要找pos=3，但發現hash[3] != 17，向后找；在pos=4為空，比較2次；

如果需要找到6(18%7=4)，需要找pos=4為空，比較1次；

如果需要找到25(75%7=5)，需要找pos=5，但發現hash[5] != 25，向后找；發現hash[6] != 25，繼續向后找；發現hash[7] != 25，繼續向后找；發現hash[8] != 25，繼續向后找；在pos=9為空，比較5次；

如果需要找到16(48%7=6)，需要找pos=6，但發現hash[,6] != 16，向后找；發現hash[7] != 16，繼續向后找；發現hash[8] != 16，繼續向后找；在pos=9為空，比較4次；

套用公式，得

$ALS失敗=3+2+1+2+1+5+47=187ALS_{失敗}= \frac{3+2+1+2+1+5+4}{7}=\frac{18}{7}$

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【数据结构-查找】3.散列表详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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

上一篇：【数据结构-查找】2.字符串（逐步演绎过
下一篇：【数据结构-查找】4.五千字干活长文带你