我们在日常工作中，能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同，比如我最早学习的C语言，需要自己实现很多基础数据结构，管理和操作会比较麻烦。相比之下，Java则要方便的多，针对通用场景的需求，Java提供了强大的集合框架，大大提高了开发者的生产力。

那么今天学习下有关集合框架方面的问题，对比Vector、ArrayList和LinkedList有何区别？

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

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

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

LinkedList顾名思义是Java提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的。

知识扩展

不同容器类型适合的场景：

  • Vector和ArrayList作为动态数组，其内部元素以数组形式顺序存储，所以非常适合随机访问的场合。插入和删除元素往往性能会相对较差（不包括尾部），比如我们在中间位置插入一个元素，需要移动后续所有元素。
  • 而LinkedList进行节点插入、删除却要高效得多，但是随机访问性能要比动态数组慢。

为了对集合框架有一个整体的认识，我画了一个简要的类图：

image.png

我们可以看到Java的集合框架，Collection接口是所有集合的根，然后扩展开提供了三大类集合，分别是：

  • List，也就是我们前面介绍最多的有序集合，它提供了方便的访问、插入和删除等操作。
  • Set，不允许有重复元素，也就是不存在两个对象equals返回true。适合日常开发中需要保证元素唯一性的场合。
  • Queue/Deque，则是Java提供的标准队列结构的实现，除了集合的基本功能，它还支持类似先进先出或者后进先出等特性。

Java的默认排序算法，具体是什么排序方式以及设计思路？

这个问题本身就是有点陷阱的味道，因为需要区分是Arrays.sort() 还是 Collections.sort()；什么数据类型；多大的数据集（太小的数据集，复杂排序是没必要的，Java会直接进行二分插入排序）等。

  • 对于原始数据类型，目前使用的是双轴快速排序，是一种改进的快速排序算法。
  • 对于对象数据类型，目前则是使用TimSort，思想上也是一种归并和二分插入排序结合的优化排序算法。
  • Java8引入了并行排序算法，对于数万，数百万的数据集来说，可以极大提高性能，它很依赖处理器和系统环境。