哈希表与树

哈希表是否总是比树快？

不，并非 总是如此 。这取决于许多因素，例如集合的大小，哈希函数以及某些哈希表实现-以及删除 *** 作的数量。

哈希表 平均

O(1)

O(n)

我现在可以想到一些偏爱树木的原因：

1. 订购很重要。[哈希表未保持顺序，BST按定义排序]
2. 延迟是一个问题-您不能承受

   O(n)

   可能发生的延迟。[这对于实时系统可能至关重要]
3. 这些数据可能与您的散列函数“相似”，并且散列到相同位置[冲突]的许多元素并非不可能。[有时可以通过使用其他哈希函数来解决]
4. 对于较小的集合-很多时候，哈希表之间的隐藏常数

   O(1)

   要比树的隐藏常数高得多-对于小集合而言，使用树可能更快。

但是，如果数据量很大，那么延迟就不是问题，并且不可能发生冲突-哈希表比使用树更好地渐近。