Mobile wallpaper 1Mobile wallpaper 2Mobile wallpaper 3Mobile wallpaper 4
Profile Image of the Author
千岛寒流
公告
欢迎来到我的博客.
标签
1918 字
10 分钟
深入理解哈希表：从原理到实现的完全指南
2025-05-12
数据结构
数据结构
/
哈希表
/
算法
/
Python

写在前面#

哈希表（Hash Table）是计算机科学中最重要的数据结构之一。它能在平均 O(1) 的时间复杂度内完成查找、插入和删除操作——比数组的 O(n) 遍历和二叉搜索树的 O(log n) 都要快得多。

本文将从零开始，用生活类比 + 图解 + 代码的方式，带你彻底理解哈希表的内部工作原理。

一、什么是哈希表？#

生活类比#

想象你去图书馆找一本《哈利·波特》：

  • 笨办法：从第一个书架开始，一本一本地翻，直到找到为止（O(n)）
  • 聪明办法：图书管理员根据书名的首字母，直接带你到 H 开头的书架区域（O(1)）

哈希表就是这个”聪明的图书管理员”——它通过一个哈希函数，把键（Key）直接转换成存储位置，省去了遍历的麻烦。

核心概念#

概念说明类比
键（Key）用于查找数据的标识符书名
值（Value）与键关联的实际数据书的内容
哈希函数将键映射到数组索引的函数图书管理员的索引规则
哈希值哈希函数的输出（数组下标）书架编号

二、哈希表的工作原理#

整体流程#

哈希表工作原理图解

以电话簿为例，查找 “Tom” 的电话号码：

  1. 将键 "Tom" 输入哈希函数
  2. 哈希函数计算出索引值 2
  3. 直接访问数组下标 [2]，取出值 138xxxx

整个过程不需要遍历，一步到位。

哈希函数的本质#

哈希函数的核心任务：将任意大小的输入，映射到固定范围的整数索引。

index=hash(key)mod  table_size\text{index} = \text{hash}(\text{key}) \mod \text{table\_size}

一个最简单的哈希函数示例（字符串键）：

def simple_hash(key: str, table_size: int) -> int:
    """将字符串中每个字符的 ASCII 码相加，再取余"""
    total = sum(ord(ch) for ch in key)
    return total % table_size

例如：simple_hash("Tom", 7) = (84 + 111 + 109) % 7 = 304 % 7 = 3

好的哈希函数的特性#

特性说明重要性
确定性相同输入始终产生相同输出必须
均匀分布输出尽可能均匀分布在数组范围内必须
高效计算计算过程简单快速重要
雪崩效应输入的微小变化导致输出巨大变化加分项

三、哈希冲突#

为什么会产生冲突？#

哈希函数把无限的输入空间映射到有限的数组空间，根据鸽巢原理，冲突是不可避免的。

例如，假设数组大小为 7：

  • hash("Tom") = 3
  • hash("Max") = 3

两个不同的键映射到了同一个索引——这就是哈希冲突。

解决方法一：链地址法（Separate Chaining）#

思路：每个数组位置不再只存一个元素，而是维护一个链表。所有哈希到同一位置的元素，都挂在这个链表上。

链地址法与开放定址法对比

class ChainingHashTable:
    def __init__(self, size=7):
        self.size = size
        self.table = [[] for _ in range(size)]  # 每个槽位是一个空链表


    def _hash(self, key):
        return hash(key) % self.size


    def put(self, key, value):
        idx = self._hash(key)
        # 如果 key 已存在，更新 value
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        # 否则追加到链表末尾
        self.table[idx].append((key, value))


    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        raise KeyError(key)


    def delete(self, key):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                del self.table[idx][i]
                return
        raise KeyError(key)

复杂度：

操作平均最坏（所有键冲突）
查找O(1)O(n)
插入O(1)O(n)
删除O(1)O(n)

解决方法二：开放定址法（Open Addressing）#

思路：冲突发生时，不使用链表，而是按照某种探测序列在数组中寻找下一个空位。

class OpenAddressingHashTable:
    def __init__(self, size=7):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size


    def _hash(self, key):
        return hash(key) % self.size


    def put(self, key, value):
        idx = self._hash(key)
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                self.values[idx] = value  # 更新
                return
            idx = (idx + 1) % self.size   # 线性探测：找下一个位置
        self.keys[idx] = key
        self.values[idx] = value


    def get(self, key):
        idx = self._hash(key)
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.size
        raise KeyError(key)

三种探测策略对比#

