哈希表

「哈希表 hash table」，又称「散列表」，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 $O(1)$ 时间内获取对应的值 value 。

如下图所示，给定 $n$ 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用下图所示的哈希表来实现。

哈希表的抽象表示

除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下表所示。

添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 $O(1)$ 时间。
查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 $O(n)$ 时间。
删除元素：需要先查询到元素，再从数组（链表）中删除，使用 $O(n)$ 时间。

表元素查询效率对比

	数组	链表	哈希表
查找元素	$O(n)$	$O(n)$	$O(1)$
添加元素	$O(1)$	$O(1)$	$O(1)$
删除元素	$O(n)$	$O(n)$	$O(1)$

观察发现，在哈希表中进行增删查改的时间复杂度都是 $O(1)$ ，非常高效。

哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等，示例代码如下：

"Python"

```python title="hash_map.py" // 初始化哈希表 hmap: dict = {}

// 添加操作 // 在哈希表中添加键值对 (key, value) hmap[12836] = "小哈" hmap[15937] = "小啰" hmap[16750] = "小算" hmap[13276] = "小法" hmap[10583] = "小鸭"

// 查询操作 // 向哈希表中输入键 key ，得到值 value name: str = hmap[15937]

// 删除操作 // 在哈希表中删除键值对 (key, value) hmap.pop(10583) ```
"C++"

```cpp title="hash_map.cpp" / 初始化哈希表 / unordered_map map;

/ 添加操作 / // 在哈希表中添加键值对 (key, value) map[12836] = "小哈"; map[15937] = "小啰"; map[16750] = "小算"; map[13276] = "小法"; map[10583] = "小鸭";

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value string name = map[15937];

/ 删除操作 / // 在哈希表中删除键值对 (key, value) map.erase(10583); ```
"Java"

```java title="hash_map.java" / 初始化哈希表 / Map map = new HashMap<>();

/ 添加操作 / // 在哈希表中添加键值对 (key, value) map.put(12836, "小哈");

map.put(15937, "小啰");

map.put(16750, "小算");

map.put(13276, "小法"); map.put(10583, "小鸭");

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value String name = map.get(15937);

/ 删除操作 / // 在哈希表中删除键值对 (key, value) map.remove(10583); ```
"C#"

```csharp title="hash_map.cs" / 初始化哈希表 / Dictionary map = new() {
```
  /* 添加操作 */
  // 在哈希表中添加键值对 (key, value)
  { 12836, "小哈" },
  { 15937, "小啰" },
  { 16750, "小算" },
  { 13276, "小法" },
  { 10583, "小鸭" }
```
};

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value string name = map[15937];

/ 删除操作 / // 在哈希表中删除键值对 (key, value) map.Remove(10583); ```
"Go"

```go title="hash_map_test.go" / 初始化哈希表 / hmap := make(map[int]string)

/ 添加操作 / // 在哈希表中添加键值对 (key, value) hmap[12836] = "小哈" hmap[15937] = "小啰" hmap[16750] = "小算" hmap[13276] = "小法" hmap[10583] = "小鸭"

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value name := hmap[15937]

/ 删除操作 / // 在哈希表中删除键值对 (key, value) delete(hmap, 10583) ```
"Swift"

```swift title="hash_map.swift" / 初始化哈希表 / var map: [Int: String] = [:]

/ 添加操作 / // 在哈希表中添加键值对 (key, value) map[12836] = "小哈" map[15937] = "小啰" map[16750] = "小算" map[13276] = "小法" map[10583] = "小鸭"

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value let name = map[15937]!

/ 删除操作 / // 在哈希表中删除键值对 (key, value) map.removeValue(forKey: 10583) ```
"JS"

```javascript title="hash_map.js" / 初始化哈希表 / const map = new Map(); / 添加操作 / // 在哈希表中添加键值对 (key, value) map.set(12836, '小哈'); map.set(15937, '小啰'); map.set(16750, '小算'); map.set(13276, '小法'); map.set(10583, '小鸭');

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value let name = map.get(15937);

/ 删除操作 / // 在哈希表中删除键值对 (key, value) map.delete(10583); ```
"TS"

