Vector、ArrayList、LinkedList 有何区别

java针对通用场景的需求，提供了强大的集合框架，提高了开发者的生产力。

• Vector是线程安全的动态数组，内部使用对象数组保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。

• ArrayList是应用更加广泛的动态数组实现，本身不是线程安全，所以性能要好很多。与Vector区别是扩容增加50%，Vector扩容会提高1倍。

• LinkedList双向链表，不需要调整容量，线程不安全。

分析：

• Vector和ArrayList作为动态数组，内部元素是以数组形式顺序存储，所以适合随机访问的场合。除了尾部插入和删除元素，性能往往相对较差，比如我们在中间位置插入一个元素，需要移动后续所有元素。

• LinkedList进行节点插入、删除高效的多，但是随机访问性能要比动态数组慢。

675536edf1563b11ab7ead0def1215c7.png

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

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

我们需要对各种具体集合实现，至少了解基本特性和典型使用场景，以Set的几个实现为例：

• TreeSet支持自然顺序访问，但是添加、删除、包含等操作相对低效（log（n）时间）。
• HashSet利用哈希算法，如果哈希散列正常，可以提供常数时间的添加、删除、包含等操作，但是它不保证有序。
• LinkedHashSet，内部构建了一个记录插入顺序的双向链表，因此提供了按照插入顺序遍历的能力，为了保证常数时间的添加、删除、包含等操作，性能略低于HashSet，因为链表维护需要开销。
• 在遍历元素时，HashSet性能受自身容量影响，所以初始化时，除非有必要，不然不要将其背后的HashMap容量设置过大。而对于LinkedHashSet，由于其内部链表提供的方便，遍历性能只和元素多少有关系。