您是否对上述这些结构有过一些经验？如果插入和查找很重要,那么在实践中看起来最好的是什么？
如果哈希表有很多冲突,你最终会得到一个需要遍历的存储桶列表,所以如果性能很重要,你最终可能会在O(n)中结束.到目前为止,我没有使用基数树的经验,而且我认为红黑树在查找时击败了AVL树.
你有什么经历？
谢谢,丹
我不认为我曾经有过用哈希表编写代码的情况,并且结构已被证明具有固有的不可接受的性能.
我不认为我曾经遇到过用平衡树编写代码的情况,并且结构已被证明具有固有的不可接受的性能.
所以我不要太担心它,并采取简单的路线.Python提供基于散列的集/字典,所以我使用它们.C++ 03提供了set和map,但不unordered_set和unordered_map,所以我用的.在语言/库而双方都可以,我用我是否需要为了一棵树,一个哈希表,如果(一)我不需要顺序,和(B)我还是可以写一个体面的哈希函数.如果我已经拥有自然顺序,但不是自然哈希函数,那么当然简单的路径就是树.
实际上,绝大多数关联数组都是在字符串,整数或元组中键入的.所以你总是有一个订单,一个不错的哈希函数是不远的.如果我使用的那个似乎都很狡猾,那么很容易尝试它们.
基数树基本上适用于您期望长公共前缀的情况.例如,如果您的密钥是网页的URL,那么它们之间的"几乎所有"和"全部"之间的某个地方将以http://或者开头https://,主机名为树的各个部分提供更多公共前缀.因此,明显的优化是避免在查找期间多次比较该公共前缀,这表示针对"普通"平衡树.但与往常一样,"明显的"优化并不一定值得付出努力,除非您碰巧有一个库已经可以提供.