簡單講解哈希表

一、哈希表的概念

1、查找算法

  當我們在一個 鏈表 或者 順序表查找 一個數據元素 是否存在 的時候,唯一的方法就是遍歷整個表,這種方法稱為 線性枚舉

  如果這時候,順序表是有序的情況下,我們可以采用折半的方式去查找,這種方法稱為 二分枚舉
  線性枚舉 的時間復雜度為 O ( n ) O(n) O(n)。二分枚舉 的時間復雜度為 O(log2​n)。是否存在更快速的查找方式呢?這就是本要介紹的一種新的數據結構 —— 哈希表。

2、哈希表

  由於它不是順序結構,所以很多數據結構書上稱之為 散列表,下文會統一采用 哈希表 的形式來說明,作為讀者,隻需要知道這兩者是同一種數據結構即可。
  我們把需要查找的數據,通過一個 函數映射,找到 存儲數據的位置 的過程稱為 哈希。這裡涉及到幾個概念:
  a)需要 查找的數據 本身被稱為 關鍵字
  b)通過 函數映射關鍵字 變成一個 哈希值 的過程中,這裡的 函數 被稱為 哈希函數
  c)生成 哈希值 的過程過程可能產生沖突,需要進行 沖突解決
  d)解決完沖突以後,實際 存儲數據的位置 被稱為 哈希地址,通俗的說,它就是一個數組下標;
  e)存儲所有這些數據的數據結構就是 哈希表,程序實現上一般采用數組實現,所以又叫 哈希數組。整個過程如下圖所示:

3、哈希數組

  為瞭方便下標索引,哈希表 的底層實現結構是一個數組,數組類型可以是任意類型,每個位置被稱為一個槽。如下圖所示,它代表的是一個長度為 8 的 哈希表,又叫 哈希數組

4、關鍵字

  關鍵字 是哈希數組中的元素,可以是任意類型的,它可以是整型、浮點型、字符型、字符串,甚至是結構體或者類。如下的 A、C、M 都可以是關鍵字;

int A = 5;
char C[100] = "Hello World!";
struct Obj { };
Obj M;

  哈希表的實現過程中,我們需要通過一些手段,將一個非整型的 關鍵字 轉換成 數組下標,也就是 哈希值,從而通過O(1) 的時間快速索引到它所對應的位置。
  而將一個非整型的 關鍵字 轉換成 整型 的手段就是 哈希函數

5、哈希函數

  哈希函數可以簡單的理解為就是小學課本上那個函數,即

y = f ( x )

,這裡的 f(x) 就是哈希函數,x是關鍵字,y是哈希值。好的哈希函數應該具備以下兩個特質:
  a)單射;
  b)雪崩效應:輸入值x的 1比特的變化,能夠造成輸出值y至少一半比特的變化;
  單射很容易理解,圖 ( a ) (a) (a) 中已知哈希值 y 時,鍵 x 可能有兩種情況,不是一個單射;而圖 (b) 中已知哈希值 y時,鍵 x 一定是唯一確定的,所以它是單射。由於 x  和 y  一一對應,這樣就從本原上減少瞭沖突。

  

雪崩效應是為瞭讓哈希值更加符合隨機分佈的原則,哈希表中的鍵分佈的越隨機,利用率越高,效率也越高。
  常用的哈希函數有:直接定址法除留餘數法數字分析法平方取中法折疊法隨機數法 等等。有關哈希函數的內容,下文會進行詳細講解。

6、哈希沖突

  哈希函數在生成 哈希值 的過程中,如果產生 不同的關鍵字得到相同的哈希值 的情況,就被稱為 哈希沖突
  即對於哈希函數y=f(x),當關鍵字 x1≠x2 ,但是卻有f(x1​)=f(x2​),這時候,我們需要進行沖突解決。
  沖突解決方法有很多,主要有:開放定址法再散列函數法鏈地址法公共溢出區法 等等。有關解決沖突的內容,下文會進行詳細講解。

7、哈希地址

  哈希地址 就是一個 數組下標 ,即哈希數組的下標。通過下標獲得數據,被稱為 索引。通過數據獲得下標,被稱為 哈希。平時工作的時候,和同事交流時用到的一個詞 反查 就是說的 哈希

二、常用哈希函數

1、直接定址法

  直接定址法 就是 關鍵字 本身就是 哈希值,表示成函數值就是

f(x)=x

  例如,我們需要統計一個字符串中每個字符的出現次數,就可以通過這種方法。任何一個字符的范圍都是 [0,255],所以隻要用一個長度為 256 的哈希數組就可以存儲每個字符對應的出現次數,利用一次遍歷枚舉就可以解決這個問題。C代碼實現如下:

int i, hash[256];
for(i = 0; str[i]; ++i) {
    ++hash[ str[i] ];
}

  這個就是最基礎的直接定址法的實現。hash[c]代表字符c在這個字符串str中的出現次數。

2、平方取中法

  平方取中法 就是對 關鍵字 進行平方,再取中間的某幾位作為 哈希值
  例如,對於關鍵字 1314,得到平方為1726596,取中間三位作為哈希值,即265。
  平方取中法 比較適用於 不清楚關鍵字的分佈,且位數也不是很大 的情況。

