哈希表v自平衡搜索树 [英] Hash tables v self-balancing search trees

问题描述

我很想知道与使用哈希表相比，使用自平衡树技术存储项目可能会超出什么原因?

I am curious to know what is the reasoning that could overweighs towards using a self-balancing tree technique to store items than using a hash table.

我看到哈希表不能保持插入顺序，但是我总是可以在顶部使用链表来存储插入顺序.

I see that hash tables cannot maintain the insertion-order, but I could always use a linked list on top to store the insertion-order sequence.

我看到对于较小的值，散列函数会增加成本，但是我总是可以将散列函数与键一起保存，以加快查找速度.

I see that for small number of values, there is an added cost of of the hash-function, but I could always save the hash-function together with the key for faster lookups.

我知道哈希表比红黑树的直接实现更难实现，但是在实际实现中，人们不愿意为此加倍努力吗?

I understand that hash tables are difficult to implement than the straight-forward implementation of a red-black tree, but in a practical implementation wouldn't one be willing to go an extra mile for the trouble?

我看到使用哈希表发生冲突是很正常的，但是使用开放式寻址技术(如双重哈希)可以将密钥保存在哈希表本身中，这并没有将问题简化为:是否将这种偏爱转向红黑树?

I see that with hash tables it is normal for collisions to occur, but with open-addressing techniques like double hashing that allow to save the keys in the hash table itself, hasn't the problem been reduced to the effect of not tipping the favor towards red black trees for such implementations?

我很好奇我是否确实错过了哈希表的缺点，该缺点仍然使红黑树在实际应用程序(例如文件系统等)中成为非常可行的数据结构.

I am curious if I am strictly missing a disadvantage of hash table that still makes red black trees quite viable data structure in practical applications (like filesystems, etc.).

推荐答案

这就是我能想到的:

1. 有些数据无法散列(或散列太昂贵)，因此无法存储在散列表中.
2. 树按所需顺序(已排序)而不是插入顺序保留数据.即使您通过哈希表运行链表，也不能(有效)使用哈希表.
3. 树木在最坏情况下的表现更好

这篇关于哈希表v自平衡搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！