```typescript title="hash_map.ts" / 初始化哈希表 / const map = new Map(); / 添加操作 / // 在哈希表中添加键值对 (key, value) map.set(12836, '小哈'); map.set(15937, '小啰'); map.set(16750, '小算'); map.set(13276, '小法'); map.set(10583, '小鸭'); console.info('\n添加完成后，哈希表为\nKey -> Value'); console.info(map);

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value let name = map.get(15937); console.info('\n输入学号 15937 ，查询到姓名 ' + name);

/ 删除操作 / // 在哈希表中删除键值对 (key, value) map.delete(10583); console.info('\n删除 10583 后，哈希表为\nKey -> Value'); console.info(map); ```
"Dart"

```dart title="hash_map.dart" / 初始化哈希表 / Map map = {};

/ 添加操作 / // 在哈希表中添加键值对 (key, value) map[12836] = "小哈"; map[15937] = "小啰"; map[16750] = "小算"; map[13276] = "小法"; map[10583] = "小鸭";

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value String name = map[15937];

/ 删除操作 / // 在哈希表中删除键值对 (key, value) map.remove(10583); ```
"Rust"

```rust title="hash_map.rs" use std::collections::HashMap;

/ 初始化哈希表 / let mut map: HashMap = HashMap::new();

/ 添加操作 / // 在哈希表中添加键值对 (key, value) map.insert(12836, "小哈".to_string()); map.insert(15937, "小啰".to_string()); map.insert(16750, "小算".to_string()); map.insert(13279, "小法".to_string()); map.insert(10583, "小鸭".to_string());

/ 查询操作 / // 向哈希表中输入键 key ，得到值 value let _name: Option<&String> = map.get(&15937);

/ 删除操作 / // 在哈希表中删除键值对 (key, value) let _removed_value: Option = map.remove(&10583); ```
"C"

c title="hash_map.c" // C 未提供内置哈希表
"Zig"

```zig title="hash_map.zig"

```

哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值。示例代码如下：

"Python"

```python title="hash_map.py" // 遍历哈希表 // 遍历键值对 key->value for key, value in hmap.items():
```
  print(key, "->", value)
```
// 单独遍历键 key for key in hmap.keys():
```
  print(key)
```
// 单独遍历值 value for value in hmap.values():
```
  print(value)
```
```
"C++"

```cpp title="hash_map.cpp" / 遍历哈希表 / // 遍历键值对 key->value for (auto kv: map) {
```
  cout << kv.first << " -> " << kv.second << endl;
```
} // 使用迭代器遍历 key->value for (auto iter = map.begin(); iter != map.end(); iter++) {
```
  cout << iter->first << "->" << iter->second << endl;
```
} ```
"Java"

```java title="hash_map.java" / 遍历哈希表 / // 遍历键值对 key->value for (Map.Entry kv: map.entrySet()) {
```
  System.out.println(kv.getKey() + " -> " + kv.getValue());
```
} // 单独遍历键 key for (int key: map.keySet()) {
```
  System.out.println(key);
```
} // 单独遍历值 value for (String val: map.values()) {
```
  System.out.println(val);
```
} ```
"C#"

```csharp title="hash_map.cs" / 遍历哈希表 / // 遍历键值对 Key->Value foreach (var kv in map) {
```
  Console.WriteLine(kv.Key + " -> " + kv.Value);
```
} // 单独遍历键 key foreach (int key in map.Keys) {
```
  Console.WriteLine(key);
```
} // 单独遍历值 value foreach (string val in map.Values) {
```
  Console.WriteLine(val);
```
} ```
"Go"

```go title="hash_map_test.go" / 遍历哈希表 / // 遍历键值对 key->value for key, value := range hmap {
```
  fmt.Println(key, "->", value)
```
} // 单独遍历键 key for key := range hmap {
```
  fmt.Println(key)
```
} // 单独遍历值 value for _, value := range hmap {
```
  fmt.Println(value)
```
} ```
"Swift"

```swift title="hash_map.swift" / 遍历哈希表 / // 遍历键值对 Key->Value for (key, value) in map {
```
  print("\(key) -> \(value)")
```
} // 单独遍历键 Key for key in map.keys {
```
  print(key)
