栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

java基础-集合-List

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

java基础-集合-List

一、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排序规则独立,耦合性更低。

时间复杂度:

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/973453.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号