哈希表在Python中的具体实现（dict） 描述 Python中的字典（dict）是哈希表的典型实现，用于存储键值对。它支持高效的插入、查找和删除操作，平均时间复杂度为O(1)。与Java的HashMap不同，Python的dict在解决哈希冲突时采用开放定址法，并通过动态扩容保证性能。本专题将详细解析dict的内部结构、哈希冲突解决策略、扩容机制及内存管理。 1. 内部结构：索引表与条目数组 Python的dict由两个核心数组构成： 索引表（Indices） ：一个稀疏数组，存储条目在条目数组中的索引（整数）。初始大小为8，每个位置存-1（表示空位）。 条目数组（Entries） ：存储实际的键值对数据，每个条目包含哈希值、键、值三个字段。条目按插入顺序排列。 示例 ：插入键"a"（哈希值为97） 计算索引： 97 % 8 = 1 （索引表大小为8）。 检查索引表位置1：若为-1，则在条目数组追加新条目（哈希值=97, 键="a", 值=...），并将索引表位置1更新为该条目索引（如0）。 若位置1已被占用（哈希冲突），进入冲突解决流程。 2. 哈希冲突解决：伪随机探测 Python使用开放定址法中的 伪随机探测（Pseudo-Random Probing） 解决冲突： 当目标索引被占用时，通过公式计算下一个探测位置： new_index = (5 * current_index + 1) % 2^i （其中i为索引表大小的指数，如大小为8时i=3）。 探测序列覆盖所有索引，避免聚类现象。 示例 ：假设索引1已被占用，继续插入键"b"（哈希值为98）： 计算初始索引： 98 % 8 = 2 。 若索引2空闲，直接插入；若被占用，按公式计算下一个索引： 第一次探测： (5*2 + 1) % 8 = 11 % 8 = 3 第二次探测： (5*3 + 1) % 8 = 16 % 8 = 0 ，直到找到空位。 3. 动态扩容与缩容 当条目数达到索引表大小的2/3时触发扩容，以减少冲突概率： 扩容规则 ：新索引表大小为当前大小的4倍（如8→32），直到超过50,000条后改为2倍。 重新哈希 ：将所有条目重新映射到新索引表（ hash % new_size ）。 缩容条件 ：删除大量条目后，若条目数小于索引表大小的1/2，可能缩容至最小8。 示例 ：初始大小为8的dict插入6个条目（6 ≥ 8* 2/3 ≈ 5.33）时触发扩容： 新索引表大小为32。 遍历条目数组，重新计算每个键的索引（如 97 % 32 = 1 ）。 新索引表初始化为-1，重新填充条目索引。 4. 内存优化：紧凑型布局 Python 3.6+的dict采用紧凑型结构提升缓存效率： 条目数组按插入顺序存储，迭代时直接遍历条目数组（而非索引表），保证顺序性。 索引表仅存储映射关系，条目数组连续存储键值对，减少内存碎片。 5. 特殊机制：删除操作与墓碑标记 删除条目时，为避免破坏探测链，采用 墓碑标记（Tombstone） ： 在索引表中将对应位置标记为特殊值（如-2），而非直接置为-1。 插入新条目时，墓碑位置可复用；扩容时墓碑被清除。 示例 ：删除键"a"（原索引为1）： 在索引表位置1标记为墓碑（-2）。 条目数组中保留该条目，但标记为无效。 后续插入键"c"（哈希值99）时，若计算索引为1，发现是墓碑则直接覆盖。 总结 Python的dict通过索引表与条目数组分离、伪随机探测、动态扩容和墓碑标记等机制，实现了高效且内存友好的哈希表。其设计在冲突解决、顺序迭代和缓存优化上具有独特优势，是工程实践与理论结合的典范。