对比Vector、 ArrayList、 LinkedList有何区别
对比Vector、 ArrayList、 LinkedList有何区别
对比Vector、 ArrayList、 LinkedList有何区别？
这三者都是实现集合框架中的List，也就是所谓的有序集合，因此具体功能也比较近似，比如都提供按照位置进行定位、添加或者删除的操作，都提倛迭代器以遍历其內容等。但因为具体的设计区别，在行为、性能、线程安全等方面，表现又有很大不同。
Vector 是 Java 早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，同步有额外开销，Vector 内部是使用对象数组保存数据，也可以根据需要自动增加容量，当数组已满时，会创建新的数组，并拷贝原数组数据。
ArrayList 是应用更广泛的动态数组，本身不是线程安全的，与 Vector 相似， ArrayList 也是可以根据需要调整容量，不过两者间的调整有区别，Vector 在扩容时提高一倍， ArrayList 则是增加 50%。
LinkedList 是 Java 提供的双向链表，所有它不需要调整容量，它也不是线程安全的。
Vector、 ArrayList、 LinkedList均为线型的数据结构，但是从实现方式与应用场景中又存在差别,可以从下面几个方面总结。
底层实现方式
ArrayList内部用数组来实现；LinkedList内部采用双向链表实现；Vector内部用数组实现。
读写机制
ArrayList在执行插入元素是超过当前数组预定义的最大值时，数组需要扩容，扩容过程需要调用底层System.arraycopy()方法进行大量的数组复制操作；在删除元素时并不会减少数组的容量 （如果需要缩小数组容量，可以调用trimToSize()方法）；在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
LinkedList在插入元素时，须创建一个新的Entry对象，并更新相应元素的前后元素的引用；在查找元素时，需遍历链表；在删除元素时，要遍历链表，找到要删除的元素，然后从链表上将此元 素删除即可。
Vector与ArrayList仅在插入元素时容量扩充机制不一致。对于Vector，默认创建一个大小为10的Object数组，并将capacityIncrement设置为0；当插入元素数组大小不够时，如 果capacityIncrement大于0，则将Object数组的大小扩大为现有size+capacityIncrement；如果capacityIncrement<=0,则将Object数组的大小扩大为现有大小的2倍。
读写效率
ArrayList对元素的增加和删除都会引起数组的内存分配空间动态发生变化。因此，对其进行插入和删除速度较慢，但检索速度很快。
LinkedList由于基于链表方式存放数据，增加和删除元素的速度较快，但是检索速度较慢。
线程安全性
ArrayList、 LinkedList为非线程安全；
Vector是基于synchronized实现的线程安全的ArrayList。
单线程应尽量使用ArrayList， Vector因为同步会有性能损耗；即使在多线程环境下，我们可以利用Collections这个类中为我们提供的synchronizedList(List list)方法返回一个 线程安全的同步列表对象。
- https://www.coursera.org/learn/algorithms-part1
- http://hg.openjdk.java.net/jdk/jdk/file/bf9177eac58d/src/java.base/share/classes/java/util/TreeSet.java
- http://mail.openjdk.java.net/pipermail/core-libs-dev/2018-January/051000.html
Java 集合框架
image
- List，也就是我们前面介绍最多的有序集合，它提供了方便的访问、插入、删除等操作
- set,set是不允许重复元素的，这是和L最明显的区别，也就是不存在两个对象 equals返回true。我们在日常开发中有很多需要保证元素唯一性的场合。
- Queue/ Deque，则是Java提供的标准队列结构的实现，除了集合的基本功能，它还支持类似先入先出（FFO, First-in- First-Out）或者后入先岀（LIFO,Last-In- First out）等特定行为。这里不包括 BlockingQueue，因为通常是并发编程场合，所以被放置在并发包里。
Set 实现
- TreeSet支持自然顺序访问，但是添加、删除、包含等操作要相对低效（log(n)时间）。
- HashSet则是利用哈希算法，理想情况下，如果哈希散列正常，可以提供常数时间的添加、删除、包含等操作，但是它不保证有序。
- LinkedHashSet，内部构建了一个记录插入顺序的双向链表，因此提供了按照插入顺序遍历的能力，与此同时，也保证了常数时间的添加、删除、包含等操作，这些操作性能略低于HashSet，因为需要维护链表的开销。
- 在遍历元素时， HashSet性能受自身容量影响，所以初始化时，除非有必要，不然不要将其背后的HashMap容量设置过大。而对于LinkedHashSet，由于其内部链表提供的方便，遍历性能只和元素多少有关系
Collections 工具类
对于java.util.concurrent里面的线程安全容器，我在专栏后面会去介绍。但是，并不代表这些集合完全不能支持并发编程的场景，在Collections工具类中，提供了一系列的synchronized方法。
static <T> Lis<T> synchronizedLis(Lis<T> list)
线程安全集合
List list = Collections.synchronizedLis(new ArrayList());