策略探测序列优点缺点
线性探测h, h+1, h+2, …实现简单容易聚集（primary clustering）
二次探测h, h+1², h+2², …减少聚集可能无法探测所有位置
双重哈希h, h+hash₂(key), h+2·hash₂(key), …分布最均匀计算开销较大

四、哈希表的存储结构#

底层数组#

哈希表的底层是一个固定大小的数组（称为”桶数组”或”bucket array”）。

索引:  [0]    [1]    [2]    [3]    [4]    [5]    [6]
值:   Amy    ---    Tom    Bob    Eve    Max    ---

当数据量接近数组大小时，冲突概率急剧上升，查找退化为 O(n)。此时需要扩容（rehash）。

负载因子#

负载因子=已存储元素数量数组大小=nm\text{负载因子} = \frac{\text{已存储元素数量}}{\text{数组大小}} = \frac{n}{m}

负载因子冲突概率性能
0 ~ 0.5低优秀
0.5 ~ 0.75适中良好
0.75+高明显退化
1.0（满）100%退化为 O(n)

[!tip] Java HashMap 的阈值 Java 的 HashMap 默认负载因子阈值为 0.75。当超过这个值时，数组大小翻倍，所有元素重新哈希（rehash）到新数组中。

扩容（Rehash）过程#

def _resize(self):
    """当负载因子超过阈值时扩容"""
    old_table = self.table
    self.size *= 2                    # 数组大小翻倍
    self.table = [[] for _ in range(self.size)]
    self.count = 0
    for bucket in old_table:
        for key, value in bucket:
            self.put(key, value)      # 重新哈希所有元素

五、常见哈希函数#

类型公式适用场景
除法取余hash = key % table_size整数键
乘法取整hash = floor(key * A % 1 * table_size)浮点数键
平方取中hash = (key²) // 10^(n/2) % table_size数字键
字符串哈希逐字符加权求和字符串键

一个更健壮的字符串哈希函数（DJB2 算法）：

def djb2_hash(key: str, table_size: int) -> int:
    """Dan Bernstein 的经典哈希算法"""
    hash_val = 5381
    for ch in key:
        hash_val = ((hash_val << 5) + hash_val) + ord(ch)  # hash * 33 + c
    return hash_val % table_size

六、完整实现：带扩容的哈希表#

class HashMap:
    """链地址法实现，支持自动扩容"""


    def __init__(self, initial_size=7, load_factor=0.75):
        self.size = initial_size
        self.load_factor = load_factor
        self.count = 0
        self.table = [[] for _ in range(self.size)]


    def _hash(self, key):
        return hash(key) % self.size


    def _check_resize(self):
        if self.count / self.size > self.load_factor:
            self._resize()


    def _resize(self):
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        for bucket in old_table:
            for key, value in bucket:
                self.put(key, value)


    def put(self, key, value):
        self._check_resize()
        idx = self._hash(key)
        bucket = self.table[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1


    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        raise KeyError(key)


    def delete(self, key):
        idx = self._hash(key)
        bucket = self.table[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.count -= 1
                return
        raise KeyError(key)


    def __repr__(self):
        items = []
        for bucket in self.table:
            for k, v in bucket:
                items.append(f"{k}: {v}")
        return "{" + ", ".join(items) + "}"

使用示例：

hm = HashMap()
hm.put("Tom", 13800001111)
hm.put("Amy", 13900002222)
hm.put("Bob", 13600003333)
print(hm.get("Tom"))   # 13800001111
hm.delete("Amy")
print(hm)              # {Tom: 13800001111, Bob: 13600003333}

七、实际应用#

场景说明
字典/MapPython dict、Java HashMap、JS Object
缓存系统Redis、Memcached 的核心数据结构
数据库索引加速 WHERE 条件查询
去重利用键的唯一性快速判重
计数器统计词频、访问次数等
符号表编译器中变量名到内存地址的映射

八、总结#

对比项数组/链表哈希表
查找O(n)O(1) 平均
插入O(n)O(1) 平均
删除O(n)O(1) 平均
有序性有序（数组）无序
空间紧凑需要额外空间

哈希表的核心就一句话：用空间换时间。通过哈希函数把查找变成计算，把遍历变成定位，从而实现了常数级的操作速度。

[!note] 参考资料

深入理解哈希表：从原理到实现的完全指南
https://qiandaos.top/posts/hash-table/
作者
千岛寒流
发布于
2025-05-12
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

小白自制Linux开发板（一）—— 原理图设计与PCB绘制
Redis学习系列 | Redis 不只是缓存——一个数据结构服务器的世界观
© 2026 千岛寒流. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 7.6.5
封面
Sample Song
Sample Artist
封面
Sample Song
Sample Artist
0:00 / 0:00