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

核心结构哈希表是一个“数组”每个 dict 底层对应一块数组table数组每个槽位slot可能存一个 key-value。12index:01234567value: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]任何输入的key 会被哈希hash(key)123456d[abc]123# python会计算hhash(abc) → 得到一个整数如918273645sloth%table_size → 如918273645%85于是 key 放到槽位 512index:01234567value: [ ] [ ] [ ] [ ] [ ] [(abc,123)] [ ] [ ]如果计算出的槽位已经被占用dict 不会链表化存储而是 继续找下一个空槽位其中会使用 开放寻址Open Addressing12slot6空 → 放这里slot6也有人 → 看 slot7dict 会控制“负载因子”使用率比如如果槽位使用率超过 ~2/3自动扩容。扩容后空间很大冲突变少因此 dict 的性能保持 O(1)。扩容操作table 大小扩成原来的 2 倍所有 key 重新哈希并放入新 tablerehash看具体的应用场景使用dict进行查找、插入操作时间复杂度是O(1)1. 查找过程查找d[key]计算 hash(key)定位槽位 slot hash % table_size看到槽位里是不是这个 key是 → 找到否 → 使用开放寻址规则继续探测那么影响时间长短的就要看hash算法的底层原理了hash函数大致是位运算随机化1 adict {} 2 adict[key]value 3 if i not in adict: # i是否属于adict的key