欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言 哈希查找詳解(哈希表的創(chuàng)建、處理沖突、查找等)

 更新時間:2024年01月02日 09:55:59   作者:花開富貴?  
哈希表是一種非常重要的數(shù)據(jù)結(jié)構(gòu),并在大量的計算機(jī)科學(xué)和工程應(yīng)用中發(fā)揮重要作用,了解哈希表的原理和實(shí)現(xiàn)方式,將有助于我們更好地理解這個數(shù)據(jù)結(jié)構(gòu)及如何應(yīng)用它來解決實(shí)際問題,這篇文章主要介紹了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)文章

  • C++中Stack(棧)的使用方法與基本操作詳解

    C++中Stack(棧)的使用方法與基本操作詳解

    Stack是一種常見的數(shù)據(jù)結(jié)構(gòu),常常被用來解決遞歸問題、括號匹配問題、函數(shù)調(diào)用棧等等。本文將介紹C++中stack的使用方法及基本操作,需要的可以參考一下
    2023-05-05
  • Linux系統(tǒng)下C語言中的標(biāo)準(zhǔn)IO總結(jié)

    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-01
  • c++中的消息框messagebox()詳細(xì)介紹及使用方法

    c++中的消息框messagebox()詳細(xì)介紹及使用方法

    本文將介紹下c++中的messagebox()的使用方法:常用屬性/按鈕的形式/返回值等等,感興趣的朋友可以了解下,希望本文可以幫助到你
    2013-02-02
  • C++面試基礎(chǔ)之static關(guān)鍵字詳解

    C++面試基礎(chǔ)之static關(guān)鍵字詳解

    這篇文章主要給大家介紹了關(guān)于C++面試基礎(chǔ)之static關(guān)鍵字的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-02-02
  • C++實(shí)現(xiàn)銀行排隊(duì)系統(tǒng)

    C++實(shí)現(xiàn)銀行排隊(duì)系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)銀行排隊(duì)系統(tǒng),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-07-07
  • C語言實(shí)現(xiàn)簡單通訊錄功能

    C語言實(shí)現(xiàn)簡單通訊錄功能

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡單通訊錄功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • C++ Boost MultiIndex使用詳細(xì)介紹

    C++ 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
  • C++遍歷文件夾目錄的方法

    C++遍歷文件夾目錄的方法

    這篇文章主要介紹了C++遍歷文件夾目錄的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-04-04
  • 如何尋找數(shù)組中的第二大數(shù)

    如何尋找數(shù)組中的第二大數(shù)

    本篇文章是對如何尋找數(shù)組中的第二大數(shù)進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • 詳解Matlab如何繪制?;鶊D

    詳解Matlab如何繪制?;鶊D

    ?;鶊D是一種特定類型的流程圖,圖中延伸的分支的寬度對應(yīng)數(shù)據(jù)流量的大小,通常應(yīng)用于能源、材料成分、金融等數(shù)據(jù)的可視化分析。本文將用Matlab繪制好看的?;鶊D,需要的可以參考一下
    2022-03-03

最新評論