Python的字典哈希数据结构

Question

我正在构建一个非常大的字典,我正在执行许多检查以查看密钥是否在结构中,然后添加它是否唯一或递增计数器(如果它是相同的).

Python使用哈希数据结构来存储字典(不要与加密哈希函数混淆).查找是O(1),但如果哈希表已满,则必须重新进行,这非常昂贵.

我的问题是,我会更好地使用AVL二进制搜索树 还是哈希表足够好？

Answer 1

唯一可以肯定的方法是实现和检查,但我的通知猜测是字典会更快,因为二进制搜索树的成本为O(log(n)),用于查找和插入,我认为除了在最不重要的情况下(例如大规模哈希冲突),哈希表的O(1)查找将超过偶尔的大小调整.

如果你看一下Python字典的实现,你会看到:

1. 字典以8个条目(PyDict_MINSIZE)开头;
2. 一个包含50,000或更少条目的字典,当它增长时,它的大小是四倍;
3. 超过50,000个词条的词典在增长时会增加一倍;
4. 键哈希缓存在字典中,因此在调整字典大小时不会重新计算它们.

(" 优化字典的注意事项 "也值得一读.)

因此,如果您的词典有1,000,000个条目,我相信它将被调整大小十一次(8→32→128→512→2048→8192→32768→131072→262144→524288→1048576→2097152),额外插入成本为2,009,768调整大小.这似乎远远低于将1,000,000次插入到AVL树中所涉及的所有重新平衡的成本.

Answer 2

Python 字典经过高度优化。Python 进行了 Python 开发人员在 CPython 字典实现中满足的各种特殊情况优化。

1. 在 CPython 中，所有 PyDictObject 都针对仅包含字符串键的字典进行了优化。
2. Python 的字典尽量不超过 2/3。

《美丽的代码》一书讨论了这一切。

第十八章是 Adrew Kuchling 的《Python 字典实现：成为所有人的一切》

使用它比尝试实现手工制作的自定义实现要好得多，后者必须将所有这些优化复制到字典查找的主要 CPython 实现附近的任何位置。