目录
- Set
- HashSet
- 有序非线程安全 LinkedHashSet
- 有序线程安全 ConcurrentLinkedHashSet
- LinkedHashSet vs TreeSet
- 深入解析
- 1. LinkedHashSet
- 2. TreeSet
- 参考资料
Set
HashSet
Java中的Set集合的核心特性就是不允许包含重复的元素。它是一个不允许存储重复对象且不保证顺序的集合。
唯一性: Set集合中的每个元素都是唯一的,如果尝试添加一个已存在的元素,该操作会失败或被忽略。即使是 null 值也只能包含一个。
无序性: 大多数Set的实现类(如HashSet)不保证元素的顺序,即元素在集合中的存储和返回顺序可能与添加顺序不同。
有序非线程安全 LinkedHashSet
LinkedHashSet 是有序的,它维护插入顺序,同时不是线程安全的。要使其在多线程环境中使用,需要使用 Collections.synchronizedSet() 将其包装起来,或者使用 ConcurrentLinkedHashSet 等线程安全的集合类。
有序线程安全 ConcurrentLinkedHashSet
或者使用Collections.synchronizedSet() 包装LinkedHashSet
您好!很高兴为您对比 LinkedHashSet 和 TreeSet。它们都是 Java 集合框架中的 Set
接口实现,但各自在底层实现、存储顺序和性能上有很大的不同。
LinkedHashSet vs TreeSet
特性 | LinkedHashSet | TreeSet |
---|---|---|
底层数据结构 | 哈希表(HashMap ) + 双向链表 |
红黑树(NavigableMap / TreeMap ) |
存储顺序 | 维护元素的插入顺序(有序) | 维护元素的自然排序或定制排序(有序) |
是否排序 | 否(按插入顺序遍历,但元素本身无排序) | 是(元素按大小排序) |
允许 null 元素 |
允许一个 null 元素 |
不允许(在 Java 7 之后,TreeSet 不允许 null 元素,否则会抛出 NullPointerException ) |
性能 | 插入、删除、查找操作的平均时间复杂度为 $O(1)$ | 插入、删除、查找操作的时间复杂度为 $O(\log n)$ |
使用场景 | 需要快速的插入/查找,并且要求遍历时保持元素添加的先后顺序。 | 需要对存储的元素进行自动排序,并支持范围查询、取最大/最小等操作。 |
深入解析
1. LinkedHashSet
- 如何保持顺序? 它在
HashSet
的基础上增加了一个双向链表,这个链表会记录元素的插入顺序。因此,当你遍历LinkedHashSet
时,元素会按照它们被添加到集合中的顺序出现。 - 性能优势: 继承了哈希表的优点,提供极快的 $O(1)$ 平均性能。
2. TreeSet
- 如何保持顺序? 它的底层是红黑树,这是一种自平衡二叉查找树。它确保元素在任何时候都处于排序状态。
- 自然排序: 元素需要实现
Comparable
接口。 - 定制排序: 可以在构造
TreeSet
时传入一个Comparator
。
- 自然排序: 元素需要实现
- 性能特点: 由于是基于树结构,所有基本操作的时间复杂度都是 $O(\log n)$,虽然比
LinkedHashSet
慢,但这是维持有序性的代价。 - 特殊能力: 作为
SortedSet
和NavigableSet
的实现,它提供了许多额外的功能,例如获取小于/大于某个元素的子集、获取最大/最小元素等。
总结来说:
- 如果您的主要需求是高性能且需要保持插入顺序,请使用 LinkedHashSet。
- 如果您的主要需求是让元素自动排序,请使用 TreeSet。
您目前在开发中更倾向于使用哪一个呢?我可以提供一些它们具体的使用代码示例。