TreeMap或HashMap？

Question

何时使用哈希映射或树图？

我知道当我需要对它们进行排序时,我可以使用TreeMap迭代元素.但就是这样吗？当我只想查阅地图或某些最佳特定用途时,没有优化？

Answer 1

TreeMap提供有保证的O(log n)查找时间(和插入等),HashMap如果哈希码适当地分散键,则提供O(1)查找时间.

除非您需要对条目进行排序,否则我会坚持下去HashMap.或者ConcurrentHashMap当然有.我不记得所有这些之间的差异的细节,但是HashMap一个完全合理的"默认"选项:)

为了完整起见,我应该指出,大约一个月前有关于各种地图内部的Stack Overflow的讨论.请参阅此问题中的评论,如果我很高兴我这样做,我会将其复制到此答案中.

Answer 2

Hashtables(通常)执行搜索操作(查找)在复杂性范围内O(n)<=T(n)<=O(1),平均案例复杂度为O(1 + n/k); 然而,二进制搜索树(BST)在复杂度范围内执行搜索操作(查找)O(n)<=T(n)<=O(log_2(n)),平均情况复杂度为O(log_2(n)).应该知道每个(和每个)数据结构的实现(由您),以了解操作的优点,缺点,时间复杂性和代码复杂性.

例如,哈希表中的条目数通常具有一些固定数量的条目(其中一些条目可能根本不被填充)与冲突列表.另一方面,树通常每个节点有两个指针(引用),但如果实现允许每个节点有两个以上的子节点,则可以更多,这允许树在添加节点时增长,但可能不允许重复.(Java TreeMap的默认实现不允许重复)

还有一些特殊情况需要考虑,例如,如果特定数据结构中的元素数量不受限制地增加或接近数据结构的基础部分的限制会怎么样？那些执行一些重新平衡或清理操作的摊销操作呢？

例如,在散列表中,当表中的元素数量变得足够大时,可以发生任意数量的冲突.另一方面,树插入(或删除)后通常需要重新平衡过程.

所以,如果你有类似缓存的东西(例如有界的元素数量,或者已知大小),那么散列表可能是你最好的选择; 但是,如果你有更像字典的东西(例如,填充一次,并且多次查找),那么我会使用一棵树.

然而,这只是在一般情况下(没有给出任何信息).您必须了解在决定使用哪种数据结构时如何做出正确选择的过程.

当我需要一个多映射(范围查找)或分类扁平化集合时,它不能是一个哈希表.

Answer 3

两者之间的最大差异是实现中使用的底层结构.

HashMaps使用数组和散列函数来存储元素.当您尝试插入或删除数组中的项时,哈希函数会将键转换为数组中应存储对象的索引(忽略冲突).虽然哈希映射通常非常快,因为它们不需要迭代大量数据,但它们在填充时会变慢,因为它们需要将所有键/值复制到新数组中.

TreeMaps将数据存储在已排序的树结构中.虽然这意味着他们永远不必分配更多空间并复制到它,但操作需要迭代已经存储的部分数据.有时会改变大量的结构.

当您不需要排序时,两个Hashmaps中通常会有更好的性能.