【python】字典数据结构的设计原理学习
先说结论：python的dict，底层是哈希表（hash table）与开放寻址方案（二次探测 + 伪随机跳跃）
其中，
核心结构：哈希表是一个“数组”
每个 dict 底层对应一块数组（table），数组每个槽位（slot）可能存一个 key-value。
index: 0 1 2 3 4 5 6 7
value:[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]任何输入的key 会被哈希（hash(key)）
d["abc"] = 123
# python会计算
h = hash("abc") →得到一个整数，如 918273645
slot = h % table_size →如 918273645 % 8 = 5于是 key 放到 槽位 5
index: 0 1 2 3 4 5 6 7
value:[ ] [ ] [ ] [ ] [ ] [('abc',123)] [ ] [ ]如果计算出的槽位已经被占用，dict 不会链表化存储，而是 继续找下一个空槽位，其中会使用 开放寻址（Open Addressing）
slot 6 空？ → 放这里
slot 6 也有人？ → 看 slot 7
dict 会控制“负载因子”（使用率），比如如果槽位使用率超过 ~2/3，自动扩容。扩容后空间很大，冲突变少，因此 dict 的性能保持 O(1)。
扩容操作：
[*]table 大小扩成原来的 2 倍
[*]所有 key 重新哈希并放入新 table（rehash）
看具体的应用场景：使用dict进行查找、插入操作，时间复杂度是O(1)
1. 查找过程
查找 d：
[*]计算 hash(key)
[*]定位槽位 slot = hash % table_size
[*]看到槽位里是不是这个 key
[*]是 → 找到
[*]否 → 使用开放寻址规则继续探测
那么影响时间长短的，就要看hash算法的底层原理了，hash函数大致是位运算+随机化
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我
页:
[1]