C語言 哈希查找詳解(哈希表的創(chuàng)建、處理沖突、查找等)
前言
哈希查找(Hash Search)是一種基于哈希表實(shí)現(xiàn)的數(shù)據(jù)查找算法,也可以被稱為散列查找。
在哈希查找中,首先根據(jù)給定的鍵值通過哈希函數(shù)計算出對應(yīng)的哈希值,然后利用該哈希值在哈希表中定位到具有相同哈希值的一個桶(Bucket),再在桶中進(jìn)行線性查找和比較,以確定目標(biāo)記錄是否存在。若存在,則返回該記錄在哈希表中存放的位置;若不存在,則說明該記錄未被存儲在哈希表中。
哈希表(Hash Table):
哈希表也叫散列表,是一種根據(jù)關(guān)鍵碼值(Key-value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。通常情況下,它通過把關(guān)鍵碼值映射到一個表中的位置來訪問記錄,以加快查找的速度。換句話說,哈希表就是一種以鍵值對作為存儲基本單位的數(shù)據(jù)結(jié)構(gòu)。
哈希函數(shù)(Hash Function):
哈希函數(shù)是一種將任意長度的輸入(也叫“鍵”或“關(guān)鍵字”)映射到固定長度的輸出(也叫“哈希值”或“散列值”的)的函數(shù)。通常情況下,哈希函數(shù)需要具有以下特點(diǎn):
可以接受不同長度的輸入,但輸出長度固定。對于相同的輸入,必須輸出相同的結(jié)果。對于不同的輸入,輸出的哈希值應(yīng)盡可能均勻地分布在整個哈希表中。計算速度快、容易實(shí)現(xiàn)且不會出現(xiàn)哈希沖突(即不同的輸入映射到了同一個哈希值上)等要求
哈希函數(shù)的構(gòu)造方法
哈希函數(shù)的構(gòu)造方法有很多種,常見的包括以下幾種:
直接定址法(Direct Addressing):將關(guān)鍵字直接作為地址使用,適用于關(guān)鍵字較小且連續(xù)的情況。例如對于關(guān)鍵字 k,哈希函數(shù)可以設(shè)置為 f(k) = a * k + b,其中 a、b 是常數(shù)。
數(shù)字分析法(Digital Analysis):根據(jù)關(guān)鍵字的分布規(guī)律來設(shè)計哈希函數(shù),適用于數(shù)據(jù)中存在一定規(guī)律的情況。例如對于電話號碼(11 位數(shù)字),可以將前三位和后兩位分別乘以某個常數(shù)相加得到哈希值。
平方取中法(The Mid-square Method):將關(guān)鍵字平方后取中間幾位作為哈希值,適用于關(guān)鍵字位數(shù)較多的情況,可增加哈希函數(shù)的隨機(jī)性和分布性。
除留余數(shù)法(Modular division method):將關(guān)鍵字除以一個常數(shù) m,取余數(shù)作為哈希值,即 f(k) = k % m。除留余數(shù)法是哈希函數(shù)設(shè)計中最常用的方法之一,容易實(shí)現(xiàn)且效果不錯。
折疊法(Folding method):將關(guān)鍵字分割成若干段,取每段的和作為哈希地址。適用于關(guān)鍵字長度較長的情況。
隨機(jī)數(shù)法(Random Number):使用隨機(jī)函數(shù)生成隨機(jī)數(shù)來產(chǎn)生哈希值,這種方法雖然能夠盡可能避免哈希沖突,但也會帶來效率上的問題。
哈希函數(shù)的構(gòu)造方法應(yīng)該根據(jù)實(shí)際情況進(jìn)行選擇和設(shè)計,要盡可能避免哈希沖突、保證哈希表的均勻性和穩(wěn)定性,并滿足計算速度快、易于實(shí)現(xiàn)等要求。同時需要注意的是,不同的哈希函數(shù)適用于不同類型的數(shù)據(jù),需要根據(jù)具體數(shù)據(jù)進(jìn)行選擇。
處理哈希沖突的方法
哈希函數(shù)在將關(guān)鍵字映射到哈希表的數(shù)組下標(biāo)時,可能會遇到多個不同的關(guān)鍵字被映射到同一個單元格的情況,即發(fā)生哈希沖突。處理哈希沖突的方法有以下幾種:
- 鏈地址法(Chaining)也叫拉鏈法:將哈希表中每個單元格視為鏈表的頭節(jié)點(diǎn),所有哈希值相同的關(guān)鍵字放在該單元格對應(yīng)鏈表的末尾。這種方法不會浪費(fèi)空間,但需要消耗時間查找鏈表。
開放定址法(Open addressing):當(dāng)哈希值發(fā)生沖突時,依次檢查哈希表中下一個位置是否空閑,直到找到一個合適的位置存儲該關(guān)鍵字。開放定址法中有幾種常見的變種策略,如線性探測、二次探測和雙重散列等。
再哈希法(Rehashing):使用另一種哈希函數(shù)再次計算沖突的關(guān)鍵字的哈希值,并重新安排其在哈希表中的存儲位置。這樣可以分?jǐn)偣_突,并減少鏈表長度。但是,此方式的代價較大,因?yàn)樾枰獙?shù)據(jù)結(jié)構(gòu)進(jìn)行重新哈希操作。
根據(jù)實(shí)際應(yīng)用場景選擇適當(dāng)?shù)墓_突解決方案,可以提高哈希表的查詢效率和空間利用率。
哈希查找算法實(shí)現(xiàn)
哈希查找流程主要包括建立哈希表、插入數(shù)據(jù)、查找數(shù)據(jù)和刪除數(shù)據(jù)這幾個步驟。其中,哈希函數(shù)的設(shè)計和沖突處理方法的選擇是實(shí)現(xiàn)哈希查找算法時的關(guān)鍵。
具體實(shí)現(xiàn)流程如下:
- 建立哈希表:選定合適的哈希函數(shù)、定義好哈希表及其相關(guān)屬性,給哈希表分配足夠的空間。
- 插入數(shù)據(jù):將要查找的數(shù)據(jù)通過哈希函數(shù)轉(zhuǎn)化為對應(yīng)的哈希碼,并確定在哈希表中對應(yīng)的位置;進(jìn)而將數(shù)據(jù)儲存在該位置上。如果發(fā)生沖突,則采用相應(yīng)的沖突處理方法來解決沖突,保證數(shù)據(jù)被正確儲存。
- 查找數(shù)據(jù):需要查詢數(shù)據(jù)時,先通過相同的哈希函數(shù)計算出要查找的數(shù)據(jù)的哈希碼,然后根據(jù)哈希碼得到在哈希表中的位置。若該位置上沒有數(shù)據(jù),則說明所查找的數(shù)據(jù)不存在;否則,在該位置上遍歷查找,并返回所找到的數(shù)據(jù)。
- 刪除數(shù)據(jù):刪除數(shù)據(jù)時,需要先通過哈希表查找到所要刪除數(shù)據(jù)的位置,并將其從哈希表中移除。同時,需要使用相應(yīng)的沖突解決方法,重新整理該位置上的其他數(shù)據(jù),以確保這些數(shù)據(jù)的正確性不受影響。
以下介紹常用的兩種哈希表:
開放定址法處理沖突的哈希表
開放定址哈希表是一種基于數(shù)組實(shí)現(xiàn)的哈希表,可以采用線性探測、二次探測、雙重散列等方式處理哈希沖突。其中,線性探測法是最簡單的方法,其思路是依次訪問下一個(i+1)個槽位,直到發(fā)現(xiàn)空閑槽位為止。
下面是使用線性探測法創(chuàng)建哈希表的示例代碼:
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #define NIL 0 typedef struct { int* Table;//儲存哈希節(jié)點(diǎn)的數(shù)組基地址 int size;//哈希表長度 }HashTable; //初始化哈希表 HashTable* InitHashTabel(int size) { HashTable* H = malloc(sizeof(HashTable)); H->size = size; H->Table = (int*)malloc(sizeof(int) * size); //將所以槽位初始化為空閑狀態(tài) while (size > 0) H->Table[--size] = NIL; return H; } //哈希函數(shù) int Hash(int data, int size) { return data % size;//除留余數(shù)法 } //線性探測法解決哈希沖突 int LinearProbe(HashTable* H, int data) { int Pos = Hash(data, H->size);//通過哈希函數(shù)計算得到其哈希地址 //若當(dāng)前位置被占用 while (H->Table[Pos] != NIL) { //若已存在當(dāng)前鍵 if (H->Table[Pos] == data) { return Pos;//返回其位置 } Pos = (Pos + 1) % H->size;//線性探測下一個槽位 } return Pos;//返回空閑位置 } //插入哈希節(jié)點(diǎn) int Insert(HashTable* H, int key) { int Pos = LinearProbe(H, key);//獲取該關(guān)鍵字應(yīng)所在位置 //判斷該關(guān)鍵字是否在哈希表中 if (H->Table[Pos] != key) { H->Table[Pos] = key; return 1;//插入成功 } return 0;//插入失敗 } //查詢哈希節(jié)點(diǎn) int Search(HashTable* H, int key) { //線性探測查找key是否在哈希表中 int Pos = LinearProbe(H, key); if (H->Table[Pos] != NIL) return Pos; return -1;//所查元素不存在 } //刪除哈希節(jié)點(diǎn) int Delete(HashTable* H, int key) { int Pos = Search(H, key);//查找該關(guān)鍵字 if (Pos != -1) { H->Table[Pos] = NIL;//直接將槽位置空 return 1;//刪除成功,返回1 } return 0;//刪除失敗,返回0 } //打印哈希表節(jié)點(diǎn) void print(HashTable* H) { for (int i = 0; i < H->size; i++) { if (H->Table[i] == NIL) printf("NIL "); else printf("%d ", H->Table[i]); } } int main() { HashTable* H = InitHashTabel(10); printf("插入元素10、34、20、13、11、2:\n"); Insert(H, 10); Insert(H, 34); Insert(H, 20); Insert(H, 13); Insert(H, 11); Insert(H, 2); print(H); printf("\n刪除13和20:\n"); Delete(H, 13); Delete(H, 20); print(H); }
運(yùn)行程序初始化哈希表,進(jìn)行插入、刪除操作:
鏈地址法處理沖突的哈希表
使用鏈地址法處理沖突的哈希表通常被稱為“散列表”(hash table)或“哈希映射”(hash map)。和開放地址法相比,鏈地址法能夠更好地處理哈希沖突,并且不需要考慮如何重新計算哈希碼。因此,在實(shí)際應(yīng)用中,鏈地址法的散列表在很多情況下更為常見。
下面為使用無頭結(jié)點(diǎn)鏈表的哈希表:
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> //儲存一個元素的結(jié)構(gòu)體 typedef struct { int key; //可添加其他元素 char* value;//字符串元素 }ElementType; //鏈表節(jié)點(diǎn)結(jié)構(gòu)體 typedef struct node { ElementType data; struct node* next; }Node; //哈希表結(jié)構(gòu)體 typedef struct { Node** Table;//哈希表指針數(shù)組基地址 int Hash_size;//表長 }HashTable; //初始化 HashTable* InitHashTable(int TableSize) { HashTable* H = malloc(sizeof(HashTable)); H->Hash_size = TableSize; H->Table = (Node**)malloc(sizeof(Node*) * H->Hash_size); //初始化數(shù)組內(nèi)每個指針 for (int i = 0; i < H->Hash_size; i++) { H->Table[i] = NULL; } return H; } //哈希函數(shù) int Hash(HashTable* H, int key) { return key % H->Hash_size; } //查找 Node* Search(HashTable* H, int key) { Node* p; int Pos; Pos = Hash(H, key);//計算哈希值 p = H->Table[Pos];//該關(guān)鍵字應(yīng)在鏈表的基地址 //搜索該鏈表 while (p != NULL && p->data.key != key) p = p->next; return p; } //插入 void Insert(HashTable* H, ElementType elem) { Node* p; int Pos; p = Search(H, elem.key);//查找該關(guān)鍵字 if (p == NULL) { //若哈希表中不存在該關(guān)鍵字,頭插法插入新節(jié)點(diǎn)。 Pos = Hash(H, elem.key); p = (Node*)malloc(sizeof(Node)); p->data = elem; p->next = H->Table[Pos]; H->Table[Pos] = p; } } //刪除 void Delete(HashTable* H, int key) { //查找該關(guān)鍵字是否在哈希表中 if (Search(H, key) != NULL) { int Pos = Hash(H, key); Node* p1, * p2; p1 = H->Table[Pos]; //若刪除的節(jié)點(diǎn)為頭結(jié)點(diǎn) if (p1->next == NULL) { H->Table[Pos] = NULL; free(p1); } else { while (p1->next->data.key != key) p1 = p1->next; p2 = p1->next; p1->next = p2->next; free(p2); } } } int main() { HashTable* H = InitHashTable(10); ElementType elem; Node* p; elem.key = 13; elem.value = "^_^"; Insert(H, elem); elem.key = 6; elem.value = "QWQ"; Insert(H, elem); p = Search(H, 13); printf("%d : %s\n", p->data.key, p->data.value); p = Search(H, 6); printf("%d : %s\n", p->data.key, p->data.value); Delete(H, 6); }
運(yùn)行代碼,插入兩個元素,然后刪除一個;
總結(jié)
在計算機(jī)科學(xué)領(lǐng)域中,哈希表是一種高效的數(shù)據(jù)結(jié)構(gòu),具有快速存儲和查找數(shù)據(jù)的特點(diǎn)。它的應(yīng)用非常廣泛,可以用于字典或關(guān)聯(lián)數(shù)組、緩存、數(shù)據(jù)庫索引、去重、計數(shù)器等場景。
雖然哈希表看起來很簡單,但要實(shí)現(xiàn)一個健壯且高效的哈希表并不容易。需要考慮許多因素,如哈希函數(shù)的設(shè)計、處理沖突的方法、負(fù)載因子、自動擴(kuò)容等等。
同時,哈希表也有其局限性,如空間利用率較低、哈希沖突會導(dǎo)致性能下降、不支持順序遍歷等問題。因此,在實(shí)際應(yīng)用中,我們需要根據(jù)具體情況選擇最適合的數(shù)據(jù)結(jié)構(gòu)。
總之,哈希表是一種非常重要的數(shù)據(jù)結(jié)構(gòu),并在大量的計算機(jī)科學(xué)和工程應(yīng)用中發(fā)揮重要作用。了解哈希表的原理和實(shí)現(xiàn)方式,將有助于我們更好地理解這個數(shù)據(jù)結(jié)構(gòu)以及如何應(yīng)用它來解決實(shí)際問題。
到此這篇關(guān)于C語言 哈希查找(哈希表的創(chuàng)建、處理沖突、查找等)的文章就介紹到這了,更多相關(guān)C語言 哈希查找內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Linux系統(tǒng)下C語言中的標(biāo)準(zhǔn)IO總結(jié)
最近用到了C語言的標(biāo)準(zhǔn)IO庫,由于對其中的一些細(xì)節(jié)不是非常清楚,導(dǎo)致了許多Bug,花了好長時間來調(diào)試,所以在此做個筆記,這篇文章主要給大家介紹了關(guān)于Linux系統(tǒng)下C語言中標(biāo)準(zhǔn)IO的相關(guān)資料,需要的朋友可以參考下2024-01-01c++中的消息框messagebox()詳細(xì)介紹及使用方法
本文將介紹下c++中的messagebox()的使用方法:常用屬性/按鈕的形式/返回值等等,感興趣的朋友可以了解下,希望本文可以幫助到你2013-02-02C++面試基礎(chǔ)之static關(guān)鍵字詳解
這篇文章主要給大家介紹了關(guān)于C++面試基礎(chǔ)之static關(guān)鍵字的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02C++實(shí)現(xiàn)銀行排隊(duì)系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)銀行排隊(duì)系統(tǒng),具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-07-07C++ Boost MultiIndex使用詳細(xì)介紹
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫,作為標(biāo)準(zhǔn)庫的后備,是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一,是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱2022-11-11