Java中的List你真的会用吗？

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

典型回答

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

• Vector是java早期提供线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步有额外的开销。Vector内部是使用自动增加的容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
• ArrayList是应用更加广泛的动态数组实现方式，它本身不是线程安全的，所以性能要好很多。与Vectro近似，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 <T> List<T> synchronizedList(List<T> list)

欢迎大家来到IT世界,在知识的湖畔探索吧!

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

欢迎大家来到IT世界,在知识的湖畔探索吧!List list = Collections.synchronizedList(new ArrayList());

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

java提供的默认排序算法

这个问题本身就是有点陷阱的意味，因为需要区分是 Arrays.sort() 还是 Collections.sort() （底层是调用 Arrays.sort()）

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