Python字典的底层哈希数据结构

Question

我正在建立一个非常大的字典，并且进行很多检查，以查看某个键是否在这个结构中。如果这个键是唯一的，我就添加它；如果它已经存在，我就增加一个计数器。

在Python中，字典是通过一种叫做哈希数据结构来存储的（这和加密哈希函数是不同的）。查找的速度是O(1)，也就是说查找非常快。但是，如果哈希表满了，就需要重新计算哈希，这个过程非常耗费资源。

我的问题是，使用AVL二叉搜索树会更好，还是哈希表就足够了？

Answer 1

物品和独特物品的比例是多少？预计会有多少个独特物品呢？

如果一个哈希桶满了，那么扩展它应该只是重新分配一些内存，而不是重新计算哈希值。

测试一个计数字典应该非常简单快捷。

另外，注意从Python 2.7开始就有的计数器类，详细信息可以查看这个链接：http://docs.python.org/library/collections.html#counter-objects，还有这个链接：http://svn.python.org/view?view=rev&revision=68559

Answer 2

Python 的字典（dictionaries）经过了高度优化。Python 在 CPython 字典的实现中做了很多特别的优化，这些都是 Python 开发者考虑到的。

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

书籍《美丽的代码》中详细讨论了这些内容。

第十八章是由 Adrew Kuchling 撰写的《Python 的字典实现：为所有人服务》。

使用 Python 自带的字典要好得多，而不是尝试自己手动实现一个，因为如果自己做的话，必须要复制这些优化，才能接近 CPython 字典查找的效果。

Answer 3

要想确定哪个更快，最好的办法就是同时实现这两种方法然后比较一下。不过我猜测字典会更快，因为二叉搜索树查找和插入的时间复杂度是O(log(n))，而哈希表的查找时间复杂度是O(1)。在大多数情况下，哈希表的查找速度会比偶尔的扩容要快，除非遇到极端糟糕的情况，比如大量的哈希冲突。

如果你看看Python字典的实现，你会发现：

1. 字典一开始有8个条目（PyDict_MINSIZE）；
2. 如果字典的条目在50,000个或更少时，扩容时会变成原来的四倍；
3. 如果字典的条目超过50,000个，扩容时会变成原来的两倍；
4. 字典中的键的哈希值会被缓存，所以在扩容时不会重新计算。

(关于字典优化的说明也值得一读。)

所以如果你的字典有1,000,000个条目，我相信它会在扩容时调整11次（8 → 32 → 128 → 512 → 2048 → 8192 → 32768 → 131072 → 262144 → 524288 → 1048576 → 2097152），在扩容过程中会多插入2,009,768次。这看起来远远低于在AVL树中插入1,000,000个条目时需要的重新平衡的成本。