細談散串列系列一共有三篇文章
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、總結回顧
散串列是一種非常高效的查找資料結構，但它也有它的缺點，
散串列的優缺點：
- 優點：它回避了關鍵字之間反復比較的繁瑣，直接一步到位查找結果，
- 缺點：記錄之間沒有任何關聯
所以，散串列對于那些查找性能要求高，記錄之間關系無要求的資料有非常好的適用性，
細談散串列系列到這里就結束啦，希望我們后會有期！！！
以上就是本篇文章的所有內容了，如果覺得有幫助到你的話，
麻煩動動小手，點贊收藏轉發！！！
你的每一次點贊都是我更新的最大動力~
我們下期再見！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/252181.html
標籤：其他
下一篇：c語言遞回系列總結