經典算法學習——哈希查找

哈希查找也稱為散列查找。所謂的哈希其實就是在記錄的存儲位置和記錄的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)。查找時，根據這個確定的對應關系找到給定值的映射f(key),若查找集合中存在這個記錄，則必定在f(key)的位置上。哈希技術既是一種存儲方法，也是一種查找方法。示例代碼上傳至：https://github.com/chenyufeng1991/HashSearch 。

六種哈希函數的構造方法：

（1）直接定址法

函數公式：f(key) = a * key + b（a,b為常數）

這種方法的優點是：簡單、均勻，不會產生沖突。但是需要事先知道關鍵字的分布情況，適合查找表較小並且連續的情況。

（2）數字分析法

也就是取出關鍵字中的若干位組成哈希地址。比如我們的11位手機號是“187****1234”，其中前三位是接入號，一般對應不同的電信公司。中間四位表示歸屬地。最後四位才表示真正的用戶號。

如果現在要存儲某個部門的員工的手機號，使用手機號碼作為關鍵字，那麼很有可能前面7位都是相同的，所以我們選擇後面的四位作為哈希地址就不錯。

（3）平方取中法

取關鍵字平方後的中間幾位作為哈希地址。由於一個數的平方的中間幾位與這個數的每一位都有關，所以平方取中法產生沖突的機會相對較小。平方取中法所取的位數由表長決定。

如：K=456，K^2=207936,如果哈希表的長度為100，則可以取79（中間兩位）作為哈希函數值。

（4）折疊法

折疊法是將關鍵字從左到右分割成位數相等的幾個部分（最後一部分位數不夠可以短），然後將這幾部分疊加求和，並按哈希表表長，取後幾位作為哈希地址。當關鍵字位數很多，而且關鍵字中每一位上數字分布大致均勻時，可以使用折疊法。

如：我們的關鍵字是9876543210，哈希表表長三位，我們可以分為四組：987 | 654 | 321 | 0，然後將他們疊加求和：987+654+321+0 = 1962,再取後三位就可以得到哈希地址為962.

（5）除留余數法

選擇一個適當的正整數p（p<=表長），用關鍵字除以p，所得的余數可以作為哈希地址。即：H(key) = key % p(p<=表長)，除留余數法的關鍵是選取適當的p，一般選p為小於或等於哈希表的長度(m)的某個素數。

如：m = 8,p=7.

m = 16,p = 13.

m = 32,p = 31.

（6）隨機數法

函數公式：f(key) = random(key). 這裡的random是隨機函數，當關鍵字的長度不等時，采用這種方式比較合適。

總之，哈希函數的規則就是：通過某種轉換關系，使關鍵字適度的分散到指定大小的順序結構中。越分散，查找的時間復雜度就越小， 空間復雜度就越高。哈希查找明顯是一種以空間換時間的算法。

 

上面提到了如何構造一個哈希函數，那就不得不提如何避免沖突的算法。

（1）開放定址法

當沖突發生時，使用某種方法在哈希表中形成一探查序列。然後沿著該探查序列逐個單位的查找，直到找到一個開放的地址（即該地址單元為空）為止。對於哈希表中形成一探查序列時，可以有3種不同的方法：

1.線性探測法

將散列看成一個環形表，探測序列是（假設表長為m）：

H(k),H(k)+1,H(k)+2.....m-1,0,1......H(k)-1。用線性探測法解決沖突時，求下一個開放地址的公式為：Hi = (H(k)+i) MOD m.

2.二次探測法

二次探測法的探測序列依次是12，-12，22，-22等等。當發生沖突時，求下一個開放地址的公式為：

H2i-1=(H(k)+i2)MODm