```
} // 单独遍历值 Value for value in map.values {
```
  print(value)
```
} ```
"JS"

```javascript title="hash_map.js" / 遍历哈希表 / console.info('\n遍历键值对 Key->Value'); for (const [k, v] of map.entries()) {
```
  console.info(k + ' -> ' + v);
```
} console.info('\n单独遍历键 Key'); for (const k of map.keys()) {
```
  console.info(k);
```
} console.info('\n单独遍历值 Value'); for (const v of map.values()) {
```
  console.info(v);
```
} ```
"TS"

```typescript title="hash_map.ts" / 遍历哈希表 / console.info('\n遍历键值对 Key->Value'); for (const [k, v] of map.entries()) {
```
  console.info(k + ' -> ' + v);
```
} console.info('\n单独遍历键 Key'); for (const k of map.keys()) {
```
  console.info(k);
```
} console.info('\n单独遍历值 Value'); for (const v of map.values()) {
```
  console.info(v);
```
} ```
"Dart"

```dart title="hash_map.dart" / 遍历哈希表 / // 遍历键值对 Key->Value map.forEach((key, value) {
```
print('$key -> $value');
```
});

// 单独遍历键 Key map.keys.forEach((key) {
```
print(key);
```
});

// 单独遍历值 Value map.values.forEach((value) {
```
print(value);
```
}); ```
"Rust"

```rust title="hash_map.rs" / 遍历哈希表 / // 遍历键值对 Key->Value for (key, value) in &map {
```
  println!("{key} -> {value}");
```
}

// 单独遍历键 Key for key in map.keys() {
```
  println!("{key}"); 
```
}

// 单独遍历值 Value for value in map.values() {
```
  println!("{value}");
```
} ```
"C"

c title="hash_map.c" // C 未提供内置哈希表
"Zig"

```zig title="hash_map.zig"

```

哈希表简单实现

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为「桶 bucket」，每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 定位对应的桶呢？这是通过「哈希函数 hash function」实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步。

通过某种哈希算法 hash() 计算得到哈希值。
将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。

index = hash(key) % capacity

随后，我们就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。

设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100 。下图以 key 学号和 value 姓名为例，展示了哈希函数的工作原理。

哈希函数工作原理

以下代码实现了一个简单哈希表。其中，我们将 key 和 value 封装成一个类 Pair ，以表示键值对。

"Python" ```python class Pair: """键值对"""

def init(self, key: int, val: str):
```
  self.key = key
  self.val = val
```

class ArrayHashMap: """基于数组实现的哈希表"""

def __init__(self):
    """构造方法"""
   // 初始化数组，包含 100 个桶
    self.buckets: list[Pair | None] = [None] * 100

def hash_func(self, key: int) -> int:
    """哈希函数"""
    index = key % 100
    return index

def get(self, key: int) -> str:
    """查询操作"""
    index: int = self.hash_func(key)
    pair: Pair = self.buckets[index]
    if pair is None:
        return None
    return pair.val

def put(self, key: int, val: str):
    """添加操作"""
    pair = Pair(key, val)
    index: int = self.hash_func(key)
    self.buckets[index] = pair

def remove(self, key: int):
    """删除操作"""
    index: int = self.hash_func(key)
   // 置为 None ，代表删除
    self.buckets[index] = None

def entry_set(self) -> list[Pair]:
    """获取所有键值对"""
    result: list[Pair] = []
    for pair in self.buckets:
        if pair is not None:
            result.append(pair)
    return result

def key_set(self) -> list[int]:
    """获取所有键"""
    result = []
    for pair in self.buckets:
        if pair is not None:
            result.append(pair.key)
    return result

def value_set(self) -> list[str]:
    """获取所有值"""
    result = []
    for pair in self.buckets:
        if pair is not None:
            result.append(pair.val)
    return result

def print(self):
    """打印哈希表"""
    for pair in self.buckets:
        if pair is not None:
            print(pair.key, "->", pair.val)


- "C++"
```cpp
/* 键值对 */
struct Pair {
  public:
    int key;
    string val;
    Pair(int key, string val) {
        this->key = key;
        this->val = val;
    }
};

/* 基于数组实现的哈希表 */
class ArrayHashMap {
  private:
    vector<Pair *> buckets;

