Java Collection

Collection——狭义上的集合

接口Collection派生了三大类集合，分别是List、Set、Queue/Deque。

• List，有序集合，提供了访问、插入、删除等操作。
• Set，不允许重复元素的，这是和List最明显的区别，不存在两个对象equals返回true。在开发中有很多需要保证元素唯一性的场合可以使用。
• Queue/Deque，Java提供的标准队列结构的实现，除了集合的基本功能，它还支持类似先入先出（FIFO， First-in-First-Out）或者后入先出（LIFO，Last-In-First-Out）等特定行为。

Vector是Java早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，同步是有额外开销的。Vector内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。

ArrayList是应用动态数组实现，它本身不是线程安全的，性能要好很多。与Vector类似，ArrayList也是可以根据需要调整容量，不过两者的调整逻辑有所区别，Vector在扩容时会提高1倍，而ArrayList则是增加50%。

LinkedList是双向链表，它不需要像上面两种那样调整容量，它也不是线程安全的。这些集合不是完全孤立的，比如LinkedList，既是List，也是Deque。

TreeSet支持自然顺序访问，但添加、删除、包含等操作要相对低效（log(n)）。

HashSet利用哈希算法，理想情况下哈希散列正常，可以提供常数时间的添加、删除、包含等操作，但是它不保证有序。

LinkedHashSet内部构建了一个记录插入顺序的双向链表，因此提供了按照插入顺序遍历的能力，也保证了常数时间的添加、删除、包含等操作，这些操作性能略低于HashSet，因为需要维护链表的开销。

注：

• 每种集合的通用逻辑，都被抽象到相应的抽象类中，比如AbstractList就集中了各种List操作的通用部分。
• Vector和ArrayList非常适合随机访问的场合。LinkedList进行节点插入、删除却要高效得多，但是随机访问性能则要比动态数组慢。
• TreeSet代码里实际默认是利用TreeMap实现的，Java类库创建了一个Dummy对象“PRESENT”作为value，然后所有插入的元素其实是以键的形式放入了TreeMap里面；同理，HashSet也是以HashMap为基础实现的，它们是Map类的马甲。
• 在遍历元素时，HashSet性能受自身容量影响，所以初始化时最好不要将HashMap容量设置过大。而对于LinkedHashSet，由于其内部链表提供的方便，遍历性能只和元素多少有关系。

Java 8中支持了Lambda和Stream，相应的Java集合框架也进行了大范围的增强，支持类似为集合创建相应stream或者parallelStream的方法实现，方便地实现函数式代码。源码中这些API的设计和实现比较独特，它们不是实现在抽象类里面，而是以默认方法的形式实现在Collection这样的接口里。这是Java 8在语言层面的新特性，Java面向对象基本机制的演进允许接口实现默认方法，原来实现在类似Collections这种工具类中的方法，大多可以转换到相应的接口上。

Java 9中提供了一系列的静态工厂方法，比如List.of()、Set.of()，大大简化了构建小容器实例的代码量。业界实践发现相当一部分集合实例容量都非常有限，且在生命周期中并不会进行修改。通过各种of静态工厂方法创建的实例，还应用了一些最佳实践，比如它是不可变的，符合我们对线程安全的需求；它不需要考虑扩容，空间上更加紧凑等。阅读of方法的源码发现，Java已经支持可变参数（varargs），但官方类库还是提供了一系列特定参数长度的方法，看起来似乎非常不优雅，为什么呢？这其实是为了最优的性能，JVM在处理变长参数时会有明显的额外开销，如果你需要实现性能敏感的API，也可以参考。

Collection集合类都不是线程安全的，但并不代表这些集合完全不能支持并发编程的场景，在Collections工具类中提供了一系列的synchronized方法，但平常不推荐使用，同步控制粒度太大，不适合对性能要求较高的场景。

// 定义
static <T> List<T> synchronizedList(List<T> list)// 使用
List list = Collections.synchronizedList(new ArrayList());

实现原理是将方法（比如get、set、add等）通过synchronized添加同步原语。注意这些方法创建的线程安全集合，都符合迭代时fail-fast行为，当发生意外的并发修改时，尽早抛出ConcurrentModificationException异常，以避免不可预计的行为。

集合排序

集合具体使用哪种排序算法，需要区分是Arrays.sort()还是Collections.sort() （底层是调用Arrays.sort()）；什么数据类型；多大的数据集（太小的数据集，复杂排序是没必要的，Java会直接进行二分插入排序）等。

• 对于原始数据类型，目前使用的是所谓双轴快速排序（Dual-Pivot QuickSort，java/util/DualPivotQuicksort.java），早期版本是相对传统的快速排序。
• 对于对象数据类型，目前则是使用TimSort，它是一种归并和二分插入排序（binarySort）结合的优化排序算法（java/util/TimSort.java）。TimSort并不是Java独创的，它的思路是查找数据集中已经排好序的分区，然后合并这些分区来达到排序的目的。
• Java 8引入了并行排序算法（直接使用parallelSort方法），这是为了充分利用现代多核处理器的计算能力，底层实现基于fork-join框架，当处理的数据集比较小的时候，差距不明显，甚至还表现差一点；当数据集增长到数万或百万以上时，会有很大的提升，具体取决于处理器和系统环境。

Have Fun