二叉search树在哈希表上的优势
二叉search树比哈希表有什么优势？
哈希表可以在Theta（1）时间内查找任何元素，添加一个元素也是一样容易的……但我不确定相反的优势。
请记住，二进制search树（基于引用）是内存有效的。 他们不会保留比他们需要更多的记忆。
例如，如果散列函数的范围R(h) = 0...100 ，那么即使只是散列20个元素，也需要分配一个由100个（指向）元素组成的数组。 如果您要使用二叉search树来存储相同的信息，则只会根据需要分配尽可能多的空间，以及一些关于链接的元数据。
没有人指出的一个优点是二叉search树可以有效地进行范围search。
为了说明我的想法，我想做一个极端的例子。 假设你想得到所有的键元素都在0到5000之间的元素，实际上只有一个这样的元素和10000个其他键元素不在范围内的元素。 BST可以非常有效地进行范围search，因为它不search不可能得到答案的子树。
而如何在散列表中进行范围search呢？ 您需要迭代每个桶空间（即O（n）），或者您必须查找是否存在1,2,3,4 …最多5000个。 （0到5000之间的键是一个无限集？例如键可以是小数）
二叉树的一个“优点”是可以遍历所有元素。 这不是一个哈希表不可能，但不是一个正常的操作一个devise成散列结构。
除了所有其他的好评：
与二叉树相比，散列表通常具有更好的caching行为，需要更less的内存读取。 对于散列表，通常只有在访问保存数据的引用之前才会进行单个读取。 二叉树，如果它是一个平衡的变体，需要按照k * lg（n）内存读取的顺序对某个常量k进行操作。
另一方面，如果一个敌人知道你的散列函数，敌人可以强制你的散列表进行冲突，从而大大地妨碍了它的性能。 解决方法是从家庭中随机select散列函数，但BST没有这个缺点。 而且，当哈希表压力增长过多时，您往往会放大并重新分配哈希表，这可能是一个昂贵的操作。 BST在这里有更简单的行为，并不倾向于突然分配大量数据并进行重新哈希操作。
树木往往是最终的平均数据结构。 他们可以作为列表，可以很容易地拆分为并行操作，具有快速删除，插入和查找O（lg n）的顺序。 他们没有做什么特别好，但他们也没有任何过分的不良行为。
最后，与散列表相比，BST更容易在（纯）function语言中实现，并且它们不需要实施破坏性更新（上面的Pascal的持久性参数）。
二叉树比哈希表的主要优点是二叉树给你两个额外的操作你不能做（容易，快速）与一个哈希表
-
find最接近（不一定等于）某个任意键值的元素（或者最接近的上/下）
-
以sorting的顺序遍历树的内容
二者是连接的 – 二叉树保持其内容的sorting顺序，所以需要sorting顺序的事情很容易做到。
（平衡）二叉search树还具有这样的优点：其渐近复杂度实际上是一个上限，而散列表的“常量”时间是摊销次数：如果你有一个不适合的散列函数，最终可能会降级到线性时间，而不是不变。
哈希表在创build时会占用更多的空间 – 对于尚未插入的元素（无论是否插入），它将具有可用插槽，二叉search树将只有它所需的大小是。 另外，当一个散列表需要更多的空间时，扩展到另一个结构可能是耗时的，但是这可能取决于实现。
二叉search树可以用一个持久接口来实现，在那里返回一个新的树，但是旧的树继续存在。 旧的和新的树共同实施了大部分的节点。 你不能用一个标准的哈希表来做到这一点。
二叉树search和插入速度较慢，但中缀遍历非常好，这意味着您可以按sorting顺序遍历树的节点。
迭代一个哈希表的条目并没有什么意义，因为它们全都分散在内存中。
BST还在O（logn）时间内提供“findPredecessor”和“findSuccessor”操作（查找下一个最小和次最大的元素），这也可能是非常方便的操作。 哈希表不能提供那个时候的效率。
从破解编码采访，第6版
我们可以用平衡二叉search树（BST）来实现哈希表。 这给了我们一个O（log n）查找时间。 这样做的好处是可能使用更less的空间，因为我们不再分配一个大的数组。 我们也可以按顺序遍历这些键，这有时候会很有用。
如果你想以一种sorting的方式访问数据，那么一个sorting列表必须与哈希表保持并行。 .Net中的Dictionary就是一个很好的例子。 （请参阅http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx ）。
这具有不仅减慢插入的副作用，而且比b树消耗更多的内存。
此外，由于对b树进行sorting，所以很容易find结果范围，或者执行联合或合并。
这也取决于使用，哈希允许find完全匹配。 如果你想查询范围，那么BST是select。 假设你有大量的数据e1，e2，e3 ….. en。
使用散列表可以在任何时间定位任何元素。
如果您想查找大于e41且小于e8的范围值，BST可以快速find该值。
关键是用来避免碰撞的散列函数。 当然，我们不能完全避免碰撞，在这种情况下，我们会采取链接或其他方法。 这使得在最坏的情况下检索不再是恒定的时间。
一旦填满，哈希表必须增加其桶大小，并再次复制所有元素。 这是BST以外的额外费用。
哈希表是一种无序的数据结构，在devise手机时，您希望保留尽可能多的数据用于数据存储。 散列表是一个无序的数据结构 – 这意味着它不保留任何特定顺序的元素。 所以，如果你使用手机地址簿的哈希表，那么你需要额外的内存来对值进行sorting，因为你肯定需要按字母顺序显示这些值 – 毕竟它是一个地址簿。 因此，通过使用散列表，您必须预留内存来sorting否则将被用作存储空间的元素。 但是二叉search树是一个有序的数据结构。由于二叉search树已经sorting，所以不需要浪费内存或处理时间在手机中sortinglogging。 正如我们前面提到的，在二叉树上执行查找或插入比使用散列表执行要慢，但手机地址簿几乎不会超过5000个条目。 有了这么less的条目，二叉search树的O（log（n））肯定会足够快。 因此，考虑到所有这些信息，二叉search树就是这种情况下应该使用的数据结构，因为它是一个比散列表更好的select。
哈斯表是不好的索引…当你正在寻找一个范围….. BST是更好的。 这就是为什么大多数数据库索引使用B +树而不是HashTable的原因
哈希映射是一个集合关联数组。 所以，你的数组input值被汇集成桶。 在一个开放的寻址scheme中，你有一个指向一个存储桶的指针，并且每当你向一个存储桶中添加一个新的值时，你就会发现存储桶中有空闲空间。 有几种方法可以做到这一点 – 从桶的开始处开始，每次增加指针并testing它是否被占用。 这被称为线性探测。 然后，您可以像添加一样执行二进制search，您可以在桶的开始位置和每次search空闲空间时双倍或下降两倍之间的差异加倍。 这被称为二次探测。 好。 现在这两种方法的问题是，如果桶溢出到下一个桶地址，那么你需要 –
- 将每个桶大小加倍 – malloc（N桶）/更改散列函数 – 所需时间：取决于malloc实现
- 将每个较早的桶数据传输/复制到新的桶数据中。 这是一个O（N）操作，其中N表示整个数据
好。 但是如果你使用链表，那么不应该有这样的问题吧？ 是的，在链接列表中，你没有这个问题。 考虑到每个桶以一个链表开始，并且如果一个桶中有100个元素，则需要遍历这100个元素才能到达链表的末尾，因此List.add（Element E）需要时间
- 将元素散列到一个桶中 – 正如在所有实现中一样
- 花点时间找出所述bucket-O（N）操作中的最后一个元素。
链表实现的优点是你不需要像开放地址实现的情况那样进行内存分配操作和所有桶的O（N）传输/复制。
因此，最小化O（N）操作的方法是将实现转换为二进制search树的实现，其中查找操作是O（log（N）），并且将该元素添加到基于其值的位置中。 BST的附加function是它被分类！
散列表的主要优点是它几乎可以在〜= O（1）中执行所有操作。 而且很容易理解和实施。 它确实有效地解决了许多“面试问题”。 所以如果你想破解一个编码面试，用哈希表做最好的朋友;-)
类HashSet和Table是无序的集合。 从接口不是很明显（也可能是其他），但哈希表已经使用AVL树实现。 这意味着哈希码不会被数组的模数减less（冲突less），也意味着不会对数组进行重新哈希（性能更平滑）。 它们是无序集合的事实意味着你只提供一个equals函数和一个hashCode函数 – 而不是一个完整的比较器。 因此，无论使用哈希表Table <K，T>还是二叉树Tree <K，T>都取决于K类 – 它是完全可比较的还是只能进行相等的比较。
在某些情况下，数据types是可比较的并且是平等可比的 – 比如String。 这意味着HashSet <String>和Set <String>都是可能的。 search一个string的散列集比在一组有序的string上search要快10倍左右。 如果比较器比较昂贵，那么与HashTable相比，树会变慢。 如果比较器速度很快（比如整数和浮点数），那么树会比散列表运行得更快。