3、折疊法

  折疊法 是將關鍵字分割成位數相等的幾部分(註意最後一部分位數不夠可以短一些),然後再進行求和,得到一個 哈希值
  例如,對於關鍵字 5201314,將它分為四組,並且相加得到:52+01+31+4=88,這就是哈希值。
  折疊法 比較適用於 不清楚關鍵字的分佈,但是關鍵字位數較多 的情況。

4、除留餘數法

  除留餘數法 就是 關鍵字 模上 哈希表 長度,表示成函數值就是

f(x)=x mod m

  其中 m 代表瞭哈希表的長度,這種方法,不僅可以對關鍵字直接取模,也可以在 平方取中法、折疊法 之後再取模。
  例如,對於一個長度為 4 的哈希數組,我們可以將關鍵字 模 4 得到哈希值,如圖所示:

5、位與法

  哈希數組的長度一般選擇 2 的冪,因為我們知道取模運算是比較耗時的,而位運算相對較為高效。
  選擇 2 的冪作為數組長度,可以將 取模運算 轉換成 二進制位與。
  令 m = 2^k,那麼它的二進制表示就是:

,任何一個數模上 m,就相當於取瞭 m  的二進制低 k 位,而

 

,所以和 位與m−1 的效果是一樣的。即:

  除瞭直接定址法,其它三種方法都有可能導致哈希沖突,接下來,我們就來討論下常用的一些哈希沖突的解決方案。

三、常見哈希沖突解決方案

1、開放定址法

1)原理講解

  開放定址法 就是一旦發生沖突,就去尋找下一個空的地址,隻要哈希表足夠大,總能找到一個空的位置,並且記錄下來作為它的 哈希地址。公式如下:

  這裡的di​ 是一個數列,可以是常數列(1,1,1,…,1),也可以是等差數列(1,2,3,…,m−1)。

2)動畫演示

  上圖中,采用的是哈希函數算法是 除留餘數法,采用的哈希沖突解決方案是 開放定址法,哈希表的每個數據就是一個關鍵字,插入之前需要先進行查找,如果找到的位置未被插入,則執行插入;否則,找到下一個未被插入的位置進行插入;總共插入瞭 6 個數據,分別為:11、12、13、20、19、28。
  這種方法需要註意的是,當插入數據超過哈希表長度時,不能再執行插入。

  本文在第四章講解 哈希表的現實 時采用的就是常數列的開放定址法。

2、再散列函數法

1)原理講解

  再散列函數法 就是一旦發生沖突,就采用另一個哈希函數,可以是 平方取中法、折疊法、除留餘數法 等等的組合,一般用兩個哈希函數,產生沖突的概率已經微乎其微瞭。
  再散列函數法 能夠使關鍵字不產生聚集,當然,也會增加不少哈希函數的計算時間。

2)動畫演示

待補充

3、鏈地址法

1)原理講解

  當然,產生沖突後,我們也可以選擇不換位置,還是在原來的位置,隻是把 哈希值 相同的用鏈表串聯起來。這種方法被稱為 鏈地址法

2)動畫演示

  上圖中,采用的是哈希函數算法是 除留餘數法,采用的哈希沖突解決方案是 鏈地址法,哈希表的每個數據保留瞭一個 鏈表頭結點尾結點,插入之前需要先進行查找,如果找到的位置,鏈表非空,則插入尾結點並且更新尾結點;否則,生成一個新的鏈表頭結點和尾結點;總共插入瞭 6 個數據,分別為:11、12、13、20、19、28。

4、公共溢出區法

1)原理講解

  一旦產生沖突的數據,統一放到另外一個順序表中,每次查找數據,在哈希數組中到的關鍵字和給定關鍵字相等,則認為查找成功;否則,就去公共溢出區順序查找,這種方法被稱為 公共溢出區法
  這種方法適合沖突較少的情況。

2)動畫演示

待補充

四、哈希表的實現

1、數據結構定義

  由於哈希表的底層存儲還是數組,所以我們可以定義一個結構體,結構體中定義一個數組類型的成員,如果需要記錄哈希表元素的個數,還可以記錄一個 size字段。
  C語言實現如下:

#define maxn (1<<17)          // (1)
#define mask (maxn-1)         // (2)
#define DataType int          // (3)
#define Boolean int           // (4)
#define NULLKEY (maxn+2)      // (5)
typedef struct {
    DataType data[maxn];
}HashTable;

(1) 利用位運算計算哈希函數進行加速,哈希表的長度為 2 的冪;

(2) 利用上文提到的 位與法 作為哈希函數,進行位與的掩碼必須是二進制表示都是1的,所以等於 2 的冪減一;

(3) 定義關鍵字類型為整型int

(4) 定義一個佈爾變量類型;

(5) NULLKEY作為哈希表對應位置為空時的標記,必須是一個非關鍵字能取到的值;

2、哈希表初始化

  哈希表初始化要做的事情,就是把哈希表的每個位置都置空。C語言代碼實現如下:

