Java中的List你真的会用吗？

最近来了一个实习生，小强问他关于java中list的用法，他很快答上来。然后问他arraylist、vector和linkedList的区别，他就有点懵了，其实小强也不能回答的非常完善，于是整理出来和大家一起进阶学习。

典型回答

Vector、ArrayList和LinkedList三者都是实现集合框架中的List，也就是所谓有序集合，因此具体功能比较近似，比如都提供按照位置进行定位、添加或删除的操作，都提供迭代器以遍历其内容等。但因具体的设计区别，在性能、线程安全等方面，表现有很大不同。

• Vector是java早期提供线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步有额外的开销。Vector内部是使用自动增加的容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
• ArrayList是应用更加广泛的动态数组实现方式，它本身不是线程安全的，所以性能要好很多。与Vector近似，ArrayList也是 可以根据需要调整容量，不过两者的调整逻辑有所区别，Vector在扩容时会提高一倍，而ArrayList则是增加50%
• LinkedList是java提供的双向链表，它不需要上面两种调整容量，它也不是线程安全的。

补充

• Vector和ArrayList作为动态数组，其内部元素以数组形式顺序存储，所以非常适合随机访问的场合。除了尾部插入和删除元素，比如在中间位置插入一个元素，需要移动后续元素。
• LinkedList进行节点插入、删除却高效很多，但是随机访问的性能则要比动态数组慢很多。

排序算法

内部排序，至少掌握基础算法如归并排序、交换排序（冒泡、快排）、选择排序、插入排序等。

外部排序，掌握利用内存和外部存储处理超大数据集，至少要理解过程和思路。

比如哪些是排序是不稳定的呢（快排、堆排），或者思考稳定意味着什么； 对不同数据集，各种排序的最好或最差情况； 从某个角度如何进一步优化（比如空间占用，假设业务场景需要最小辅助空间，这个角度堆排序就比归并优异）等

集合框架

Collection接口是所有集合的根，然后提供3大集合：

• List：提供方便的插入、删除和访问操作
• Set：不允许重复元素
• Queue、Deque：支持FIFO或LIFO

set的底层实现都是map，TreeSet 代码里实际默认是利用 TreeMap 实现的，Java 类库创建了一个 Dummy 对象“PRESENT”作为 value，然后所有插入的元素其实是以键的形式放入了 TreeMap 里面；同理，HashSet 其实也是以 HashMap 为基础实现的！

Set

• TreeSet：支持自然顺序访问，但是添加、删除、包含等操作要相对低效(log(n))时间
• HashSet 则是利用哈希算法，理想情况下，如果哈希散列正常，可以提供常数时间的添加、删除、包含等操作，但是它不保证有序
• LinkedHashSet，内部构建了一个记录插入顺序的双向链表，因此提供了按照插入顺序遍历的能力，与此同时，也保证了常数时间的添加、删除、包含等操作，这些操作性能略低于 HashSet，因为需要维护链表的开销

线程安全

以上集合类非线程安全，在Collections工具类中，提供了一系列synchronized方法

static  List synchronizedList(List list)

可以用类似方式实现线程安全集合：

List list = Collections.synchronizedList(new ArrayList());

它的实现，基本就是将每个基本方法，比如 get、set、add 之类，都通过 synchronizd 添加基本的同步支持，非常简单粗暴，但也非常实用。注意这些方法创建的线程安全集合，都符合迭代时 fail-fast 行为，当发生意外的并发修改时，尽早抛出 ConcurrentModificationException 异常，以避免不可预计的行为。