跳转至

哈希表

提前建立目录,能省几次逐行寻找?

有一列号码和姓名。如果每次查号码都从头扫描,同一批记录会被重复比较。先把号码当作**键**、姓名当作对应的**值**。把键交给一条计算规则(哈希函数),就能算出数组里从哪一格找起。建立映射有成本,键增加和删除时也要维护;查找反复发生时,这笔成本更容易摊开。

从未查过、以后只查一次,值得先建索引吗?

先看数据规模和用途。只查一次时,线性扫描通常足够简单;需要多次查询时才更可能抵掉建表开销。

哈希表(hash table),又称散列表,它通过建立键 key 与值 value 之间的映射,实现高效的元素查询。具体而言,我们向哈希表中输入一个键 key ,在哈希函数将键分布得较均匀、表内仍留有足够空间时,查找对应的值 value 的期望时间为 \(O(1)\)(见时间复杂度)。

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

哈希表的抽象表示

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

  • 添加元素:这里只计末尾追加,不扫描重复键。动态数组偶尔扩容,长串追加平摊为 \(O(1)\);链表若保留尾指针,追加为 \(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)\),插入也可达到期望摊还 \(O(1)\)。若很多键集中在同一处,查询可能退化到 \(O(n)\),单次扩容也需要搬运已有记录。

哈希表常用操作

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

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)
hash_map.cpp
/* 初始化哈希表 */
unordered_map<int, string> map;

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

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

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);
hash_map.java
/* 初始化哈希表 */
Map<Integer, String> 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);
hash_map.cs
/* 初始化哈希表 */
Dictionary<int, string> map = new() {
    /* 添加操作 */
    // 在哈希表中添加键值对 (key, value)
    { 12836, "小哈" },
    { 15937, "小啰" },
    { 16750, "小算" },
    { 13276, "小法" },
    { 10583, "小鸭" }
};

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

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.Remove(10583);
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)
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)
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);
hash_map.ts
/* 初始化哈希表 */
const map = new Map<number, string>();
/* 添加操作 */
// 在哈希表中添加键值对 (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);
hash_map.dart
/* 初始化哈希表 */
Map<int, String> map = {};

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

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

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583);
hash_map.rs
use std::collections::HashMap;

/* 初始化哈希表 */
let mut map: HashMap<i32, String> = 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<String> = map.remove(&10583);
hash_map.c
// C 未提供内置哈希表
hash_map.kt
/* 初始化哈希表 */
val map = HashMap<Int,String>()

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

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

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583)
hash_map.rb
# 初始化哈希表
hmap = {}

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

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

# 删除操作
# 在哈希表中删除键值对 (key, value)
hmap.delete(10583)
hash_map.zig

可视化运行

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20hmap%20%3D%20%7B%7D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%B7%BB%E5%8A%A0%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E6%B7%BB%E5%8A%A0%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap%5B12836%5D%20%3D%20%22%E5%B0%8F%E5%93%88%22%0A%20%20%20%20hmap%5B15937%5D%20%3D%20%22%E5%B0%8F%E5%95%B0%22%0A%20%20%20%20hmap%5B16750%5D%20%3D%20%22%E5%B0%8F%E7%AE%97%22%0A%20%20%20%20hmap%5B13276%5D%20%3D%20%22%E5%B0%8F%E6%B3%95%22%0A%20%20%20%20hmap%5B10583%5D%20%3D%20%22%E5%B0%8F%E9%B8%AD%22%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%9F%A5%E8%AF%A2%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%90%91%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E8%BE%93%E5%85%A5%E9%94%AE%20key%20%EF%BC%8C%E5%BE%97%E5%88%B0%E5%80%BC%20value%0A%20%20%20%20name%20%3D%20hmap%5B15937%5D%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E5%88%A0%E9%99%A4%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap.pop%2810583%29&cumulative=false&curInstr=2&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

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

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)
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;
}
hash_map.java
/* 遍历哈希表 */
// 遍历键值对 key->value
for (Map.Entry <Integer, String> 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);
}
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);
}
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)
}
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)
}
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);
}
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);
}
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);
});
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}");
}
hash_map.c
// C 未提供内置哈希表
hash_map.kt
/* 遍历哈希表 */
// 遍历键值对 key->value
for ((key, value) in map) {
    println("$key -> $value")
}
// 单独遍历键 key
for (key in map.keys) {
    println(key)
}
// 单独遍历值 value
for (_val in map.values) {
    println(_val)
}
hash_map.rb
# 遍历哈希表
# 遍历键值对 key->value
hmap.entries.each { |key, value| puts "#{key} -> #{value}" }

# 单独遍历键 key
hmap.keys.each { |key| puts key }

# 单独遍历值 value
hmap.values.each { |val| puts val }
hash_map.zig

可视化运行

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20hmap%20%3D%20%7B%7D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%B7%BB%E5%8A%A0%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E6%B7%BB%E5%8A%A0%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap%5B12836%5D%20%3D%20%22%E5%B0%8F%E5%93%88%22%0A%20%20%20%20hmap%5B15937%5D%20%3D%20%22%E5%B0%8F%E5%95%B0%22%0A%20%20%20%20hmap%5B16750%5D%20%3D%20%22%E5%B0%8F%E7%AE%97%22%0A%20%20%20%20hmap%5B13276%5D%20%3D%20%22%E5%B0%8F%E6%B3%95%22%0A%20%20%20%20hmap%5B10583%5D%20%3D%20%22%E5%B0%8F%E9%B8%AD%22%0A%20%20%20%20%0A%20%20%20%20%23%20%E9%81%8D%E5%8E%86%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20%23%20%E9%81%8D%E5%8E%86%E9%94%AE%E5%80%BC%E5%AF%B9%20key-%3Evalue%0A%20%20%20%20for%20key,%20value%20in%20hmap.items%28%29%3A%0A%20%20%20%20%20%20%20%20print%28key,%20%22-%3E%22,%20value%29%0A%20%20%20%20%23%20%E5%8D%95%E7%8B%AC%E9%81%8D%E5%8E%86%E9%94%AE%20key%0A%20%20%20%20for%20key%20in%20hmap.keys%28%29%3A%0A%20%20%20%20%20%20%20%20print%28key%29%0A%20%20%20%20%23%20%E5%8D%95%E7%8B%AC%E9%81%8D%E5%8E%86%E5%80%BC%20value%0A%20%20%20%20for%20value%20in%20hmap.values%28%29%3A%0A%20%20%20%20%20%20%20%20print%28value%29&cumulative=false&curInstr=8&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

哈希表简单实现

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

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

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

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

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

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

哈希函数工作原理

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

array_hash_map.py
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 | None:
        """查询操作"""
        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)

哈希冲突与扩容

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

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

12836 % 100 = 36
20336 % 100 = 36

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

哈希冲突示例

如果哈希算法能把键近似均匀地分到各桶,记录数量不变时,多准备一些桶,撞在同一个桶里的概率就会下降。若两个键一开始就算出了相同的哈希值,即使增大容量也无法把这一对分开。因此,我们可以通过扩容哈希表来减少哈希冲突。

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

哈希表扩容

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

负载因子(load factor)是哈希表的一个重要概念,指记录数量除以桶数。例如 8 个桶中放了 6 条记录,负载因子就是 \(6/8=0.75\)。它反映表有多满或桶里平均有多少条记录,可用于决定何时扩容。想知道冲突是否集中,还要看记录的实际分布。