void HashInit(HashTable *ht) {
    int i;
    for(i = 0; i < maxn; ++i) {
        ht->data[i] = NULLKEY;      // (1)
    }
}
  • (1) 將哈希表的每個位置都置空;

3、哈希函數計算

  哈希函數計算采用 除留餘數法 的優化版本 位與法。C語言代碼實現如下:

int HashGetAddr(DataType key) {
    return key & mask;
}

4、哈希表查找

  查找需要采用和插入時相同的哈希沖突方案,即開放尋址法。C語言代碼實現如下:

Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
    int startaddr = HashGetAddr(key);    // (1)
    *addr = startaddr;                   // (2)
    while(ht->data[*addr] != key) {      // (3)
        *addr = HashGetAddr(*addr + 1);  // (4)
        if(ht->data[*addr] == NULLKEY)   // (5)
            return 0;                     
        if(*addr == startaddr)           // (6)
            return 0;                    
    }
    return 1;                            // (7)
}

(1) 根據 哈希函數HashGetAddr計算得到一個哈希值startaddr

(2) addr是需要作為返回值的,所以要用解引用;

(3) 在哈希表的addr對應查找,如果不是空位,則繼續(4);否則,跳出循環;

(4) 往後找一個位置;

(5) 如果發現一個空位,說明這個關鍵字在哈希表中沒有對應數據,直接返回 0,代表查找失敗;

(6) 代表整個 哈希表 都已經遍歷完畢,都沒有找到合適的關鍵字,直接返回 0,代表查找失敗;

(7) 否則,返回 1 代表查找成功;

5、哈希表插入

  哈希沖突時(即當沒有合適位置),就找下一相鄰位置,即尋址數列為常數列 (1,1,1,…,1)。插入需要註意當哈希表慢時,不能再執行插入操作。C語言代碼實現如下:

int HashInsert(HashTable *ht, DataType key) {
    int addr = HashGetAddr(key);               // (1)
    int retaddr;
    if ( HashSearchKey(ht, key, &retaddr ) ) { // (2)
        return retaddr;
    } 
    while(ht->data[addr] != NULLKEY)           // (3)
        addr = HashGetAddr(addr + 1);          // (4)
    ht->data[addr] = key;                      // (5)
    return addr;                               // (6)
}

 (1) 根據 哈希函數HashGetAddr計算得到一個哈希值addr

(2) 插入前需要先查找是否存在,如果已經存在,則不執行插入;

(3) 在哈希表的addr對應查找,如果不是空位,則繼續 (3);否則,跳出循環;

(4) 往後找一個位置,繼續判斷是否為空; 

(5) 跳出循環則代表當前哈希表的addr位置沒有其它元素占據,則可以作為當前key的位置進行插入;

(6) 返回addr作為key的哈希地址;

6、哈希表刪除

  有瞭查找的基礎,刪除操作就比較簡單瞭,如果不能找到一個關鍵字的位置,則不對哈希表進行任何操作,返回空關鍵字;否則,將找到的位置賦為空關鍵字,並且返回刪除的位置;

int HashRemove(HashTable *ht, DataType key) {
    int addr;
    if ( !HashSearchKey(ht, key, &addr ) ) {     // (1)
        return NULLKEY;
    } 
    ht->data[addr] = NULLKEY;                    // (2)
    return addr;
}

 (1) 首先執行查找;

(2) 對找到的位置,將找到位置關鍵字清空;

7、哈希表完整實現

  最後,給出一個 開放定址法 的哈希表的完整實現,如下:

/******************** 哈希表 開放定址法 ********************/
#define maxn (1<<17)
#define mask (maxn-1)
#define DataType int
#define Boolean int
#define NULLKEY (1<<30)

typedef struct {
    DataType data[maxn];
}HashTable;

void HashInit(HashTable *ht) {
    int i;
    for(i = 0; i < maxn; ++i) {
        ht->data[i] = NULLKEY;
    }
}

int HashGetAddr(DataType key) {
    return key & mask; 
}

Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
    int startaddr = HashGetAddr(key);
    *addr = startaddr;
    while(ht->data[*addr] != key) {
        *addr = HashGetAddr(*addr + 1);
        if(ht->data[*addr] == NULLKEY) {
            return 0;
        }
        if(*addr == startaddr) {
            return 0;
        }
    }
    return 1;
}

int HashInsert(HashTable *ht, DataType key) {
    int addr = HashGetAddr(key);
    int retaddr;
    if ( HashSearchKey(ht, key, &retaddr ) ) {
        return retaddr;
    } 
    while(ht->data[addr] != NULLKEY)
        addr = HashGetAddr(addr + 1);
    ht->data[addr] = key;
    return addr;
}

int HashRemove(HashTable *ht, DataType key) {
    int addr;
    if ( !HashSearchKey(ht, key, &addr ) ) {
        return NULLKEY;
    } 
    ht->data[addr] = NULLKEY;
    return addr;
}

/******************** 哈希表 開放定址法 ********************/

到此這篇關於簡單講解哈希表的文章就介紹到這瞭,更多相關哈希表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: