前言

哈希查找（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)偣_突，并減少鏈表長度。但是，此方式的代價較大，因為需要對數(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)文章希望大家以后多多支持腳本之家！

最新評論