对比Vector、ArrayList、LinkedList有何区别 - 《java核心技术》笔记

1. 实现方式不同
   Vector是java早期提供的线程安全的动态数组，内部用对象数组来保存数据，可以自动增加容量。

ArrayList是应用更加广泛的动态数组实现，本身不是线程安全。也可以自动扩容，Vector会增加1倍，ArrayList则是50%。

LinkedList是双向链表，不能自动扩容，也是线程不安全的。

Vector和ArrayList作为动态数组，其内部元素是以数组形式顺序存储的，除了头尾插入删除外其他位置性能较差。LinkedList进行节点插入删除则高效，但是随机访问性能比动态数组慢。

可以看到java的集合框架，Collection是所有集合的根，扩展开来三大类：

• List，有序集合。
• Set，没有重复元素。
• Queue/Deque，队列结构，支持FIFO、LIFO等特定行为。

TreeSet实际默认是利用TreeMap实现的，创建了一个Dummy对象“PRESENT”作为value。同理HashSet也是以HashMap为基础实现的。

对于非线程安全的类，java也在Collections工具类中提供了一系列的synchronized方法，比如static <T> List<T> synchronizedList(List<T> list)，使用方式：List list = Collections.synchronizedList(new ArrayList());，是将每个基本方法都通过synchronized添加基本的同步支持。

2. 排序方法

• 太小的数据，使用二分插入排序；
• 对于原始数据类型，使用双轴快排；
• 对于对象数据类型，使用TimSort，思想上也是一种归并和二分插入排序结合的优化排序算法，简单来说是查找数据集中已经排好序的分区，然后合并分区。