TreeSet和LinkedHashSet以及TreeMap和LinkedHashMap相比，增加的成本是多少？

Question

LinkedHashSet - 这种实现避免了HashSet所提供的未指定的、通常混乱的排序，而又不会带来与TreeSet相关的成本增加。

对于LinkedHashMap与TreeMap也是如此。

这个成本增加（LinkedHashMap与TreeMap）到底是什么？

这是否意味着TreeSet需要更多的内存来存储每个元素？LinkedHashSet需要为两个额外的链接占用更多的内存，但是TreeSet需要额外的内存来存储Map.Entry元素对（因为它隐含地基于TreeMap），此外LinkedHashSet基于HashMap，其也有Map.Entry元素对的开销...

因此，区别在于添加新元素的速度（在TreeSet的情况下，由于某些“排序”，需要更长的时间）。

还有其他重要的成本增加吗？

- sdasda

---

TreeSet的插入或查找是O(log(n))。LinkedHashSet的插入或查找是O(1)。这就是它们之间的主要区别。 - JB Nizet

Answer 1

TreeSet/TreeMap 的操作（如 add(), contains() (对于 TreeSet), put(), containsKey() (对于 TreeMap) 等）具有更高的时间复杂度，因为它们需要对树中的元素进行寻址（或添加元素到树中），这需要对数时间，而 LinkedHashSet/LinkedHashMap 对于这些操作需要期望恒定时间。

在内存需求方面，差异非常小：

• TreeMap 条目包含键、值、3 个 Entry 引用（左、右、父）和一个布尔值。

• LinkedHashMap 条目包含键、值、3 个 Entry 引用（下一个、前一个、后一个）和一个整数。

- Eran

Answer 2

当遍历 HashSet 时，迭代顺序通常是对象哈希值的顺序，如果你想得到可预测的顺序，这种顺序通常没有太大用处。

如果合理的排序很重要，则通常需要使用 TreeSet，该集合按排序顺序进行迭代，但代价是维护排序的复杂度较高。

LinkedHashSet 可以作为中间方案解决 HashSet 迭代顺序看似不可预测的问题，通过使用插入顺序来确保迭代顺序至少是一致的。

- OldCurmudgeon