对比Vector、ArrayList、LinkedList有何区别 - 《java核心技术》笔记
- 实现方式不同
Vector是java早期提供的线程安全的动态数组,内部用对象数组来保存数据,可以自动增加容量。
ArrayList是应用更加广泛的动态数组实现,本身不是线程安全。也可以自动扩容,Vector会增加1倍,ArrayList则是50%。
LinkedList是双向链表,不能自动扩容,也是线程不安全的。
Vector和ArrayList作为动态数组,其内部元素是以数组形式顺序存储的,除了头尾插入删除外其他位置性能较差。LinkedList进行节点插入删除则高效,但是随机访问性能比动态数组慢。
可以看到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添加基本的同步支持。
- 排序方法
- 太小的数据,使用二分插入排序;
- 对于原始数据类型,使用双轴快排;
- 对于对象数据类型,使用TimSort,思想上也是一种归并和二分插入排序结合的优化排序算法,简单来说是查找数据集中已经排好序的分区,然后合并分区。