基于本文回答

播面 播面

文图音视，全方位拆解八股文
0
评论
请从左侧选择一个分类

Python 的字典（Dictionary）底层实现原理（哈希表）

知识点图片

Python 的字典（dict）是 Python 中最重要、最常用的数据结构之一。它的底层实现基于 哈希表（Hash Table），这使得字典在理想情况下的查找、插入和删除操作的时间复杂度都为 O(1)。

然而，Python 对哈希表的实现经过了多次优化（特别是 Python 3.6 之后）。下面我将深入浅出地解析其底层原理。

1. 核心概念：哈希表与哈希函数

字典本质上是一个数组（在内存中是连续的空间），通过 哈希函数 将“键（Key）”映射到数组的“索引（Index）”上。

  1. 哈希函数（Hash Function）：

    • 当你执行 d['name'] = 'Alice' 时，Python 首先计算 'name' 的哈希值：hash('name')。
    • 得到一个整数（例如 -909234...）。
    • 要求： 字典的 Key 必须是不可变类型（可哈希），如整数、字符串、元组；列表和字典不能作为 Key。

  2. 计算索引：

    • 哈希值通常很大，不能直接作为数组下标。Python 通过取模运算（位运算优化）将哈希值映射到数组的大小范围内。
    • 公式大致为：index = hash(key) & (len(array) - 1)。

2. 解决哈希冲突（Collision）

当两个不同的 Key 计算出的索引位置相同时，就发生了哈希冲突。

Python 使用 开放寻址法（Open Addressing） 来解决冲突，而不是链地址法（Linked List，如 Java 的 HashMap）。

  • 工作原理：
    • 如果计算出的位置 i 已经被占用了，Python 就会按照特定的规则探测下一个位置 j。
    • 如果 j 也被占用，继续探测 k，直到找到一个空位。
  • 探测算法：
    • Python 并不是简单的“线性探测”（即 i+1, i+2...），因为这会导致数据聚集（Clustering）。
    • Python 使用一种伪随机探测序列（j = (5 * j) + 1 + perturb），让数据在数组中分布得更均匀。

3. 内存结构的演变（关键点）

这是面试或深入理解时的加分项。Python 3.6 对字典的内存结构进行了重构，使其更紧凑且有序。

A. Python 3.6 之前（稀疏数组，无序）

在老版本中，字典是一个巨大的结构体数组（Entry Array）。每个槽位（Slot）存储三个信息：哈希值、Key 指针、Value 指针。

plaintext 
# 示意图：一个大小为 8 的旧版字典
[
  [hash1, ptr_key1, ptr_val1],  # 索引 0
  [null,  null,     null    ],  # 索引 1 (空)
  [null,  null,     null    ],  # 索引 2 (空)
  [hash2, ptr_key2, ptr_val2],  # 索引 3
  ...
]
  • 缺点： 空间浪费严重。为了减少冲突，哈希表必须保持大约 1/3 的空闲空间。由于每个槽位都很大（存了3个值），这些空槽位浪费了大量内存。
  • 无序： 遍历是按照物理内存顺序进行的，因为插入时位置是跳跃的，所以遍历结果看起来是无序的。

B. Python 3.6 及之后（紧凑数组，有序）

新版实现将数据结构拆分为两个数组：索引数组（Indices） 和 实体数组（Entries）。

  1. Indices（稀疏，但很小）： 只存储整数（指向 Entries 的下标）。
  2. Entries（稠密，按插入顺序）： 存储真正的 (hash, key, value)，并且是紧密排列的，没有空洞。

示例： d = {'name': 'Alice', 'age': 18}

Entries 数组（存数据）：

plaintext 
Entries = [
    0: [hash_name, 'name', 'Alice'],  # 第一次插入
    1: [hash_age,  'age',  18     ]   # 第二次插入
]

Indices 数组（存哈希表逻辑）：
假设 'name' 哈希取模后是 2，'age' 哈希取模后是 5。

plaintext 
Indices = [None, None, 0, None, None, 5, None, ...]
# 索引 2 的位置存的是 0 -> 代表去 Entries[0] 找数据
# 索引 5 的位置存的是 1 -> 代表去 Entries[1] 找数据
  • 优点 1（省内存）： Indices 数组只存简单的整数（如 1 字节或 2 字节），即使有空洞，浪费的空间也非常小。Entries 数组是紧凑的，没有空洞。相比老版本，内存占用减少了约 20%-25%。
  • 优点 2（有序）： 当我们遍历字典时，直接遍历 Entries 数组。因为 Entries 是严格按照插入顺序追加数据的，所以Python 3.7+ 正式宣布字典是有序的。

4. 扩容机制（Resizing）

为了保证查找效率，哈希表不能太满。Python 使用 负载因子（Load Factor） 来决定何时扩容。

  1. 触发条件： 当字典中已使用的元素数量达到总容量的 2/3 时，Python 会自动扩容。
  2. 扩容过程：
    • 申请一块更大的内存（通常是原来的 2 倍或 4 倍）。
    • Rehashing： 所有的键值对都需要重新计算索引，并搬运到新的表中（因为数组长度变了，取模的结果 hash & (new_size - 1) 也会变）。
    • 这是一个耗时操作（O(N)），所以应尽量避免频繁扩容。

5. 字典操作流程总结

查找流程 (value = d[key])：

  1. 计算 h = hash(key)。
  2. 计算索引 ix = h & (size - 1)。
  3. 查看 Indices[ix]：
    • 如果是 None -> KeyError。
    • 如果有值 loc -> 去 Entries[loc] 检查。
  4. 检查 Entries[loc] 中的 stored_hash 是否等于 h 且 stored_key 是否等于 key：
    • 如果相等 -> 返回 Value。
    • 如果不相等（哈希冲突） -> 按照探测规则修改 ix，回到步骤 3。

删除流程 (del d[key])：

Python 的字典删除并不是物理删除，而是伪删除。

  • 在 Indices 数组中，将对应的位置标记为 DUMMY（一个特殊的占位符）。
  • 这是为了保证探测链不断裂（如果直接设为 None，处于冲突链后方的元素就找不到了）。
  • 只有在扩容或重建字典时，这些 DUMMY 才会真正被清理掉。

总结

  1. 底层结构： 哈希表。
  2. 冲突解决： 开放寻址法（伪随机探测）。
  3. 关键优化（Python 3.6+）： 分离了“索引数组”和“实体数组”。
    • Indices： 稀疏，存下标，负责哈希映射。
    • Entries： 稠密，存数据，负责存储和保持顺序。
  4. 特性： 查找快（O(1)）、空间换时间、Key 必须可哈希、Python 3.7+ 保证有序。
00:00
00:00