何时使用哈希映射或树映射?
我知道当我需要对元素进行排序时,可以使用TreeMap进行迭代。但是只有这些吗?在我只想查询映射或者一些特定的最优用途时,是否存在优化?
何时使用哈希映射或树映射?
我知道当我需要对元素进行排序时,可以使用TreeMap进行迭代。但是只有这些吗?在我只想查询映射或者一些特定的最优用途时,是否存在优化?
TreeMap
提供了保证 O(log n) 的查找时间(以及插入等操作),而 HashMap
则在哈希码适当地分散键的情况下提供 O(1) 的查找时间。
除非您需要对条目进行排序,否则我建议使用 HashMap
。当然也可以使用 ConcurrentHashMap
。我记不清它们之间的差异细节,但 HashMap
是一个完全合理的“默认”选项 :)
为了完整起见,我应该指出 Stack Overflow 上有一个关于各种映射内部的讨论。请参见此问题的评论,如果 bestsss 愿意,我将把它们复制到此答案中。
TreeSet
vs HashSet
”,但假设我经常进行集合交集操作。在这种情况下,即使您不明确使用它们的排序方式,拥有元素排序通常也是一种净胜利。 - phoojiLinkedHashMap
作为默认的Map
。它拥有更好和可预测的迭代(就像LinkedList),不会随着Java版本或HashMap实现而改变。 - bestsssO(n)<=T(n)<=O(1)
范围内,平均情况下的复杂度为 O(1 + n/k)
;然而,二叉搜索树(BST)执行搜索操作(查找),其复杂度在 O(n)<=T(n)<=O(log_2(n))
范围内,平均情况下的复杂度为 O(log_2(n))
。了解每种(和每一个)数据结构的实现对于理解操作的优点、缺点、时间复杂度和代码复杂度非常重要。O(n)<=T(n)<=O(1)
是正确的吗? - f.ardelianO(1) ≤ T(n) ≤ O(n)
,对于平衡树,应该是T(n) = O(log n)
(据我所记,常数可以从O符号中剥离)。 - ony这两者之间最大的区别在于实现时使用的底层结构。
HashMap使用数组和哈希函数存储元素。当您尝试在数组中插入或删除项目时,哈希函数将键转换为数组上的索引位置,对象被存储/应该存储在那里(忽略冲突)。虽然HashMap通常非常快,因为它们不需要迭代大量数据,但在填充时会变慢,因为它们需要将所有键/值复制到一个新数组中。
TreeMap使用排序树结构存储数据。虽然这意味着它们永远不需要分配更多空间并将数据复制到其中,但操作需要对已存储的部分数据进行迭代。有时要改变大量的结构。
在这两个中,如果您不需要排序,则HashMap通常具有更好的性能。
将新元素插入HashMap通常比将元素插入TreeMap要快得多。除非您需要对元素进行排序,否则建议使用HashMap。
不要忘记还有LinkedHashMap
,它几乎和HashMap
一样快,可以进行添加/包含/删除操作,但还保持插入顺序。
get()
函数的速度非常快,除非使用 accessOrder=true
来创建它,这时只需进行几个(6个)赋值和一个间接操作(接近于零)。LinkedHashMap 是我在 java.util 中最喜欢的结构。 - bestsss
TreeMap
是一种可导航的排序映射表,与其他地图有很大的区别。它有一些有趣的特性,例如基于当前键查找下一个/上一个值/键,但需要键的 [自然] 顺序,而HashMap
则基于哈希,所以直接比较并不合适。如果没有定义自然排序(类似于java.util.URL
),则无法实际使用TreeMap
。此外,对象比较通常比hashcode/equals
更慢。 - bestsss