細談散清單系列一共有三篇文章
1、散清單的概述
2、散列函數的作用與構造
3、散清單查找的代碼實作
文章目錄
-
- 細談散清單系列一共有三篇文章
- 1、散清單的查找算法實作
-
-
- 1. 定義一個散清單的結構以及一些相關常數
- 2. 對散清單進行初始化
- 3. 定義散列函數，可根據不同情況更改算法
- 4. 對散清單進行插入操作
- 5. 通過散清單查找關鍵字
-
- 2、散清單查找性能分析
-
-
- 1. 散列函數是否均勻
- 2. 處理沖突的方法
- 3. 散清單的裝填因子
-
- 3、總結回顧
終于來到本系列的最終章了，在前面說了那麼多散清單查找的理論，本章會将散清單的查找進行代碼實作。
1、散清單的查找算法實作
1. 定義一個散清單的結構以及一些相關常數
HashTable：散清單結構
elem：動态數組
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 // 定義散清單長為數組的長度
#define NULLKEY -32768
typedef struct{
int *elem; // 資料元素存儲基址，動态配置設定數組
int count; // 目前資料元素個數
}HashTable;
int m = 0; // 散清單表長，全局變量
2. 對散清單進行初始化
/* 初始化散清單 */
Status InitHashTable(HashTable *H){
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m * sizeof(int));
for(i = 0; i < m; i++)
H->elem[i] = NULLKEY;
return OK;
}
3. 定義散列函數，可根據不同情況更改算法
為了計算插入時的位址，定義散列函數
/* 散列函數 */
int Hash(int key){
return key % m; //除留餘數法
}
4. 對散清單進行插入操作
初始化完成之後，就可以對散清單進行插入操作。
- 計算出散列位址
- 若不為空，則說明有沖突
- 此時我們應用開放定址法的線性探索進行重新尋址（此處也可以改為其他解決沖突的方法）
/* 插入關鍵字進行散清單 */
void InsertHash(HashTable *H, int key){
int addr = Hash(key) // 求散列位址
while(H->elem[addr] != NULLKEY) // 如果不為空，則沖突
addr = (addr + 1) % m; // 開放定址法的線性探索
H->elem[addr] = key; // 知道有空位後插入關鍵字
}
5. 通過散清單查找關鍵字
散清單存在後，我們在需要時就可以通過散清單查找關鍵字
/* 散清單查找關鍵字 */
Status SearchHash(HashTable H, int key, int *addr){
*addr = Hash(key); // 求散列位址
while(H.elem[*addr] != key){// 如果不為空，則沖突
*addr = (*addr + 1) % m; // 開方定址法的線性探索
if(H.elem[*addr] == NULLKEY || *addr = Hash(key)){
/* 如果循環回到原點 */
return UNSUCCESS; // 則說明關鍵字不存在
}
}
return SUCCESS;
}
從上面的代碼我們可以看出，查找的代碼與插入的代碼非常相似，隻需要做一個不存在關鍵字的判斷而已。
2、散清單查找性能分析
如果沒有沖突時，此時的散清單查找效率是最高的，時間複雜度隻為O(1)；
但可惜，這也隻是如果，在實際應用中，沖突是不可避免的。
那散列查找的平均查找長度取決于哪些因素呢？
1. 散列函數是否均勻
散列函數的好壞直接決定了出現沖突的頻繁程度。但由于不同的散列函數對同一組随機的關鍵字，産生沖突的可能性是相同的，是以我們可以不考慮它對平均查找長度的影響。
2. 處理沖突的方法
相同的關鍵字、散列函數，但處理沖突的方法不同，會使得平均查找長度不同。
如線性探測處理沖突可能會産生堆積，顯然就沒有二次探測法好。
而鍊位址法處理沖突不會産生任何堆積，是以具有更佳的平均查找性能。
3. 散清單的裝填因子
所謂的裝載因子α = 填入表中的記錄個數 / 散清單長度。
α 标志着散清單的裝滿的程度：
- 當填入表中的記錄越多，α 就越大，産生沖突的可能性就越大；
這就相當于，你去公共廁所裡面上廁所，裡面有12個坑位，但是已經有11個坑位有人了。
那麼此時的裝填因子α = 11 / 12 = 0.9167，此時你敲門碰到裡面有人的幾率就十分的大。
是以，散清單的平均查找長度取決于裝填因子，而不是取決于查找集合中的記錄個數。
綜上所述，隻要我們選擇一個合适的裝填因子以便将平均查找長度限定在一個範圍内，此時我們散列查找的時間複雜度就真的是O(1)了。
通常我們都是将散清單的空間設定得比查找集合大，此時雖然是浪費了一定的空間，但換來的卻是查找效率的大大提升，是一筆劃算的買賣。
3、總結回顧
散清單是一種非常高效的查找資料結構，但它也有它的缺點。
散清單的優缺點：
- 優點：它回避了關鍵字之間反複比較的繁瑣，直接一步到位查找結果。
- 缺點：記錄之間沒有任何關聯
是以，散清單對于那些查找性能要求高，記錄之間關系無要求的資料有非常好的适用性。
細談散清單系列到這裡就結束啦，希望我們後會有期！！！
以上就是本篇文章的所有内容了，如果覺得有幫助到你的話，
麻煩動動小手，點贊收藏轉發！！！
你的每一次點贊都是我更新的最大動力~
我們下期再見！
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)