【python】字典数据结构的设计原理学习

核心结构：哈希表是一个“数组”

每个 dict 底层对应一块数组（table），数组每个槽位（slot）可能存一个 key-value。

1 2	index:01234567 value: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

任何输入的key 会被哈希（hash(key)）

1 2 3 4 5 6

d["abc"]=123 # python会计算 h=hash("abc") → 得到一个整数，如918273645 slot=h%table_size → 如918273645%8=5

于是 key 放到槽位 5

1 2	index:01234567 value: [ ] [ ] [ ] [ ] [ ] [('abc',123)] [ ] [ ]

如果计算出的槽位已经被占用，dict 不会链表化存储，而是 继续找下一个空槽位，其中会使用 开放寻址（Open Addressing）

1 2	slot6空？ → 放这里 slot6也有人？ → 看 slot7

dict 会控制“负载因子”（使用率），比如如果槽位使用率超过 ~2/3，自动扩容。扩容后空间很大，冲突变少，因此 dict 的性能保持 O(1)。

扩容操作：

• table 大小扩成原来的 2 倍

• 所有 key 重新哈希并放入新 table（rehash）

看具体的应用场景：使用dict进行查找、插入操作，时间复杂度是O(1)

1. 查找过程

查找d[key]：

1. 计算 hash(key)

2. 定位槽位 slot = hash % table_size

3. 看到槽位里是不是这个 key

   • 是 → 找到

   • 否 → 使用开放寻址规则继续探测

那么影响时间长短的，就要看hash算法的底层原理了，hash函数大致是位运算+随机化

1 adict = {} 2 adict[key]=value 3 if i not in adict: # i是否属于adict的key