Java 中的集合主要分为三类：Set(集)，List(列表)，Map(映射)。Set 集合是比较简单的一种集合。主要实现类有 HashSet 和 TreeSet。Set 集合中的对象的时无序的，并且不会重复的。List 集合是以线性存储元素的，主要的实现类有 ArrayList 和 LinkedList。List 集合的元素，是有序的并且可重复的。
HashSet
- HashSet 的底层实现是 HashMap 的 keySet()。
- HashSet 是按照 Hash 算法来存储和读取元素的，存取速度较快。访问成本是O(1)。
- HashSet 的元素可以为 null。
TreeSet
- TreeSet 的底层实现是 TreeMap。
- TreeSet 的元素不允许为 null。
ArrayList
- ArrayList 的底层实现是一个动态数组。我们知道，数组一旦初始化之后，长度就不可变化。这里的动态数组，是指重新生成一个数组，并把之前的数组内容 copy 过去。
- ArrayList 中插入和删除元素的速度较慢，因为涉及到数组的元素移动。
- ArrayList 的元素也可以是 null。
LinkedList
- LinkedList 的底层实现是基于双向链表的。
- LinkedList 的插入和删除速度由于 ArrayList, 读取速度比 ArrayList 差。
- LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
- get方法，利用二分法来查找元素。
区别
| 名称 | 底层实现 | 增删 | 查 | 线程安全 | 有序 | 元素可重复 | 元素可为空 |
|---|---|---|---|---|---|---|---|
| HashSet | HashMap | 较快 | 较快 | 否 | 否 | 否 | 是 |
| TreeSet | TreeMap | 较慢 | 较慢 | 否 | 是 | 否 | 否 |
| ArrayList | 动态数组 | 较慢 | 较快 | 否 | 是 | 是 | 是 |
| LinkedList | 双向链表 | 较快 | 较慢 | 否 | 是 | 是 | 是 |
时间复杂度
| 对象 | add方法 | get方法 | contains方法 |
|---|---|---|---|
| HashSet | O(1) | O(1) | O(1) |
| TreeSet | O(logn) | - | O(logn) |
| ArrayList | O(1) | O(1) | O(n) |
| LinkedList | O(1) | O(1) | O(n) |
总结
- 集合元素可重复，使用 List。反之使用 Set。
- 查询操作较多，建议使用 ArrayList。
- 增删元素较多，建议使用 LinkedList。