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

Question

我正在构建一个非常大的字典，进行很多检查以查看一个键是否在数据结构中，如果是唯一的则添加，如果是相同的则增加计数器。

Python使用哈希数据结构来存储字典（不要与密码学哈希函数混淆）。查找是O（1）的，但如果哈希表已满，则必须重新哈希，这非常昂贵。

我的问题是，我是否最好使用AVL二叉搜索树，还是哈希表已足够好？

- rook

---

请注意，如果你正在考虑散列表和AVL树哪个性能更好，那么还有很多其他的选择。例如Trie树和Splay树。 - Steve Jessop

也许您甚至可以使用计数布隆过滤器。 - Jochen Ritzel

from collections import Counter - Matthieu M.

@THC4k，是的，谷歌使用了布隆过滤器，非常有趣的东西。 - rook

Answer 1

唯一确定的方法是实现两者并进行检查，但我的知情猜测是字典会更快，因为二叉搜索树在查找和插入时的成本为O(log(n))，而我认为除了在最恶劣的情况下（例如大规模哈希碰撞）哈希表的O(1)查找将超过偶尔的调整大小。

如果您查看Python dictionary implementation，您会发现：

1. 字典从8个条目（PyDict_MINSIZE）开始； 2. 50,000个或更少条目的字典增长时会增加4倍； 3. 具有50,000个以上条目的字典增长时会增加两倍； 4. 键哈希值被缓存在字典中，因此在调整字典大小时不会重新计算。

（值得阅读的是"NOTES ON OPTIMIZING DICTIONARIES"。）

因此，如果您的字典有1,000,000个条目，我相信它将被调整大小11次（8→32→128→512→2048→8192→32768→131072→262144→524288→1048576→2097152），在调整大小期间需要进行2,009,768次额外插入。这似乎比将1,000,000个元素插入AVL树中所涉及的所有重新平衡的成本要小得多。

- Gareth Rees

Answer 2

Python字典是高度优化的。Python在CPython字典实现中提供了各种特殊情况的优化，Python开发人员为此进行了优化。

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

书籍 "Beautiful Code" 讨论了这些内容。

第18章是Adrew Kuchling所写的《Python字典实现：成为所有人的东西》。

使用它比尝试实现手工定制更好，后者将不得不复制所有这些优化才能接近主要的CPython字典查找实现。

- pyfunc

---

Python非常依赖于字典，这对语言本身的性能产生了广泛影响。我敢打赌，他们的实现很难被超越。 - André Caron

@André Caron：当然！还可以看看Gareth Rees的回答。我们几乎是相似的写法。Python对字典的实现和优化非常好，它依赖于它。很难超越它。 - pyfunc

我刚刚在阅读关于“优化字典”的笔记。这是一份很棒的文献。我喜欢人们记录实验和讨论，因为这样可以避免重复工作（就像这篇文章一样…）。 - André Caron

Answer 3

项目与独特项目的比例是多少？ 预期有多少个独特项目？

如果哈希桶已满，则扩展只需要进行一些内存重新分配，而不是重新哈希。

测试计数字典应该非常快且易于完成。

请注意，自Python 2.7以来提供了计数器类 http://docs.python.org/library/collections.html#counter-objects http://svn.python.org/view?view=rev&revision=68559

- pixelbeat

---

是的，楼主说字典必须重新散列是错误的。 - Daniel Roseman

我认为将项目重新分配到更大的桶数组中的操作即使你已经存储了完整的哈希值并且不需要重新计算它，只需使用不同的值进行模运算，这个操作被称为再散列。无论哪种情况，与普通插入相比，这都是一项昂贵的操作。 - Steve Jessop

增加桶的大小和增加桶的数量是有区别的。增加桶的大小通常比较便宜，特别是当只存储对象指针时。增加桶的数量则是另外一回事。由于这种情况应该只发生“足够频繁”，因此应该考虑将其分摊到插入次数上。 - André Caron

Answer 4

使用字典是O(1)的。随着字典的增长，有时需要重新分配内存，但这是平摊O(1)的。

如果您使用的其他算法是O(log n)，那么简单的字典将在数据集变大时始终胜出。

如果您使用任何类型的树，则其中必然会有一个O(log n)的组件。

不仅哈希表足够好，而且它更好。

- John La Rooy

Answer 5

如果想要击败内置的数据结构，你需要在C中实现自己的数据结构。

此外，如果使用get，可以避免两次查找现有元素而节省一些开销。如果使用Python 2.7+，也可以使用collections.Counter。

def increment(map, key):
    map[key] = map.get(key,0)+1

- Douglas Leeder

---

这似乎没有增加值。 - terminus

我喜欢这个，但是你的增量函数没有增加 :-) - André Caron