查看原文

python/cpython/Objects/dictobject.c 是 CPython 的 dict 实现。

• indices 做 hashtable, entries 则作为 KeyEntry 的数组用来存 kv 数据。
• hashtable 有两种：combined table, split table.
• 哈希表中的 slots 有 4 种类型：unused, active, dummy, pending; 前两个很好理解，一个没用过，一个有数据，后两种跟删过的数据有关。
• 最小的 size 是 8，一个工程上的假设和优化。
• perturb_shift 设置为 5，用来做哈希碰撞的检测，也是个工程上认为是个合理的取值。
• 数据量到达 2n/3 的时候会做扩容
• hash look 算法取自 Knuth Vol. 3, Sec. 6.4.
• Open addressing 比 chaining 性能更好，因为后者的 malloc overhead.