平均速度，btree或散列表的速度是多少？

Question

我试着比较b-tree和hash table查找时间复杂度。

B树需要log_b(n)操作和log_b(n) <= b如果n <= b^b所以b = 10是10^10在任何情况下，我有一下了10操作。 哈希表平均需要查询1查询。但如果我有一个10^10键和我的哈希表的大小是10^10/10那么它将是10操作查找平均情况下（单独链接），或不？

我认为这是很多理论。我想知道，在实践中有什么更好？为什么？

Answer 1

实际上哪个更好？

这取决于。

b树总是O（log n）的表现。

哈希表是O（1）（比B树好得多）与

1. 好的哈希函数为您的数据。
2. 足够的散列桶。

如果这些条件不能满足，然后哈希表将趋于为O（n）（即比B-树更糟糕）。

摘要：良好的散列函数：散列表通常会更好。一棵b树是一致的，不需要散列函数。

在实践ñ并不大，甚至是普通的哈希会好到足以实现足够接近O（1），关于这个问题花费的时间是一个毫无意义的优化。

真实答案：直到您测量性能并确定数据结构查找时间显着时，才会将您的优化工作放在您的用户将看到显着差异的地方。

Answer 2

由于它们提供不同的功能，因此无法轻松进行比较。哈希表是一个键值存储，而树也允许基于顺序查找（上一个/下一个等）。

经验法则：如果您想将它们用于特定任务，则只需度量哪一个更好。

注意：这些数字是巨大的，它甚至适合您的机器的内存？