@[TOC]
哈希表和哈希函數(shù)的概念
??哈希表（散列表）棘伴，是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說深纲，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄召川，以加快查找的速度。這個映射函數(shù)叫做哈希（散列）函數(shù)目锭，存放記錄的數(shù)組叫做哈希（散列）表。
??給定表M纷捞，存在函數(shù)f(key)痢虹，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址主儡，則稱表M為哈希(Hash）表世分，函數(shù)f(key)為哈希(Hash) 函數(shù)。
??數(shù)據(jù)的哈希地址=f（關(guān)鍵字的值）缀辩。
??哈希地址只是表示在查找表中的存儲位置，而不是實際的物理存儲位置踪央。f（）是一個函數(shù)臀玄，通過這個函數(shù)可以快速求出該關(guān)鍵字對應(yīng)的的數(shù)據(jù)的哈希地址，稱之為“哈希函數(shù)”畅蹂。
哈希函數(shù)的構(gòu)造
直接定址法
??取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址健无。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）液斜。若其中H(key）中已經(jīng)有值了累贤，就往下一個找叠穆，直到H(key）中沒有值了，就放進去臼膏。
??例如有一個從 1 歲到 100 歲的人口數(shù)字統(tǒng)計表
??假設(shè)其哈希函數(shù)為第一種形式硼被，其關(guān)鍵字的值表示最終的存儲位置。若需要查找年齡為 25 歲的人口數(shù)量渗磅，將年齡 25 帶入哈希函數(shù)中嚷硫，直接求得其對應(yīng)的哈希地址為 25（求得的哈希地址表示該記錄的位置在查找表的第 25 位）。一般用數(shù)組實現(xiàn)始鱼。
數(shù)字分析法
??如果關(guān)鍵字由多位字符或者數(shù)字組成仔掸，就可以考慮抽取其中的 2 位或者多位作為該關(guān)鍵字對應(yīng)的哈希地址，在取法上盡量選擇變化較多的位医清，避免沖突發(fā)生起暮。
??比如一組員工的出生年月日，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同会烙，這樣的話负懦，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大持搜，如果用后面的數(shù)字來構(gòu)成散列地址密似，則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律葫盼，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址残腌。
平方取中法
??對關(guān)鍵字做平方操作，取中間得幾位作為哈希地址贫导。此方法也是比較常用的構(gòu)造哈希函數(shù)的方法抛猫。
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議孩灯，轉(zhuǎn)載請附上原文出處鏈接和本聲明闺金。
本文鏈接：https://blog.csdn.net/qq_16933601/article/details/107168076
??例如關(guān)鍵字序列為{421，423峰档，436}败匹，對各個關(guān)鍵字進行平方后的結(jié)果為{177241，178929讥巡，190096}掀亩，則可以取中間的兩位{72，89欢顷，00}作為其哈希地址槽棍。
折疊法
??例如，在圖書館中圖書都是以一個 10 位的十進制數(shù)字為關(guān)鍵字進行編號的，若對其查找表建立哈希表時炼七，就可以使用折疊法缆巧。
??若某書的編號為：0-442-20586-4，分割方式如圖 1 中所示豌拙，在對其進行折疊時有兩種方式：一種是移位折疊陕悬，另一種是間界折疊：
- 移位折疊是將分割后的每一小部分，按照其最低位進行對齊姆蘸，然后相加墩莫，如下圖 （a）；
- 間界折疊是從一端向另一端沿分割線來回折疊逞敷，如下圖（b）狂秦。
除留余數(shù)法（常用）
??取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m推捐。不僅可以對關(guān)鍵字直接取模裂问，也可在折疊、平方取中等運算之后取模牛柒。
??對p的選擇很重要堪簿，一般取素數(shù)或m，若p選的不好皮壁，容易產(chǎn)生同義詞（即沖突）椭更。
??由經(jīng)驗得知 p 可以為不大于 m 的質(zhì)數(shù)或者不包含小于 20 的質(zhì)因數(shù)的合數(shù)。
隨機數(shù)法
??取關(guān)鍵字的一個隨機函數(shù)值作為它的哈希地址蛾魄，即：
H（key）=random（key）虑瀑，此方法適用于關(guān)鍵字長度不等的情況。
??注意：這里的隨機函數(shù)其實是偽隨機函數(shù)滴须，隨機函數(shù)是即使每次給定的 key 相同舌狗，但是 H（key）都是不同；而偽隨機函數(shù)正好相反扔水，每個 key 都對應(yīng)的是固定的 H（key）痛侍。
哈希函數(shù)的選擇
??如此多的構(gòu)建哈希函數(shù)的方法，在選擇的時候魔市，需要根據(jù)實際的查找表的情況采取適當(dāng)?shù)姆椒ㄖ鹘臁Ｍǔ？紤]的因素有以下幾方面：
- 關(guān)鍵字的長度待德。如果長度不等岂膳，就選用隨機數(shù)法。如果關(guān)鍵字位數(shù)較多磅网，就選用折疊法或者數(shù)字分析法；反之如果位數(shù)較短筷屡，可以考慮平方取中法涧偷；
- 哈希表的大小簸喂。如果大小已知，可以選用除留余數(shù)法燎潮；
- 關(guān)鍵字的分布情況喻鳄；
- 查找表的查找頻率；
- 計算哈希函數(shù)所需的時間（包括硬件指令的因素）
處理沖突的方法
??哈希沖突只能盡量減少但是不能完全避免了确封，通常處理哈希沖突的方法有以下幾種
開放定址法
??H（key）=（H（key）+ d）MOD m（其中 m 為哈希表的表長除呵，d 為一個增量）
??當(dāng)?shù)贸龅墓５刂樊a(chǎn)生沖突時，選取以下 3 種方法中的一種獲取 d 的值爪喘，然后繼續(xù)計算颜曾，直到計算出的哈希地址不在沖突為止，這 3 種方法為：
- 線性探測法：d=1秉剑，2泛豪，3，…侦鹏，m-1
- 二次探測法：d=12诡曙，-12，22略水，-22价卤，32，…
- 偽隨機數(shù)探測法：d=偽隨機數(shù)
??例如渊涝，在長度為 11 的哈希表中已填寫好 17慎璧、60 和 29 這 3 個數(shù)據(jù)（如圖（a） 所示），其中采用的哈希函數(shù)為：H（key）=key MOD 11驶赏，現(xiàn)有第 4 個數(shù)據(jù) 38 炸卑，當(dāng)通過哈希函數(shù)求得的哈希地址為 5，與 60 沖突煤傍，則分別采用以上 3 種方式求得插入位置如圖 （b）所示：
??注釋：在線性探測法中盖文，當(dāng)遇到?jīng)_突時，從發(fā)生沖突位置起蚯姆，每次 +1五续，向右探測，直到有空閑的位置為止龄恋；二次探測法中疙驾，從發(fā)生沖突的位置起，按照 +12郭毕，-12它碎，+22，…如此探測，直到有空閑的位置扳肛；偽隨機探測傻挂，每次加上一個隨機數(shù)，直到探測到空閑位置結(jié)束挖息。
再哈希法
??當(dāng)通過哈希函數(shù)求得的哈希地址同其他關(guān)鍵字產(chǎn)生沖突時金拒，使用另一個哈希函數(shù)計算，直到?jīng)_突不再發(fā)生套腹。
鏈地址法
??將所有產(chǎn)生沖突的關(guān)鍵字所對應(yīng)的數(shù)據(jù)全部存儲在同一個線性鏈表中绪抛。例如有一組關(guān)鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函數(shù)為：H(key)=key MOD 13电禀，使用鏈地址法所構(gòu)建的哈希表如下圖 所示：
建立一個公共溢出區(qū)
??建立兩張表幢码，一張為基本表，另一張為溢出表鞭呕「蛴基本表存儲沒有發(fā)生沖突的數(shù)據(jù)，當(dāng)關(guān)鍵字由哈希函數(shù)生成的哈希地址產(chǎn)生沖突時葫松，就將數(shù)據(jù)填入溢出表瓦糕。
代碼實現(xiàn)
??在哈希表中進行查找的操作同哈希表的構(gòu)建過程類似，其具體實現(xiàn)思路為：對于給定的關(guān)鍵字K腋么，將其帶入哈希函數(shù)中咕娄，求得與該關(guān)鍵字對應(yīng)的數(shù)據(jù)的哈希地址，如果該地址中沒有數(shù)據(jù)珊擂，則證明該查找表中沒有存儲該數(shù)據(jù)圣勒，查找失敗：如果哈希地址中有數(shù)據(jù)摧扇，就需要做進一步的證明（排除沖突的影響）圣贸，找到該數(shù)據(jù)對應(yīng)的關(guān)鍵字同K 進行比對，如果相等扛稽，則查找成功吁峻；反之，如果不相等在张，說明在構(gòu)造哈希表時發(fā)生了沖突用含，需要根據(jù)構(gòu)造表時設(shè)定的處理沖突的方法找到下一個地址，同地址中的數(shù)據(jù)進行比對帮匾，直至遇到地址中數(shù)據(jù)為NULL（說明查找失斪暮А），或者比對成功瘟斜。
版權(quán)聲明：本文為博主原創(chuàng)文章缸夹，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議痪寻，轉(zhuǎn)載請附上原文出處鏈接和本聲明。
本文鏈接：https://blog.csdn.net/qq_16933601/article/details/107168076
/*
* @Author: Carlos
* @Date: 2020-07-2 23:48:50
* @LastEditTime: 2020-07-2 23:48:50
* @LastEditors: Carlos
* @Description: Hash
*/
#include "stdio.h"
#include "stdlib.h"
#define HASHSIZE 7 //定義散列表長為數(shù)組的長度
#define NULLKEY -1
typedef struct
{
int *elem; //數(shù)據(jù)元素存儲地址明未，動態(tài)分配數(shù)組
int count; //當(dāng)前數(shù)據(jù)元素個數(shù)
} HashTable;
/**
* @Description: 哈希函數(shù)初始化
* @Param: HashTable *hashTable 結(jié)構(gòu)體指針
* @Return: 無
* @Author: Carlos
*/
void Init(HashTable *hashTable)
{
int i;
hashTable->elem = (int *)malloc(HASHSIZE * sizeof(int));
hashTable->count = HASHSIZE;
for (i = 0; i < HASHSIZE; i++)
{
hashTable->elem[i] = NULLKEY;
}
}
/**
* @Description: 哈希函數(shù)(除留余數(shù)法)
* @Param: int data 哈希的數(shù)據(jù)
* @Return: 哈希后data存儲的地址
* @Author: Carlos
*/
int Hash(int data)
{
return data % HASHSIZE;
}
/**
* @Description: 哈希表的插入函數(shù)槽华，可用于構(gòu)造哈希表
* @Param: HashTable *hashTable 結(jié)構(gòu)體指針，int data 哈希的數(shù)據(jù)
* @Return: 無
* @Author: Carlos
*/
void Insert(HashTable *hashTable, int data)
{
int hashAddress = Hash(data); //求哈希地址
//發(fā)生沖突
while (hashTable->elem[hashAddress] != NULLKEY)
{
//利用開放定址法解決沖突
hashAddress = (++hashAddress) % HASHSIZE;
}
hashTable->elem[hashAddress] = data;
}
/**
* @Description: 哈希表的查找算法
* @Param: HashTable *hashTable 結(jié)構(gòu)體指針趟妥，int data 哈希的數(shù)據(jù)
* @Return: 無
* @Author: Carlos
*/
int Search(HashTable *hashTable, int data)
{
int hashAddress = Hash(data); //求哈希地址
while (hashTable->elem[hashAddress] != data)
{ //發(fā)生沖突
//利用開放定址法解決沖突
hashAddress = (++hashAddress) % HASHSIZE;
//如果查找到的地址中數(shù)據(jù)為NULL，或者經(jīng)過一圈的遍歷回到原位置佣蓉，則查找失敗
if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data))
{
return -1;
}
}
return hashAddress;
}
int main()
{
int i, result;
HashTable hashTable;
int arr[HASHSIZE] = {13, 29, 27, 28, 26, 30, 38};
//初始化哈希表
Init(&hashTable);
//利用插入函數(shù)構(gòu)造哈希表
for (i = 0; i < HASHSIZE; i++)
{
Insert(&hashTable, arr[i]);
}
//調(diào)用查找算法
result = Search(&hashTable, 29);
if (result == -1)
printf("查找失敗");
else
printf("29 在哈希表中的位置是:%d", result + 1);
return 0;
}
有任何疑問披摄，點擊我的頭像可以在主頁的個人介紹中找到我的聯(lián)系方式，歡迎一起交流學(xué)習(xí)
版權(quán)聲明：本文為博主原創(chuàng)文章勇凭，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議疚膊，轉(zhuǎn)載請附上原文出處鏈接和本聲明。
本文鏈接：https://blog.csdn.net/qq_16933601/article/details/107168076
