創(chuàng)作不易，本篇文章如果幫助到了你，還請點贊 關(guān)注支持一下?>??<)!!
主頁專欄有更多知識，如有疑問歡迎大家指正討論，共同進步！
更多算法分析與設(shè)計知識專欄：算法分析??
給大家跳段街舞感謝支持！? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

一、哈希表介紹

哈希表(HashMap、unordered_map)又稱為散列表，是一種可以對已經(jīng)存儲的數(shù)據(jù)進行快速查找的數(shù)據(jù)結(jié)構(gòu)，它可以根據(jù)鍵（Key）值直接進行訪問。
舉幾個栗子：

在電話簿中，每個電話號碼對應一個名字，在查找某個人的電話號碼時根據(jù)姓名即可進行快速查找，這實際上就利用了哈希思想，鍵是電話號碼，值是名字。

如果要對某字符串進行反復搜索的操作，每次都遍歷字符串效率太低，使用哈希思想將字符進行分組(例如分為256組)，然后將每個字符按照規(guī)則存儲(將字符串中的每個字符通過哈希函數(shù)進行映射)，在后續(xù)對字符查找時即可通過關(guān)鍵字key進行快速查找到字符的存儲位置，可以在常數(shù)時間內(nèi)進行查找、插入和刪除操作。

哈希表主要利用了分組的思想，采用散列(映射)技術(shù)

哈希表的增刪查時間復雜度都是O(1)

散列技術(shù)

散列技術(shù)是一種可以用于快速查找的存儲技術(shù)，通過散列函數(shù)(哈希函數(shù))將一組數(shù)據(jù)按照特征建立對應關(guān)系。查找時只需要根據(jù)對應關(guān)系找到關(guān)鍵字key的映射，映射到內(nèi)存中的一個位置。

二、哈希表的創(chuàng)建

1.確定哈希函數(shù)

哈希函數(shù)可以根據(jù)數(shù)據(jù)的情況不同進行不同的設(shè)計，最好要滿足容易計算并且根據(jù)數(shù)據(jù)特征均勻分布

例如：
按照數(shù)據(jù)類型分組：

• 將字符按照ASCLL碼分為256組
• 將班級同學按照省份分組

取余法：
通過將關(guān)鍵字除以一個素數(shù)取余數(shù)作為哈希表中的位置

p = key%m

2.哈希沖突的解決方案

在理想情況下，不同的鍵值能夠映射到不同的索引，但是在實際中，可能存在不同的鍵值映射到相同的索引的情況，這種情況稱為哈希沖突。

舉個栗子：
如果現(xiàn)在要存放Tianxi這個字符串，通過對取余法存入到哈希表中，如下圖所示：
T i a n 都依次正常存入了，到字符x時發(fā)現(xiàn)索引0已經(jīng)被字符T占用了：

這就是不同的鍵映射到相同的索引，即哈希沖突，要解決哈希沖突有例如下面的方法：

i.開放定址法

當發(fā)生沖突時，使用某種探查技術(shù)在散列表中形成一個探查序列
可以分為：

• 線性探測

發(fā)生沖突時，線性探測會按照步長依次探測下一個位置，直到找到空位或找到目標元素為止

• 線性補償探測

線性補償探測是線性探測的一種改進版本。它同樣按照一定的步長探測哈希表中的下一個位置，但是當連續(xù)探測若干個位置都發(fā)生沖突時，它會增加步長的大?。看卧黾右欢ù笮。?，能夠加快探測速度

沿此序列逐個單元地查找，直到找到一個開放的地址為止，例如可以將上面的x存入key = 5中

ii.鏈式地址法

拉鏈法中，哈希表中每個鍵對應的值都為一個鏈表的頭節(jié)點，當發(fā)生哈希沖突時，新的鍵值對會被插入到相應的鏈表中。
如下圖所示，字符x發(fā)生哈希沖突時將其加入到鏈表頭節(jié)點中：

當哈希沖突較為頻繁時，鏈表可能會變得很長，導致查找效率下降

鏈式地址取余法代碼實現(xiàn)（C/C++）

• 1.申請表頭 表頭初始化
• 2.取余獲得索引位置 元素入表
• 3.節(jié)點空間申請 頭添加

#define MOD 6

typedef struct Node
{
	int val;
	struct Node* pNextNode;
}ListNode;

ListNode** createHash(int arr[], int length)
{
	if (arr == NULL || length <= 0) return NULL;
	//申請表頭
	ListNode** pHash = (ListNode**)malloc(sizeof(ListNode*) * MOD);
	memset(pHash, 0, sizeof(ListNode*) * MOD);
	//元素入表
	int nIndex;
	for (int i = 0; i < length; i++)
	{
		//獲得索引位置
		nIndex = arr[i] % MOD;
		//節(jié)點空間申請
		ListNode* pTempNode = NULL;
		pTempNode = (ListNode*)malloc(sizeof(ListNode));
		pTempNode->val = arr[i];

		//頭添加
		pTempNode->pNextNode = pHash[nIndex];
		pHash[nIndex] = pTempNode;
	}
	return pHash;
}

三、哈希表的使用

• 1.取余獲得索引位置
• 2.遍歷鏈表

void HashSearch(ListNode** pHash, int target)
{
	if (pHash == NULL)return;
	int nIndex = target % MOD;
	ListNode* pTempNode = pHash[nIndex];
	while (pTempNode)
	{
		if (pTempNode->val == target)
		{
			printf("success!\n");
			return;
		}
		else
		{
			pTempNode = pTempNode->pNextNode;
		}
	}
	printf("fail!\n");
	return;
}

測試代碼：

110查詢成功，100查詢失敗

文章來源地址http://www.zghlxwxcb.cn/news/detail-793936.html

到了這里，關(guān)于【算法】哈希表介紹 | 哈希表的鏈式地址法代碼實現(xiàn)（C/C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！