【演算法視訊】雜湊查詢-鏈地址法

1.3.1、雜湊查詢-鏈地址法

資訊網址:www.qghkt.com

騰訊課堂:https://qghkt.ke.qq.com/20個常用演算法

根據設定的雜湊函式Hash(key)和處理衝突的方法,將一組關鍵碼對映到一個有限的連續的地址集(區間)上,並以關鍵碼在地址集中的“像”作為記錄在表中的儲存位置,這種表稱為雜湊表,這一對映過程稱為雜湊造表或雜湊,所得的儲存位置稱為雜湊地址或雜湊地址。

       對於某個雜湊函式Hash和兩個關鍵碼K1和K2,如果K1≠K2而Hash(K1)=Hash(K2),則稱為出現了衝突,對該雜湊函式來說,K1和K2稱為同義詞。

       一般情況下,衝突不能完全避免,只能儘可能地去減少衝突,因此在建造雜湊表時不僅要設定一個“好”的雜湊函式,而且要設定處理衝突的方法。

其中,Hash(key)為雜湊函式;m為雜湊表的表長;為增量序列。

常見的增量序列有如下3種:

①  =1,2,3,…,m-1,稱為線性探測再雜湊

②  =,,,…,(k),稱為二次探測再雜湊

③  =偽隨機序列,稱為隨機探測再雜湊。

 

2)鏈地址法

【基本思路】

根據雜湊函式得到元素所在連結串列的頭指標,然後在連結串列中進行順序查詢即可。

【圖解過程】

設關鍵碼序列為47,34,19,12,52,38,33,57,63,21,雜湊表表長為11,雜湊函式為Hash(key) = key mod 11。

雜湊地址

0

1

2

3

4

5

6

7

8

9

10

關鍵碼

˄

˄

˄

˄

 

33

34

57

47

 

38

 

 

19

 

21

 

˄

˄

˄

 

˄

 

 

 

˄

 

 

12

 

 

 

 

 

 

52

 

 

 

 

˄

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

63

 

 

 

 

 

 

 

 

 

 

 

˄

 

 

 

 

 

 

 

 

 

 

 

【適用場景】

       依據記錄的關鍵碼直接得到其對應的儲存位置,即要求記錄的關鍵碼與其儲存位置之間存在一一對應關係,從而快速地找到記錄。

【演算法程式碼】

/////鏈式

//定義雜湊表中的節點

typedef structnodeInfo

{

       int key;

       struct nodeInfo *next;

}structNodeInfo;

 

 

/****************************************************************

 * 函式名稱:createChainHashTable

 * 功能描述:造鏈式的雜湊表

 * 引數說明:hashArr, 結構體的雜湊表

 *                 hashLen,雜湊表的表長,以及是modvalue.

 *                 keyArr,關鍵碼的序列

 *                 keyLen,關鍵碼序列的長度

 * 返回 值:void

 * 作    者:www.qghkt.com

 * 建立時間:

*****************************************************************

 * Copyright @ 清哥好課堂  All rightsreserved

*****************************************************************/

voidcreateChainHashTable(structNodeInfo*hashArr[], int hashLen, int keyArr[], intkeyLen)

{

       //造雜湊表

       int i;

       //初始化

       for (i = 0; i < hashLen; i )

       {

              hashArr[i] = NULL; //空

       }

       for (i = 0; i < keyLen; i )

       {

              int hashAdd = keyArr[i] % hashLen;

              structNodeInfo *p =(structNodeInfo *)malloc(sizeof(structNodeInfo));

              p->key = keyArr[i];

              p->next = NULL;

              if (hashArr[hashAdd] == NULL)

              {

                     //當前為空

                     hashArr[hashAdd] = p;

              }

              else

              {//不為空,要遍歷整個鏈,把p接到鏈的最後位置

                     structNodeInfo *pTemp =hashArr[hashAdd];

                     while (pTemp->next !=NULL)

                     {

                            pTemp =pTemp->next;

                     }

                     pTemp->next = p;

              }

       }

}

 

 

/****************************************************************

 * 函式名稱:chainHashSearch

 * 功能描述:鏈式雜湊表的查詢

 * 引數說明:hashArr,雜湊表

 *                 hashLen,雜湊表的表長,以及是雜湊函式的mod值

 *                 value,要查詢的值

 * 返回 值:如果不存在,返回-1, 如果存在,返回雜湊表中的位置

 * 作    者:www.qghkt.com

 * 建立時間:

*****************************************************************

 * Copyright @ 清哥好課堂  All rightsreserved

*****************************************************************/

intchainHashSearch(structNodeInfo *hashArr[], int hashLen, int value)

{

       int hashAdd = value % hashLen;

       structNodeInfo *p = hashArr[hashAdd];

       while (p != NULL)

       {

              if (p->key == value)

              {//找到了對應的值

                     return hashAdd;

              }

              p = p->next;

       }

       return -1;

}