我正在构建一个非常大的字典，并且正在执行许多检查以查看键是否在结构中，然后添加它是否唯一或如果相同则增加计数器。
Python 使用一个哈希数据结构存储字典（不要与加密哈希函数混淆）。查找的时间复杂度为 O(1)，但如果哈希表已满，则必须重新哈希，这是非常昂贵的。
我的问题是，使用AVL二叉搜索树还是哈希表足够好？
唯一确定的方法是同时实现并检查，但我的明智猜测是字典会更快，因为二叉搜索树的查找和插入成本为 O(log(n))，我认为除了在最悲观的情况下（例如大规模哈希冲突），哈希表的 O(1) 查找将超过偶尔调整大小。
如果你看一下Python字典实现，你会看到：
- 字典一开始有 8 个条目 (
PyDict_MINSIZE);
- 一本包含 50,000 条或更少条目的字典，随着其增长，其大小会增加四倍；
- 一本包含超过 50,000 个条目的字典，其大小会随着增长而增加一倍；
- 键哈希缓存在字典中，因此在调整字典大小时不会重新计算它们。
(The "优化字典的注意事项“也值得一读。）
因此，如果你的字典有 1,000,000 个条目，我相信它将被调整十一次大小 (8 → 32 → 128 → 512 → 2048 → 8192 → 32768 → 131072 → 262144 → 524288 → 1048576 → 2097152)，代价是 2,009,768 次额外插入期间调整大小。这似乎比在 AVL 树中插入 1,000,000 次所涉及的所有重新平衡的成本要低得多。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
