【大模型2609·数据结构算法·05】快速检索神器：哈希表底层原理与冲突解决策略

专栏导读：实现 O(1) 理论常数级检索的核心神器。本篇深度解构哈希表（Hash Table）键值映射模型与哈希函数构造方法；系统攻克哈希冲突的两大业界主流解法（链式地址法与开放寻址法），手写实现具备动态重哈希能力的工业级哈希表类。

哈希表

哈希表的概述

哈希表（Hash Table，也叫散列表），由一系列键值对（key-value pairs）组成，并且可以通过键（key）查找对应的值（value）。哈希表通过建立key与value之间的映射，实现高效的查询，我们向哈希表中输入一个key，可以在O(1)的时间内获取对应的value。

例如通过客户id获取客户姓名：

image12.png

哈希表常见的一个操作是根据key来查找value，考虑到数组查询效率最高，选择基于数组实现哈希表。利用哈希函数计算key的哈希值，然后将哈希值映射到数组索引。在实现过程中我们可能会遇到如下问题：

如何将一个个key映射到数组的索引？

如果多个key映射到数组同一个索引怎么办？

数组长度是固定的，如果后续元素过多，大于数组长度怎么办？

哈希函数

哈希表的核心组件是哈希函数。该函数将key转换为一个数组索引。哈希函数的目标是尽量均匀地将所有可能的key分布到表的不同位置，以减少冲突的发生。

哈希函数的执行步骤分为两步：

通过某种哈希算法计算出key的哈希值。

哈希值对数组长度取余，获取key对应的数组索引。

index = hash(key) % capacity

例如我们使用一个简单的哈希算法 hash(key)=key 将客户id映射到一个长度为8的数组的索引，即 index = key % 8 。

image13.png

常见的哈希算法：

通用哈希算法：除法哈希、乘法哈希、MurmurHash、CityHash。

加密哈希算法：MD5（已被成功攻击）、SHA-1（已被成功攻击）、SHA-2、SHA-3。

文件完整性检查算法：Adler-32、CRC32。

哈希冲突

哈希函数可能会将不同的键值映射到同一个索引位置，这就是所谓的哈希冲突。处理冲突的方式有多种，最常见的两种是链式法（Chaining）和开放寻址法（Open Addressing）。

链式法

将发生碰撞的每个键值对作为一个节点（Node）组成一个链表（Linked List），然后将链表的头节点保存在数组的目标位置中。这样一来，向字典中写入数据时，若发现数组的目标位置已有数据，那么就将当前的键值对作为一个节点插入链表；从字典中读取数据时，则从数组的目标位置获取链表，并进行遍历，直到找到目标数据。

image14.png

开放寻址法

当发生冲突时根据某种探查策略寻找下一个空槽位。常见的探查策略包括：

线性探查（Linear Probing）：如果当前位置已经被占用，就探查下一个位置。

二次探查（Quadratic Probing）：以平方的步长进行探查。

双重哈希（Double Hashing）：使用另一个哈希函数来计算新的索引。

负载因子

负载因子（Load Factor）是哈希表中元素个数与表的大小的比率。当负载因子过高时，可能需要进行扩容操作，以保持操作的效率。

较小的负载因子可以减少冲突的可能性，较大的负载因子可以提高哈希表的内存利用率。通常情况下负载因子在0.7~0.8是一个比较好的选择。

哈希表的功能定义

方法 说明
size() 返回哈希表中键值对个数
is_empty() 判断哈希表是否为空
put(key, value) 向哈希表插入键值对
remove(key) 从哈希表中根据键删除键值对
get(key) 从哈希表中根据键获取值
for_each(func) 遍历哈希表中的键值对

哈希表的实现

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashTable:

    def __init__(self):
        """初始化哈希表"""
        self.__capacity = 8  # 数组长度
        self.__size = 0  # 键值对个数
        self.__load_factor = 0.7  # 负载因子
        self.__table = [None] * self.__capacity

    def display(self):
        """显示哈希表内容"""
        for i, node in enumerate(self.__table):
            print(f"Index {i}: ", end="")
            current = node
            while current:
                print(f"({current.key}, {current.value}) -> ", end="")
                current = current.next
            print("None")
        print()

    def __hash(self, key):
        """哈希函数，根据key计算索引"""
        return hash(key) % self.__capacity

    def __grow(self):
        """哈希表负载因子超过阈值时进行扩容"""
        self.__capacity = self.__capacity * 2
        self.__table, old_table = [None] * self.__capacity, self.__table
        self.__size = 0

        # 将旧哈希表中的元素重新插入到新的哈希表中
        for node in old_table:
            current = node
            while current:
                self.put(current.key, current.value)
                current = current.next

    @property
    def size(self):
        """获取哈希表键值对个数"""
        return self.__size

    def is_empty(self):
        """判断哈希表是否为空"""
        return self.__size == 0

    def put(self, key, value):
        """插入键值对，处理哈希冲突"""
        # 如果负载因子超过阈值则进行扩容
        if self.__size / self.__capacity > self.__load_factor:
            self.__grow()

        index = self.__hash(key)
        new_node = Node(key, value)
        # 如果当前位置为空，直接插入
        if self.__table[index] is None:
            self.__table[index] = new_node
        else:
            # 否则，发生哈希冲突，链式存储
            current = self.__table[index]
            while current:
                # 如果键已经存在，更新值
                if current.key == key:
                    current.value = value
                    return
                if not current.next:
                    break
                current = current.next
            # 如果键不存在，插入到链表尾部
            current.next = new_node
        self.__size += 1

    def remove(self, key):
        """删除键值对"""
        index = self.__hash(key)
        current = self.__table[index]
        prev = None

        while current:
            if current.key == key:
                if prev:
                    # 删除非头节点
                    prev.next = current.next
                else:
                    # 删除头节点
                    self.__table[index] = current.next
                self.__size -= 1
                return True
            prev = current
            current = current.next
        return False

    def get(self, key):
        """访问键值对"""
        index = self.__hash(key)
        current = self.__table[index]
        while current:
            if current.key == key:
                return current.value
            current = current.next
        return None

    def for_each(self, func):
        """遍历哈希表"""
        for node in self.__table:
            current = node
            while current:
                func(current.key, current.value)
                current = current.next