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

先说结论：

python的dict，底层是哈希表（hash table）与开放寻址方案（二次探测 + 伪随机跳跃）
此中，
核心结构：哈希表是一个“数组”

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

1. index:   0   1   2   3   4   5   6   7
2. value:  [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

复制代码

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

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

复制代码

于是 key 放到 槽位 5

1. index:   0   1   2   3   4   5   6   7
2. value:  [ ] [ ] [ ] [ ] [ ] [('abc',123)] [ ] [ ]

复制代码

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

1. slot 6 空？ → 放这里
2. slot 6 也有人？ → 看 slot 7

复制代码

　　
dict 会控制“负载因子”（利用率），好比如果槽位利用率高出 ~2/3，自动扩容。扩容后空间很大，辩论变少，因此 dict 的性能保持 O(1)。
扩容利用：

• table 巨细扩成原来的 2 倍
  
• 全部 key 重新哈希并放入新 table（rehash）
  

 
看具体的应用场景：利用dict举行查找、插入利用，时间复杂度是O(1)
1. 查找过程
查找 d[key]：

• 盘算 hash(key)
  
• 定位槽位 slot = hash % table_size
  
• 看到槽位里是不是这个 key
  
  
  
  • 是 → 找到
    
  • 否 → 利用开放寻址规则继续探测
    
  
  

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