H2i=(H(k)-i2)MODm(1=優點：減少了堆集發生的可能性；

缺點：不容易探測到哈希表空間。

3.偽隨機探測法

采用隨機探測法解決沖突時，下一個開放地址的公式為：Hi=(H(k)+Ri)MODm。

其中R1,R2,...,Rm-1是一個隨機排列。

（2）再哈希法

當沖突發生時，使用另一個函數計算得到一個新的哈希地址，直到沖突不再發生時為止。Hi=RHi(key)i=1,2,…,k 。其中RHi均是不同的哈希函數。優點是不易產生聚集，缺點是增加了計算時間。

（3）鏈地址法

將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的哈希函數所產生的哈希地址為0~m-1,則可以將哈希表定義成一個由m個鏈表頭指針組成的指針數組。優點是：不產生聚集；由於結點空間是動態申請的，故更適合造表前無法確定表長的情況；從表中刪除節點容易。

（4）公共溢出區法

假設哈希函數的值域為[0...m-1]，則設向量HashTable[0...m-1]為基本表，每個分量存放一個記錄，另設立向量OverTable[0..v]為溢出表。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管它們由哈希函數得到的哈希地址是什麼，一旦發生沖突，都被填入溢出表中。

在哈希表上進行查找的過程和建表的過程基本一致。假設給定的值為k，根據建表時設定的哈希函數H，計算出哈希地址H(k),若表中該地址對應的空間未被占用。則查找失敗。否則將該地址中的節點與給定值k比較，若相等則查找成功，否則按建表時設定的處理沖突方法找下一個地址，如此反復下去，直到找到某個地址空間未被占用（查找失敗）或者關鍵字比較相等（查找成功）為止。

代碼如下：

//
//  main.c
//  HashSearch
//
//  Created by chenyufeng on 16/2/17.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include "stdio.h"
#include "stdlib.h"

#define HASHSIZE 7 // 定義散列表長為數組的長度
#define NULLKEY -32768

typedef int Status;
typedef struct{
    int *elem; // 數據元素存儲地址，動態分配數組
    int count; //  當前數據元素個數
}HashTable;

// 散列表表長，全局變量
int m = 0;

void InitHashTable(HashTable *hashTable);
Status Hash(int key);
void Insert(HashTable *hashTable,int key);
Status Search(HashTable *hashTable,int key);
void DisplayHashTable(HashTable *hashTable);

int main(int argc, const char * argv[]) {

    int result;
    HashTable hashTable;
    int arr[HASHSIZE] = {13,29,27,28,26,30,38};

    //初始化哈希表
    InitHashTable(&hashTable);

    /**
     *  向哈希表中插入數據;
     也就是把元素使用哈希函數映射到哈希表中；
     */
    for (int i = 0;i < HASHSIZE;i++){
        Insert(&hashTable,arr[i]);
    }
    //數據已存到哈希表中，打印觀察哈希表，元素的位置和原數組是完全不一樣的
    DisplayHashTable(&hashTable);

    //查找數據
    result = Search(&hashTable,30);
    if (result == -1){
        printf("沒有找到！");
    }else{
        printf("在哈希表中的位置是:%d\n",result);
    }

    return 0;
}

//初始化一個空的哈希表
void InitHashTable(HashTable *hashTable){

    m = HASHSIZE;
    hashTable->elem = (int *)malloc(m * sizeof(int)); //申請內存
    hashTable->count = m;
    for(int i = 0;i < m;i++){
        hashTable->elem[i] = NULLKEY;
    }
}

//哈希函數(除留余數法)
Status Hash(int key){
    return key % m;
}

//插入
void Insert(HashTable *hashTable,int key){

    /**
     *  根據每一個關鍵字，計算哈希地址hashAddress；
     */
    int hashAddress = Hash(key); //求哈希地址
    /**
     *  發生沖突，表示該位置已經存有數據
     */
    while(hashTable->elem[hashAddress] != NULLKEY){
        //利用開放定址的線性探測法解決沖突
        hashAddress = (hashAddress + 1) % m;
    }
    //插入值
    hashTable->elem[hashAddress] = key;
}

//查找
Status Search(HashTable *hashTable,int key){
    //求哈希地址
    int hashAddress = Hash(key);
    //發生沖突
    while(hashTable->elem[hashAddress] != key){
        //利用開放定址的線性探測法解決沖突
        hashAddress = (hashAddress + 1) % m;
        if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(key)){
            return -1;
        }
    }
    //查找成功
    return hashAddress;
}

//打印結果
void DisplayHashTable(HashTable *hashTable){
    for (int i = 0;i < hashTable->count;i++){
        printf("%d ",hashTable->elem[i]);
    }
    printf("\n");
}

在C語言編程中，我們常常會設定一些預定義常量，或者說是函數的結果狀態碼，如下所示：

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

因為在C語言中是沒有BOOL布爾這種數據類型的，所以上面的預定義可以簡化編程。我們有時候還會進行如下的預定義：

typedef int Status;

表示Status是函數的返回類型，其值是函數結果狀態代碼。我在上述代碼中也使用了這種預定義。