通常来说，我不能回答这个问题。

问题是哈希表和平衡二叉树的类型很多，它们的性能差异很大。

因此，简单的答案是：它取决于您所需的功能。如果不需要排序，请使用哈希表，否则请使用平衡的二叉树。

对于更详尽的答案，让我们考虑一些替代方法。

哈希表（有关某些基础知识，请参阅Wikipedia的条目）

• 并非所有哈希表都将链接列表用作存储桶。一种流行的替代方法是使用“更好”的存储桶，例如二叉树或另一个哈希表（带有另一个哈希函数），…
• 一些哈希表根本不使用存储桶：请参阅开放式寻址（显然，它们还带有其他问题）
• 有一种叫做线性重新哈希的东西（它是实现细节的质量），它避免了“停止世界并重新哈希”的陷阱。基本上，在迁移阶段，您只能插入“新”表中，还将一个“旧”条目移到“新”表中。当然，迁移阶段意味着需要双重查询等。

二叉树

• 重新平衡的成本很高，您可以考虑使用“跳过列表”（对于多线程访问也更好）或“播放树”。
• 一个好的分配器可以将节点在内存中“打包”在一起（更好的缓存行为），即使这不能减轻指针查找问题。
• B树和变体还提供“包装”

我们不要忘记O（1）是渐近复杂性。对于少数元素，系数通常更重要（从性能角度而言）。如果您的哈希函数很慢，则尤其如此。

最后，对于集合，您可能还希望考虑概率数据结构，例如BloomFilters。