一、ArrayList和LinkedList的区别?
- ArrayList: 基于数组(需要一块连续的内存空间); 一般情况查询效率高(适合下标访问)
- 但:如果使用尾插法,并初始化合适的容量;其写入速度,甚至超过LinkedList(需要创建大量Node对象);
- 扩容:如果数组不够,则新建一个更大的数组,将原数据拷贝心的数组中;
- 扩容因子:大约1.5;原数组长度右移一位 + 加原数组的长度;
- 如果在数据中间插入、删除:会造成后续元素的集体挪动,影响性能;
- 时间复杂度:O(1);通过下标查找一次即可;
- LinkedList:基于链表(不需要连续内存);一般情况增删效率更高(只需修改前后指针,即可新增、删除)
- 其写入、删除性能消耗:在于遍历数据节点(总得先找到元素,才能改);
- 必须使用iterator(指针随之移动,无需从起点重新开始)
- 不要使用for循环:每次get(i),都需要对list重新遍历(每次都得从头节点开始查找);
- 不要使用IndexOf:当元素不存在,会遍历整个list;
- 还额外实现了Deque接口,其可以当作队列来使用;
- 时间复杂度:O(N);需要遍历链表节点;
二、List在循环过程中删除元素,导致元素个数改变,从而报错?
- 采用Iterator.remove方法;
三、CopyOnWriteArrayList底层原理是什么?
- 1、底层结构:依旧是数组;其写操作,会复制一个新数组(长度:原长度+1);在新的数组做写操作;读操作在原数组进行;
- 2、写操作会加锁:在新数组上,加一个公平锁(防止并发写入,导致数据被覆盖而丢失);
- 3、写操作结束后,将指向原数组的指针 指向新数组;
注释:
- 优点:允许在写操作时,读取数据,提高了读性能(适合读多写少的场景);
- 时间复杂度:O(1);
- 缺点:比较占内存;读取到的可能不是,最新的实时数据(不适合实时性要求很高的场景);
- 当有线程对其频繁变更操作时,将拷贝一个新数组,存放新字段,并加锁;因此性能很差;
四、Victor:数组结构,线程安全;
五、如何保证ArrayList线程安全?
- Collections.synchronizedList(new ArrayList<>())
- 对读操作采用了synchronized
六、如何对集合排序?
- 实现Comparable接口,重写compareTo()方法(泛型对象实现Comparable接口,集合存入对象):
- 支持:TreeSet、ArrayList LinkedList(集合必须调用Collections.sort()方法,否则按写入顺序)
- 不支:HashSet
- 实现Comparator接口,重写compare()方法(通过调用集合的sort方法,传入集合,实现排序接口的规则对象):
- 支持:ArrayList LinkedList(调用集合工具类sort方法)
- 不支持:HashSet
- 二者比较:Comparator排序规则独立,耦合性更低。
时间复杂度:



