【Java核心-基础】集合 Collection

抽象类 AbstractList、AbstractSet、AbstractQueue 包含了这些接口的通用部分。

 

List

List 是有序集合，提供了方便的访问、插入、删除等操作。

ArrayList、LinkedList、Vector 都实现了 List 接口

它们的设计目标不同，具体行为、性能和线程安全方面也不同。

 

ArrayList

这是应用最广泛的动态数组。非线程安全；扩容时会增加 50%

扩容方式就是新建一个更大的内部数组，将原内部数组的数据拷贝到新数组中

 

Vector

这是Java早期提供的线程安全的动态数组。扩容时会增加 1倍。

扩容方式与 ArrayList 相同

如果没有线程安全的需求，建议不要使用该类，以避免同步开销。

 

LinkedList

这是双向链表。非线程安全；不需要像ArrayList那样新建内部数组式的扩容

 

ArrayList 和 Vector 因为内部是数组，所以非常适合随机访问。除了对尾部元素的插入和删除，性能都较差。

LinkedList 的随机访问效率较差，但是元素插入、删除操作更高效。

 

Set

Set 不允许存在重复元素，即任意两个元素 equals 返回 false

 

HashSet

HashSet 内部就是一个 HashMap。

不保证有序。

理想情况下，如果哈希散列正常，可提供常数时间的添加、删除、包含等操作

 

LinkedHashSet

LinkedHashSet 内部就是一个 LinkedHashMap。

LinkedHashMap 内部用双向链表记录了元素的“访问”顺序，可以支持对 LinkedHashSet 按照访问顺序遍历。
put、get、compute等相关操作都属于“访问”
最不常被访问的元素排在最前

 

理想情况下也能提供常数时间的添加、删除、包含等操作。

因为需要维护链表，所以性能略低于 HashSet。

也因为这个内部链表，LinkedHashSet 的遍历性能只与元素数量有关。而 HashSet 的遍历性能受自身容量影响，容量过大，性能会降低。

 

TreeSet

TreeSet 内部就是一个 TreeMap。

支持自然顺序访问，但是添加、删除、包含等操作效率较低（log(n)）

 

Queue / Deque

Queue / Deque 是队列结构。Queue 支持先入先出（FIFO），Deque 支持后入先出（LIFO）。

Stack vs Deque：两者都是“栈”。Stack 是Java早期的集合类。如果你需要的就是一个“栈”，即数据后入先出，则选 Deque。这也是面向接口编程的更优选择。