非线程安全集合浅谈

Java 的集合框架大体分为四种数据结构——线性表、映射表、集合、队列。

集合框架分析

Collection 接口是集合框架的根，然后扩展开提供了三大类集合：

• List ： 有序集合，提供了方便的访问、插入、删除等操作。
• Set ：不允许有重复元素的集合。适合在日常开发中用来保持元素的唯一性的场合。
• Queue/Dueue：是 Java 提供的标准队列接口。

每种集合的通用逻辑都被抽象到对应的 abstract 类中。

具体集合直接也不是互相独立的，比如 LinkedList 既是 List 也是 Dueue。而 Set 则是包装 Map 对象，使用一个 dummy 对象 “PRESENT” 作为 value，插入元素作为 key 的方式插入到 Map 中实现的。

Vector、ArrayList、LinkedList 的区别

Vector 是Java 早期提供的线程安全的动态数组，现在不建议再使用。其实现方式和 Collections.synchronizedList() 差不多，都是提供一个 get、set、size 等方法的粗粒度锁。

Vector、ArrayList 底层是数组，适合利用数组下标随机访问，可以充分利用 CPU 的缓存对数组结构的高缓存命中率。

其具备数组的大部分特点，如在不需要触发扩容缩容的情况下，在数组末尾增加删除数据性能很高，但是在数组中间增加删除数据效率打折扣。

LinkedList 底层是双向链表，Java 提供的 API 中大部分链表也是双向链表。其特点也是
链表的特点，在已知节点的前后插入删除节点的效率是常数级。查看其源码，可以知道 get(int index) 方法做了一点优化，先判断待获取的节点是靠近链表前段还是后段再决定从头部还是尾部开始遍历查找节点。

Vector、ArrayList 对内存要求比较苛刻，需要一整段连续的内存，即使 JVM 中存在 1GB 可用内存，但是这 1GB 内存是零散的话，仍然不能申请到这个 1GB 的顺序表。而对比下来 LinkedList 则容易在频繁的插入删除操作中造成内存碎片。

在内存的使用上，LinkedList 和 ArrayList 并没有说谁更优谁更差。ArrayList 底层是数组结构，比双向链表少了 2n 个指针，如果一个指针是 4 个字节长度，那就比双向链表在指针的开销上节省了 8n 个字节。但是数组采用的是动态扩容，Vector 每次扩容后容量翻倍，ArrayList 每次扩容后容量是原来的 1.5 倍；换成实际的数字体验会直观一些，比如原来的数组分配了 1GB 的空间刚好用满，此时只需要再插入一个记录，而 Vector 扩容后却会占用 2GB 的空间、ArrayList 占用 1.5 GB。仅仅是增加一个对象，顺序表增加了 500MB 的内存消耗，而链表仅需分配这个对象所需的内存即可。

Set

• TreeSet：

底层数据结构是红黑树，支持自然顺序访问，添加、删除、包含操作的效率是 O(logn)。

而 logn 级别的效率其实算不错了，不一定比常数级别的操作慢，毕竟有些常数级别的操作，其常数可能是一个较大的常数，如 O(1000) 也是 O(1) 级别，而 O(logn）可能只需要个位数次数的操作。

跟红黑树相似效率的算法也有，比如 AVL 树、跳表等数据结构。AVL 的绝对平衡导致在维护平衡上需要比红黑树多更多的开销，而我们毕竟是在写工业环境下的代码，不需要这么绝对平衡的结构，所以在工业上红黑树会比 AVL 树高效一些。

而跳表的插入、查找、删除效率都跟红黑树一样的级别，且其提供的 logn 级别定位到元素，然后以常数的效率遍历元素区间的功能，是红黑树不能提供的。以跳表为底层数据结构实现的 iterator 效率会比单纯使用红黑树的实现好很多。

• LinkedHashSet：

内部提供了一个记录插入顺序的双向链表，因此提供了按照插入顺序进行遍历的能力，双向链表 + hash 的组合，使得它兼具两者的优点——常数时间的添加、删除、包含等操作，但是性能略低于 hashset，因为要维护链表的开销，如果没有对顺序的需求，还是应该选用 hashset。

顺序表排序

对于顺序表排序，是先生成一份待排序数组，然后对待排序数组调用 Arrays.sort() 方法进行排序，然后再拷贝回原顺序表的。

其中 ArrayList 直接复制对象内部持有的数组，LinkedList 则是把内部链表整理到一个数组中来生成待排序数组。

Arrays.List() 排序是区分原始数据类型和对象类型的。

• 对于原始数据类型，目前使用的是双轴快排，早期版本是传统快排。这种双轴快排提高了在待排数组中与轴对象相等的元素有多个时的排序效率。

• 对于对象数据类型，目前使用的是 TimSort，思想上是一种归并和二分插入排序结合的优化排序算法，简单的思路是查找数据中已经排序好的分区（这里叫做 run），然后合并这些分区来达到排序的目的。

• Java 8 引入了并行排序算法，底层是 fork-join 框架，在多核环境下处理几万甚至上百万的大数据集时性能相比串行排序好很多。

集合的演进

stream 类是 Java 8 新引入的处理集合的工具类，功能是 scala 版 stream 的小阉割，但仍然非常强大，是我最爱的功能之一。

stream 采用函数式编程思想，配合 Optional 类一起使用可以极大挑逗 Java 程序员的幸福感。同时 stream 也利用了 Java 8 新增的 default 关键字，将功能嵌入在接口中而不是侵入原有的集合来做扩展。

Java 9 中提供的静态工厂方法，比如 List.of() 、Set.of() 弥补了一些 Collections 工具类的不足。接受参数构造不可变类的代码写起来会更舒服和简洁。

另外 List.of() 虽然支持动态参数，但是 Java 仍然提供一系列特定参数的方法，因为 JVM 在处理边长参数时会有额外开销，如果我们要实现性能敏感的 API ，可以考虑到这一点。