跳转至

哈希表

引入

哈希表又稱散列表，一種以「key-value」形式存儲數據的數據結構。所謂以「key-value」形式存儲數據，是指任意的鍵值 key 都唯一對應到內存中的某個位置。只需要輸入查找的鍵值，就可以快速地找到其對應的 value。可以把哈希表理解為一種高級的數組，這種數組的下標可以是很大的整數，浮點數，字符串甚至結構體。

哈希函數

要讓鍵值對應到內存中的位置，就要為鍵值計算索引，也就是計算這個數據應該放到哪裏。這個根據鍵值計算索引的函數就叫做哈希函數，也稱散列函數。舉個例子，如果鍵值是一個人的身份證號碼，哈希函數就可以是號碼的後四位，當然也可以是號碼的前四位。生活中常用的「手機尾號」也是一種哈希函數。在實際的應用中，鍵值可能是更復雜的東西，比如浮點數、字符串、結構體等，這時候就要根據具體情況設計合適的哈希函數。哈希函數應當易於計算，並且儘量使計算出來的索引均勻分佈。

能為 key 計算索引之後，我們就可以知道每個鍵值對應的值 value 應該放在哪裏了。假設我們用數組 a 存放數據，哈希函數是 f，那鍵值對 (key, value) 就應該放在 a[f(key)] 上。不論鍵值是什麼類型，範圍有多大，f(key) 都是在可接受範圍內的整數，可以作為數組的下標。

在 OI 中，最常見的情況應該是鍵值為整數的情況。當鍵值的範圍比較小的時候，可以直接把鍵值作為數組的下標，但當鍵值的範圍比較大，比如以 \(10^9\) 範圍內的整數作為鍵值的時候，就需要用到哈希表。一般把鍵值模一個較大的質數作為索引，也就是取 \(f(x)=x \bmod M\) 作為哈希函數。

另一種比較常見的情況是 key 為字符串的情況，由於不支持以字符串作為數組下標，並且將字符串轉化成數字存儲也可以避免多次進行字符串比較。所以在 OI 中，一般不直接把字符串作為鍵值，而是先算出字符串的哈希值，再把其哈希值作為鍵值插入到哈希表裏。關於字符串的哈希值，我們一般採用進制的思想，將字符串想象成一個 \(127\) 進制的數。那麼，對於每一個長度為 \(n\) 的字符串 \(s\)，就有：

\(x = s_0 \cdot 127^0 + s_1 \cdot 127^1 + s_2 \cdot 127^2 + \dots + s_n \cdot 127^n\)

我們可以將得到的 \(x\) 對 \(2^{64}\)（即 unsigned long long 的最大值）取模。這樣 unsigned long long 的自然溢出就等價於取模操作了。可以使操作更加方便。

這種方法雖然簡單，但並不是完美的。可以構造數據使這種方法發生衝突（即兩個字符串的 \(x\) 對 \(2^{64}\) 取模後的結果相同）。
我們可以使用雙哈希的方法：選取兩個大質數 \(a,b\)。當且僅當兩個字符串的哈希值對 \(a\) 和對 \(b\) 取模都相等時，我們才認為這兩個字符串相等。這樣可以大大降低哈希衝突的概率。

衝突

如果對於任意的鍵值，哈希函數計算出來的索引都不相同，那隻用根據索引把 (key, value) 放到對應的位置就行了。但實際上，常常會出現兩個不同的鍵值，他們用哈希函數計算出來的索引是相同的。這時候就需要一些方法來處理衝突。在 OI 中，最常用的方法是拉鍊法。

拉鍊法

拉鍊法也稱開散列法（open hashing）。

拉鍊法是在每個存放數據的地方開一個鏈表，如果有多個鍵值索引到同一個地方，只用把他們都放到那個位置的鏈表裏就行了。查詢的時候需要把對應位置的鏈表整個掃一遍，對其中的每個數據比較其鍵值與查詢的鍵值是否一致。如果索引的範圍是 \(1\ldots M\)，哈希表的大小為 \(N\)，那麼一次插入/查詢需要進行期望 \(O(\frac{N}{M})\) 次比較。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int SIZE = 1000000;
const int M = 999997;

struct HashTable {
  struct Node {
    int next, value, key;
  } data[SIZE];

  int head[M], size;

  int f(int key) { return (key % M + M) % M; }

  int get(int key) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value;
    return -1;
  }

  int modify(int key, int value) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value = value;
  }

  int add(int key, int value) {
    if (get(key) != -1) return -1;
    data[++size] = (Node){head[f(key)], value, key};
    head[f(key)] = size;
    return value;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
M = 999997
SIZE = 1000000
class Node:
    def __init__(self, next = None, value = None, key = None): 
        self.next = next
        self.value = value
        self.key = key
data = [Node() for _ in range(SIZE)]
head = [0] * M
size = 0
def f(key):
    return key % M
def get(key):
    p = head[f(key)]
    while p:
        if data[p].key == key:
            return data[p].value
        p = data[p].next
    return -1
def modify(key, value):
    p = head[f(key)]
    while p:
        if data[p].key == key:
            data[p].value = value
            return data[p].value
        p = data[p].next
def add(key, value):
    if get(key) != -1:
        return -1
    size = size + 1
    data[size] = Node(head[f(key)], value, key)
    head[f(key)] = size
    return value

這裏再提供一個封裝過的模板，可以像 map 一樣用，並且較短

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct hash_map {  // 哈希表模板

  struct data {
    long long u;
    int v, nex;
  };  // 前向星結構

  data e[SZ << 1];  // SZ 是 const int 表示大小
  int h[SZ], cnt;

  int hash(long long u) { return (u % SZ + SZ) % SZ; }

  // 這裏使用 (u % SZ + SZ) % SZ 而非 u % SZ 的原因是
  // C++ 中的 % 運算無法將負數轉為正數

  int& operator[](long long u) {
    int hu = hash(u);  // 獲取頭指針
    for (int i = h[hu]; i; i = e[i].nex)
      if (e[i].u == u) return e[i].v;
    return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
    cnt = 0;
    memset(h, 0, sizeof(h));
  }
};

在這裏，hash 函數是針對鍵值的類型設計的，並且返回一個鏈表頭指針用於查詢。在這個模板中我們寫了一個鍵值對類型為 (long long, int) 的 hash 表，並且在查詢不存在的鍵值時返回 -1。函數 hash_map() 用於在定義時初始化。

閉散列法

閉散列方法把所有記錄直接存儲在散列表中，如果發生衝突則根據某種方式繼續進行探查。

比如線性探查法：如果在 d 處發生衝突，就依次檢查 d + 1，d + 2……

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 360007;  // N 是最大可以存儲的元素數量

class Hash {
 private:
  int keys[N];
  int values[N];

 public:
  Hash() { memset(values, 0, sizeof(values)); }

  int& operator[](int n) {
    // 返回一個指向對應 Hash[Key] 的引用
    // 修改成不為 0 的值 0 時候視為空
    int idx = (n % N + N) % N, cnt = 1;
    while (keys[idx] != n && values[idx] != 0) {
      idx = (idx + cnt * cnt) % N;
      cnt += 1;
    }
    keys[idx] = n;
    return values[idx];
  }
};

例題

「JLOI2011」不重複數字

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用