Vai*_*pai 15 hashtable red-black-tree
我很想知道使用自平衡树技术来存储项目的原因是什么,而不是使用哈希表.
我看到哈希表不能维护插入顺序,但我总是可以在顶部使用链表来存储插入顺序序列.
我看到,对于少量的值,哈希函数会增加成本,但我总是可以将哈希函数与密钥一起保存,以便更快地查找.
我知道散列表很难实现,而不是红黑树的直接实现,但在实际实现中,人们是否愿意为麻烦付出更多努力？
我看到使用哈希表发生冲突是正常的,但是使用双重哈希等开放寻址技术可以将密钥保存在哈希表本身中,并没有将问题减少到不倾向于使用优惠的效果对于这种实施,红黑树？
我很好奇,如果我严格地缺少哈希表的缺点,仍然使红黑树在实际应用(如文件系统等)中非常可行的数据结构.
unb*_*eli 17
这是我能想到的:
存储分配是另一个考虑因素 每次在散列表中填充所有桶时,都需要分配新存储并重新散列所有内容.如果您提前知道数据的大小,则可以避免这种情况.另一方面,平衡树根本不会受到这个问题的影响.