  public:
    ArrayHashMap() {
        // 初始化数组，包含 100 个桶
        buckets = vector<Pair *>(100);
    }

    ~ArrayHashMap() {
        // 释放内存
        for (const auto &bucket : buckets) {
            delete bucket;
        }
        buckets.clear();
    }

    /* 哈希函数 */
    int hashFunc(int key) {
        int index = key % 100;
        return index;
    }

    /* 查询操作 */
    string get(int key) {
        int index = hashFunc(key);
        Pair *pair = buckets[index];
        if (pair == nullptr)
            return "";
        return pair->val;
    }

    /* 添加操作 */
    void put(int key, string val) {
        Pair *pair = new Pair(key, val);
        int index = hashFunc(key);
        buckets[index] = pair;
    }

    /* 删除操作 */
    void remove(int key) {
        int index = hashFunc(key);
        // 释放内存并置为 nullptr
        delete buckets[index];
        buckets[index] = nullptr;
    }

    /* 获取所有键值对 */
    vector<Pair *> pairSet() {
        vector<Pair *> pairSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                pairSet.push_back(pair);
            }
        }
        return pairSet;
    }

    /* 获取所有键 */
    vector<int> keySet() {
        vector<int> keySet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                keySet.push_back(pair->key);
            }
        }
        return keySet;
    }

    /* 获取所有值 */
    vector<string> valueSet() {
        vector<string> valueSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                valueSet.push_back(pair->val);
            }
        }
        return valueSet;
    }

    /* 打印哈希表 */
    void print() {
        for (Pair *kv : pairSet()) {
            cout << kv->key << " -> " << kv->val << endl;
        }
    }
};

"Java" ```java / 键值对 / class Pair { public int key; public String val;

public Pair(int key, String val) {
```
  this.key = key;
  this.val = val;
```
} }

/ 基于数组实现的哈希表 / class ArrayHashMap { private List buckets;

public ArrayHashMap() {
    // 初始化数组，包含 100 个桶
    buckets = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        buckets.add(null);
    }
}

/* 哈希函数 */
private int hashFunc(int key) {
    int index = key % 100;
    return index;
}

/* 查询操作 */
public String get(int key) {
    int index = hashFunc(key);
    Pair pair = buckets.get(index);
    if (pair == null)
        return null;
    return pair.val;
}

/* 添加操作 */
public void put(int key, String val) {
    Pair pair = new Pair(key, val);
    int index = hashFunc(key);
    buckets.set(index, pair);
}

/* 删除操作 */
public void remove(int key) {
    int index = hashFunc(key);
    // 置为 null ，代表删除
    buckets.set(index, null);
}

/* 获取所有键值对 */
public List<Pair> pairSet() {
    List<Pair> pairSet = new ArrayList<>();
    for (Pair pair : buckets) {
        if (pair != null)
            pairSet.add(pair);
    }
    return pairSet;
}

/* 获取所有键 */
public List<Integer> keySet() {
    List<Integer> keySet = new ArrayList<>();
    for (Pair pair : buckets) {
        if (pair != null)
            keySet.add(pair.key);
    }
    return keySet;
}

/* 获取所有值 */
public List<String> valueSet() {
    List<String> valueSet = new ArrayList<>();
    for (Pair pair : buckets) {
        if (pair != null)
            valueSet.add(pair.val);
    }
    return valueSet;
}

/* 打印哈希表 */
public void print() {
    for (Pair kv : pairSet()) {
        System.out.println(kv.key + " -> " + kv.val);
    }
}

}


## 哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 `key` 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，**理论上一定存在“多个输入对应相同输出”的情况**。

对于上述示例中的哈希函数，当输入的 `key` 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，我们得到：

```shell
12836 % 100 = 36
20336 % 100 = 36

如下图所示，两个学号指向了同一个姓名，这显然是不对的。我们将这种多个输入对应同一输出的情况称为「哈希冲突 hash collision」。

哈希冲突示例

容易想到，哈希表容量 $n$ 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

如下图所示，扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失。

哈希表扩容

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 $0.75$ 时，系统会将哈希表扩容至原先的 $2$ 倍。