哈希表和哈希函式的概念
哈希函式的構造
- 直接定址法
- 數字分析法
- 平方取中法
- 折疊法
- 除留余數法（常用）
- 亂數法
- 哈希函式的選擇
處理沖突的方法
- 開放定址法
- 再哈希法
- 鏈地址法
- 建立一個公共溢位區
代碼實作

哈希表和哈希函式的概念

??哈希表（散串列），是根據關鍵碼值(Key value)而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函式叫做哈希（散列）函式，存放記錄的陣列叫做哈希（散列）表，

??給定表M，存在函式f(key)，對任意給定的關鍵字值key，代入函式后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函式f(key)為哈希(Hash) 函式，

??資料的哈希地址=f（關鍵字的值），

??哈希地址只是表示在查找表中的存盤位置，而不是實際的物理存盤位置，f（）是一個函式，通過這個函式可以快速求出該關鍵字對應的的資料的哈希地址，稱之為“哈希函式”，

哈希函式的構造

直接定址法

??取關鍵字或關鍵字的某個線性函式值為散列地址，即H(key)=key或H(key) = a·key + b，其中a和b為常數（這種散列函式叫做自身函式），若其中H(key）中已經有值了，就往下一個找，直到H(key）中沒有值了，就放進去，
??例如有一個從 1 歲到 100 歲的人口數字統計表
在這里插入圖片描述
??假設其哈希函式為第一種形式，其關鍵字的值表示最終的存盤位置，若需要查找年齡為 25 歲的人口數量，將年齡 25 帶入哈希函式中，直接求得其對應的哈希地址為 25（求得的哈希地址表示該記錄的位置在查找表的第 25 位），一般用陣列實作，

數字分析法

??如果關鍵字由多位字符或者數字組成，就可以考慮抽取其中的 2 位或者多位作為該關鍵字對應的哈希地址，在取法上盡量選擇變化較多的位，避免沖突發生，
??比如一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體相同，這樣的話，出現沖突的幾率就會很大，但是我們發現年月日的后幾位表示月份和具體日期的數字差別很大，如果用后面的數字來構成散列地址，則沖突的幾率會明顯降低，因此數字分析法就是找出數字的規律，盡可能利用這些資料來構造沖突幾率較低的散列地址，

平方取中法

??對關鍵字做平方操作，取中間得幾位作為哈希地址，此方法也是比較常用的構造哈希函式的方法，

??例如關鍵字序列為{421，423，436}，對各個關鍵字進行平方后的結果為{177241，178929，190096}，則可以取中間的兩位{72，89，00}作為其哈希地址，

折疊法

??例如，在圖書館中圖書都是以一個 10 位的十進制數字為關鍵字進行編號的，若對其查找表建立哈希表時，就可以使用折疊法，

??若某書的編號為：0-442-20586-4，分割方式如圖 1 中所示，在對其進行折疊時有兩種方式：一種是移位折疊，另一種是間界折疊：

移位折疊是將分割后的每一小部分，按照其最低位進行對齊，然后相加，如下圖（a）；
間界折疊是從一端向另一端沿分割線來回折疊，如下圖（b），

在這里插入圖片描述

除留余數法（常用）

??取關鍵字被某個不大于散串列表長m的數p除后所得的余數為散列地址，即 H(key) = key MOD p,p<=m，不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之后取模，
??對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞（即沖突），
??由經驗得知 p 可以為不大于 m 的質數或者不包含小于 20 的質因數的合數，

亂數法

??取關鍵字的一個隨機函式值作為它的哈希地址，即：
H（key）=random（key），此方法適用于關鍵字長度不等的情況，

??注意：這里的隨機函式其實是偽隨機函式，隨機函式是即使每次給定的 key 相同，但是 H（key）都是不同；而偽隨機函式正好相反，每個 key 都對應的是固定的 H（key），

哈希函式的選擇

??如此多的構建哈希函式的方法，在選擇的時候，需要根據實際的查找表的情況采取適當的方法，通常考慮的因素有以下幾方面：

關鍵字的長度，如果長度不等，就選用亂數法，如果關鍵字位數較多，就選用折疊法或者數字分析法；反之如果位數較短，可以考慮平方取中法；
哈希表的大小，如果大小已知，可以選用除留余數法；
關鍵字的分布情況；
查找表的查找頻率；
計算哈希函式所需的時間（包括硬體指令的因素）

處理沖突的方法

??哈希沖突只能盡量減少但是不能完全避免了，通常處理哈希沖突的方法有以下幾種

開放定址法

??H（key）=（H（key）+ d）MOD m（其中 m 為哈希表的表長，d 為一個增量）
??當得出的哈希地址產生沖突時，選取以下 3 種方法中的一種獲取 d 的值，然后繼續計算，直到計算出的哈希地址不在沖突為止，這 3 種方法為：

線性探測法：d=1，2，3，…，m-1
二次探測法：d=12，-12，22，-22，32，…
偽亂數探測法：d=偽亂數

??例如，在長度為 11 的哈希表中已填寫好 17、60 和 29 這 3 個資料（如圖（a）所示），其中采用的哈希函式為：H（key）=key MOD 11，現有第 4 個資料 38 ，當通過哈希函式求得的哈希地址為 5，與 60 沖突，則分別采用以上 3 種方式求得插入位置如圖（b）所示：
在這里插入圖片描述
??注釋：在線性探測法中，當遇到沖突時，從發生沖突位置起，每次 +1，向右探測，直到有空閑的位置為止；二次探測法中，從發生沖突的位置起，按照 +12，-12，+22，…如此探測，直到有空閑的位置；偽隨機探測，每次加上一個亂數，直到探測到空閑位置結束，

再哈希法

??當通過哈希函式求得的哈希地址同其他關鍵字產生沖突時，使用另一個哈希函式計算，直到沖突不再發生，

鏈地址法

??將所有產生沖突的關鍵字所對應的資料全部存盤在同一個線性鏈表中，例如有一組關鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函式為：H(key)=key MOD 13，使用鏈地址法所構建的哈希表如下圖所示：
在這里插入圖片描述

建立一個公共溢位區

??建立兩張表，一張為基本表，另一張為溢位表，基本表存盤沒有發生沖突的資料，當關鍵字由哈希函式生成的哈希地址產生沖突時，就將資料填入溢位表，

代碼實作

??在哈希表中進行查找的操作同哈希表的構建程序類似，其具體實作思路為：對于給定的關鍵字K，將其帶入哈希函式中，求得與該關鍵字對應的資料的哈希地址，如果該地址中沒有資料，則證明該查找表中沒有存盤該資料，查找失敗：如果哈希地址中有資料，就需要做進一步的證明（排除沖突的影響），找到該資料對應的關鍵字同K 進行比對，如果相等，則查找成功；反之，如果不相等，說明在構造哈希表時發生了沖突，需要根據構造表時設定的處理沖突的方法找到下一個地址，同地址中的資料進行比對，直至遇到地址中資料為NULL（說明查找失敗），或者比對成功，

/*
 * @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 //定義散串列長為陣列的長度
#define NULLKEY -1
typedef struct
{
    int *elem; //資料元素存盤地址，動態分配陣列
    int count; //當前資料元素個數
} HashTable;
/**
 * @Description: 哈希函式初始化
 * @Param: HashTable *hashTable 結構體指標
 * @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: 哈希函式(除留余數法)
 * @Param: int data 哈希的資料
 * @Return: 哈希后data存盤的地址
 * @Author: Carlos
 */
int Hash(int data)
{
    return data % HASHSIZE;
}
/**
 * @Description: 哈希表的插入函式，可用于構造哈希表
 * @Param: HashTable *hashTable 結構體指標，int data 哈希的資料
 * @Return: 無
 * @Author: Carlos
 */
void Insert(HashTable *hashTable, int data)
{
    int hashAddress = Hash(data); //求哈希地址
    //發生沖突
    while (hashTable->elem[hashAddress] != NULLKEY)
    {
        //利用開放定址法解決沖突
        hashAddress = (++hashAddress) % HASHSIZE;
    }
    hashTable->elem[hashAddress] = data;
}
/**
 * @Description: 哈希表的查找演算法
 * @Param: HashTable *hashTable 結構體指標，int data 哈希的資料
 * @Return: 無
 * @Author: Carlos
 */
int Search(HashTable *hashTable, int data)
{
    int hashAddress = Hash(data); //求哈希地址
    while (hashTable->elem[hashAddress] != data)
    { //發生沖突
        //利用開放定址法解決沖突
        hashAddress = (++hashAddress) % HASHSIZE;
        //如果查找到的地址中資料為NULL，或者經過一圈的遍歷回到原位置，則查找失敗
        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);
    //利用插入函式構造哈希表
    for (i = 0; i < HASHSIZE; i++)
    {
        Insert(&hashTable, arr[i]);
    }
    //呼叫查找演算法
    result = Search(&hashTable, 29);
    if (result == -1)
        printf("查找失敗");
    else
        printf("29 在哈希表中的位置是:%d", result + 1);
    return 0;
}

有任何問題，均可通過公告中的二維碼聯系我

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/247015.html

標籤：嵌入式

上一篇：查找演算法之順序查找，折半查找，二叉查找樹

下一篇：qsort函式使用方法總結（詳細全面+代碼）

哈希表基本概念介紹及哈希沖突的處理方法(附原始碼)