对比Vector、ArrayList、LinkedList有何区别 - 《java核心技术》笔记

  1. 实现方式不同
    Vector是java早期提供的线程安全的动态数组,内部用对象数组来保存数据,可以自动增加容量。

ArrayList是应用更加广泛的动态数组实现,本身不是线程安全。也可以自动扩容,Vector会增加1倍,ArrayList则是50%。

LinkedList是双向链表,不能自动扩容,也是线程不安全的。

Vector和ArrayList作为动态数组,其内部元素是以数组形式顺序存储的,除了头尾插入删除外其他位置性能较差。LinkedList进行节点插入删除则高效,但是随机访问性能比动态数组慢。

675536edf1563b11ab7ead0def1215c7
可以看到java的集合框架,Collection是所有集合的根,扩展开来三大类:

  • List,有序集合。
  • Set,没有重复元素。
  • Queue/Deque,队列结构,支持FIFO、LIFO等特定行为。

TreeSet实际默认是利用TreeMap实现的,创建了一个Dummy对象“PRESENT”作为value。同理HashSet也是以HashMap为基础实现的。

对于非线程安全的类,java也在Collections工具类中提供了一系列的synchronized方法,比如static <T> List<T> synchronizedList(List<T> list),使用方式:List list = Collections.synchronizedList(new ArrayList());,是将每个基本方法都通过synchronized添加基本的同步支持。

  1. 排序方法
  • 太小的数据,使用二分插入排序;
  • 对于原始数据类型,使用双轴快排;
  • 对于对象数据类型,使用TimSort,思想上也是一种归并和二分插入排序结合的优化排序算法,简单来说是查找数据集中已经排好序的分区,然后合并分区。
comments powered by Disqus