【Java】List, Set, Queue, Map 区别?

目录

List, Set, Queue, Map 区别?

Collection和Collections

List

ArrayList 和 Array区别?

ArrayList与LinkedList区别?

ArrayList 能添加null吗?

ArrayList 插入和删除时间复杂度?

LinkedList 插入和删除时间复杂度?

LinkedList 为什么不能实现 RandomAccess 接口?

Set

Comparable和Comparator区别?

无序性和不可重复性

HashSet如何检查重复?

HashSet与HashMap区别

HashSet,LinkedHashSet,TreeSet 异同

Map

HashMap和Hashtable

HashMap和HashSet区别

ConcurrentHashMap和Hashtable?

HashMap与ConcurrentHashMap?

HashMap和TreeMap?

HashMap长度是2的幂次方?

HashMap多线程导致死循环

HashMap 为什么线程不安全?


List, Set, Queue, Map 区别?

  • List(对付顺序的好帮手): 存储的元素是有序的、可重复的。

  • Set(注重独一无二的性质): 存储的元素不可重复的。

  • Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序,存储的元素是有序的、可重复的。

  • Map(用 key 来搜索的专家): 使用键值对(key-value)存储,类似于数学上的函数 y=f(x),"x" 代表 key,"y" 代表 value,key 是无序的、不可重复的,value 是无序的、可重复的,每个键最多映射到一个值。

Collection和Collections

  • java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式,其直接继承接口有List与Set。

  • Collections则是集合类的一个工具类/帮助类,其中提供了一系列静态方法,用于对集合中元素进行排序、搜索以及线程安全等各种操作。

List

ArrayList 和 Array区别?

ArrayList 内部基于动态数组实现,比 Array(静态数组) 使用起来更加灵活:

  • ArrayList会根据实际存储的元素动态地扩容或缩容,而 Array 被创建之后就不能改变它的长度了。

  • ArrayList 允许你使用泛型来确保类型安全,Array 则不可以。

  • ArrayList 中只能存储对象。对于基本类型数据,需要使用其对应的包装类(如 Integer、Double 等)。Array 可以直接存储基本类型数据,也可以存储对象。

  • ArrayList 支持插入、删除、遍历等常见操作,并且提供了丰富的 API 操作方法,比如 add()remove()等。Array 只是一个固定长度的数组,只能按照下标访问其中的元素,不具备动态添加、删除元素的能力。

  • ArrayList创建时不需要指定大小,而Array创建时必须指定大小。

ArrayList与LinkedList区别?
  • 是否保证线程安全: ArrayListLinkedList 都是不同步的,也就是不保证线程安全;

  • 底层数据结构: ArrayList 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)

  • 插入和删除是否受元素位置的影响:

    • ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element)),时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

    • LinkedList 采用链表存储,所以在头尾插入或者删除元素不受元素位置的影响(add(E e)addFirst(E e)addLast(E e)removeFirst()removeLast()),时间复杂度为 O(1),如果是要在指定位置 i 插入和删除元素的话(add(int index, E element)remove(Object o),remove(int index)), 时间复杂度为 O(n) ,因为需要先移动到指定位置再插入和删除。

  • 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList(实现了 RandomAccess 接口) 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

  • 内存空间占用: ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

ArrayList 能添加null吗?

ArrayList 中可以存储任何类型的对象,包括 null 值。不过,不建议向ArrayList 中添加 null 值, null 值无意义,会让代码难以维护比如忘记做判空处理就会导致空指针异常。

ArrayList 插入和删除时间复杂度?

对于插入:

  • 头部插入:由于需要将所有元素都依次向后移动一个位置,因此时间复杂度是 O(n)。

  • 尾部插入:当 ArrayList 的容量未达到极限时,往列表末尾插入元素的时间复杂度是 O(1),因为它只需要在数组末尾添加一个元素即可;当容量已达到极限并且需要扩容时,则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中,然后再执行 O(1) 的操作添加元素。

  • 指定位置插入:需要将目标位置之后的所有元素都向后移动一个位置,然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素,因此时间复杂度为 O(n)。

对于删除:

  • 头部删除:由于需要将所有元素依次向前移动一个位置,因此时间复杂度是 O(n)。

  • 尾部删除:当删除的元素位于列表末尾时,时间复杂度为 O(1)。

  • 指定位置删除:需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置,因此需要移动平均 n/2 个元素,时间复杂度为 O(n)。

LinkedList 插入和删除时间复杂度?
  • 头部插入/删除:只需要修改头结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。

  • 尾部插入/删除:只需要修改尾结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。

  • 指定位置插入/删除:需要先移动到指定位置,再修改指定节点的指针完成插入/删除,因此需要移动平均 n/2 个元素,时间复杂度为 O(n)。

LinkedList 为什么不能实现 RandomAccess 接口?

RandomAccess 是一个标记接口,用来表明实现该接口的类支持随机访问(即可以通过索引快速访问元素)。由于 LinkedList 底层数据结构是链表,内存地址不连续,只能通过指针来定位,不支持随机快速访问,所以不能实现 RandomAccess 接口。

Set

Comparable和Comparator区别?
  • Comparable是“比较”的意思,而Comparator是“比较器”的意思;

  • Comparable是通过重写compareTo方法实现排序的,而Comparator是通过重写compare方法实现排序的;

  • Comparable必须在自定义类的内部实现排序方法,也就是说会修改原有的类,而Comparator是外部定义并实现排序的,不用修改原有的类。

无序性和不可重复性
  • 无序性不等于随机性 ,无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ,而是根据数据的哈希值决定的。

  • 不可重复性是指添加的元素按照 equals() 判断时 ,返回 false,需要同时重写 equals() 方法和 hashCode() 方法。

HashSet如何检查重复?
  • 向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。

  • HashSet 中的add ()方法会使用HashMap 的put()方法。

  • HashMap 的 key 是唯一的,HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。

HashSet与HashMap区别

HashSet,LinkedHashSet,TreeSet 异同
  • HashSetLinkedHashSetTreeSet 都是 Set 接口的实现类,都能保证元素唯一,并且都不是线程安全的。

  • HashSetLinkedHashSetTreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表(基于 HashMap 实现)。LinkedHashSet 的底层数据结构是链表和哈希表,元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树,元素是有序的,排序的方式有自然排序和定制排序。

  • 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景,LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景,TreeSet 用于支持对元素自定义排序规则的场景。

Map

HashMap和Hashtable
  • 线程是否安全: HashMap 是非线程安全的,Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。

  • 效率: 因为线程安全的问题,HashMap 要比 Hashtable 效率高一点。另外,Hashtable 基本被淘汰,不要在代码中使用它;

  • 对 Null key 和 Null value 的支持: HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个;Hashtable 不允许有 null 键和 null 值,否则会抛出 NullPointerException

  • 初始容量大小和每次扩充容量大小的不同: ① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

  • 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树),以减少搜索时间。Hashtable 没有这样的机制。

HashMap和HashSet区别

ConcurrentHashMap和Hashtable?

ConcurrentHashMapHashtable 的区别主要体现在实现线程安全的方式上不同。

  • 底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;

  • 实现线程安全的方式(重要):

    • 在 JDK1.7 的时候,ConcurrentHashMap 对整个桶数组进行了分割分段(Segment,分段锁),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。

    • 到了 JDK1.8 的时候,ConcurrentHashMap 已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;

    • Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

HashMap与ConcurrentHashMap?
  1. 都是 key-value 形式的存储数据;

  2. HashMap是线程不安全的,ConcurrentHashMap 在多线程环境下是线程安全的;

  3. HashMap 底层数据结构是数组 + 链表(JDK 1.8 之前)。JDK 1.8 之后是数组 + 链表 + 红黑树。当链表中元素个数达到 8 的时候,链表的查询速度不如红黑树快,链表会转为红黑树,红黑树查询速度快;

  4. HashMap 初始数组大小为 16(默认),当出现扩容的时候,以 0.75 * 数组大小的方式进行扩容;

  5. ConcurrentHashMap 在 JDK 1.8 之前是采用分段锁来现实的 Segment + HashEntry,Segment 数组大小默认是 16,2 的 n 次方;JDK 1.8 之后,采用 Node + CAS + Synchronized来保证并发安全进行实现。

HashMap和TreeMap?
  1. 存储结构:

    • HashMap 使用哈希表实现,通过键值对存储数据。

    • TreeMap 使用红黑树实现,按照键的顺序存储数据。

  2. 元素顺序:

    • HashMap 不保证元素的顺序。

    • TreeMap 根据键的顺序对元素进行排序存储。

  3. 性能:

    • HashMap 的存储和检索时间复杂度为 O(1),平均性能较高。

    • TreeMap 的存储和检索时间复杂度为 O(log N),平均性能较低。

  4. 使用场景:

    • HashMap 适用于需要快速插入和检索元素,并不关心元素的顺序。

    • TreeMap 适用于需要按照键的顺序进行存储和遍历的场景。

HashMap长度是2的幂次方?
  • 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。

  • 这个算法应该如何设计呢?

    • 我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。

  • 那为什么是两次扰动呢?

    • 这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的;

HashMap多线程导致死循环

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题,这是由于当一个桶位中有多个元素需要进行扩容时,多个线程同时对链表进行操作,头插法可能会导致链表中的节点指向错误的位置,从而形成一个环形链表,进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题,JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置,使得插入的节点永远都是放在链表的末尾,避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下,推荐使用 ConcurrentHashMap

HashMap 为什么线程不安全?

JDK1.7 及之前版本,在多线程环境下,HashMap 扩容时会造成死循环和数据丢失的问题。

数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在,这里以 JDK 1.8 为例进行介绍。

JDK 1.8 后,在 HashMap 中,多个键值对可能会被分配到同一个桶(bucket),并以链表或红黑树的形式存储。多个线程对 HashMapput 操作会导致线程不安全,具体来说会有数据覆盖的风险。

举个例子:

  • 两个线程 1,2 同时进行 put 操作,并且发生了哈希冲突(hash 函数计算出的插入下标是相同的)。

  • 不同的线程可能在不同的时间片获得 CPU 执行的机会,当前线程 1 执行完哈希冲突判断后,由于时间片耗尽挂起。线程 2 先完成了插入操作。

  • 随后,线程 1 获得时间片,由于之前已经进行过 hash 碰撞的判断,所有此时会直接进行插入,这就导致线程 2 插入的数据被线程 1 覆盖了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/462541.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Vue2(4)——iHRM组织架构

组织架构-树组件应用 树形组件-用层级结构展示信息,可展开或折叠。 属性设置 data(绑定数据)props(设置属性)- children(设置子节点的字段名)/ label(设置显示内容的字段名)default-expand-all(默认展开所有节点) 组织架构-树组件自定义结构 显示右侧结构 节点结…

Vue2(三):绑定样式、条件渲染(v-if,v-show)、列表渲染(v-for)、key的原理、列表过滤、列表排序

一、绑定样式 1.绑定class样式 (1)字符串写法 适用于&#xff1a;样式类名不确定&#xff0c;需要动态获取。 <div id"root"><div class"basic" :class"mood" click"changeMood">test</div><!-- class是原本的…

【Python】进阶学习:基于Numpy实现按指定维度拼接两个数组

【Python】进阶学习&#xff1a;基于Numpy实现按指定维度拼接两个数组 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448; 希…

第十三届蓝桥杯(C/C++ 大学B组)

目录 试题 A: 九进制转十进制 试题 B: 顺子日期 试题 C: 刷题统计 试题 D: 修剪灌木 试题 E: X 进制减法 试题 F: 统计子矩阵 试题 G: 积木画 试题 H: 扫雷 试题 I: 李白打酒加强版 试题 J: 砍竹子 试题 A: 九进制转十进制 九进制正整数 ( 2022 )转换成十进制等于多…

2000-2021年各省外商直接投资水平面板数据(含原始数据+计算结果)(无缺失)

2000-2021年各省外商直接投资水平面板数据&#xff08;含原始数据计算结果&#xff09;&#xff08;无缺失&#xff09; 1、时间&#xff1a;2000-2021年 2、指标&#xff1a;外商直接投资额&#xff08;万美元&#xff09;、外商直接投资额&#xff08;万元&#xff09;、国…

MySQL语法分类 DQL(4)聚合函数

为了更好的学习这里给出基本表数据用于查询操作 create table student (id int, name varchar(20), age int, sex varchar(5),address varchar(100),math int,english int );insert into student (id,name,age,sex,address,math,english) values (1,马云,55,男,杭州,66,78),…

2024年【危险化学品经营单位主要负责人】找解析及危险化学品经营单位主要负责人模拟考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 危险化学品经营单位主要负责人找解析考前必练&#xff01;安全生产模拟考试一点通每个月更新危险化学品经营单位主要负责人模拟考试题目及答案&#xff01;多做几遍&#xff0c;其实通过危险化学品经营单位主要负责人…

移动云行动:5.5G技术引领数字化转型

刚刚结束的全国两会上&#xff0c;有人大代表建议应尽快发挥5G-A&#xff08;5.5G&#xff09;优势&#xff0c;加快试点城市布局。此前&#xff0c;中国移动已宣布将在300多个城市启动5.5G商用部署。在通信技术的历史长河中&#xff0c;4G改变了我们的生活方式&#xff0c;而5…

【Poi-tl Documentation】区块对标签显示隐藏改造

前置说明&#xff1a; <dependency><groupId>com.deepoove</groupId><artifactId>poi-tl</artifactId><version>1.12.1</version> </dependency>模板&#xff1a; 删除行表格测试.docx 改造前测试效果 package run.siyuan…

Iframe 嵌入: 页面嵌入并保持自适应页面的宽高并铺满整个屏幕

文章目录 问题分析1. 嵌入 Iframe2. 样式3. 源码 问题 当我们使用 Iframe 嵌入页面后&#xff0c;会看到它只在小小的一部分进行展示&#xff0c;如何让它铺满整个屏幕 分析 1. 嵌入 Iframe <template><div><iframe :src"embeddedPageUrl" width…

【编程项目开源】微信飞机大战(鸿蒙版)

目标 仿微信飞机大战 效果 开发工具 下载DevEco Studio 工程截图 开源地址 https://gitee.com/lblbc/plane_game/tree/master/PlaneGame_hongmeng_ArkTS 关于 厦门大学计算机专业|华为八年高级工程师 专注《零基础学编程系列》 http://lblbc.cn/blog 包含&#xff1a;Ja…

18.相交链表

给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;函数返回结果后&…

腾讯云2核4g服务器能支持多少人访问?没搞错吧

腾讯云轻量2核4G5M带宽服务器支持多少人在线访问&#xff1f;5M带宽下载速度峰值可达640KB/秒&#xff0c;阿腾云以搭建网站为例&#xff0c;假设优化后平均大小为60KB&#xff0c;则5M带宽可支撑10个用户同时在1秒内打开网站&#xff0c;并发数为10&#xff0c;经阿腾云测试&a…

2024年【P气瓶充装】模拟考试及P气瓶充装证考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 P气瓶充装模拟考试是安全生产模拟考试一点通生成的&#xff0c;P气瓶充装证模拟考试题库是根据P气瓶充装最新版教材汇编出P气瓶充装仿真模拟考试。2024年【P气瓶充装】模拟考试及P气瓶充装证考试 1、【多选题】《中华…

Java中的实用类讲解(上篇)

如果想观看更多Java内容 可上我的个人主页关注我&#xff0c;地址子逸爱编程-CSDN博客https://blog.csdn.net/a15766649633?spm1000.2115.3001.5343 使用工具 IntelliJ IDEA Community Edition 2023.1.4 使用语言 Java8 代码能力快速提升小方法&#xff0c;看完代码自己敲…

python 实现阿里云OSS文件上传

因为我们出口的带宽限制&#xff0c;测试经常找我给他上传个包到阿里云的对象存储&#xff0c;虽然传起来也不是很费事&#xff0c;但是出于运维的职业素养&#xff0c;特意写了一个自动上传的接口&#xff0c;代码如下&#xff1a; # -*- coding: UTF-8 -*- from flask imp…

【保姆及教程】简直不要太爽了!md文件图床工具picgo配合typora和阿里云oss存储,实现文md文件的复制转贴

md文件图床工具picgo的安装和使用、配合阿里云面向对象oss 一、网址 官方网址&#xff1a;https://molunerfinn.com/PicGo/ github地址&#xff1a;https://github.com/Molunerfinn/picgo/releases 选择对应的版本下载即可 但也可以提供我给你的下载的地址&#xff1a; 方…

前端学习之css选择器--基本选择器、关系选择器、属性选择器、复合选择器、伪类选择器

目录 基本选择器 结果 关系选择器 结果 父子关系 祖先后代关系 相邻兄弟关系 兄弟关系 ​编辑 属性选择器 结果 复合选择器 结果 伪类选择器 结果 伪类选择器-操作标签 结果 未访问 访问后 悬停 基本选择器 <!DOCTYPE html> <html lang"en"…

Java-PriorityQueue源码分析

PriorityQueue 源码分析 Java中的PriorityQueue采用的是堆这种数据结构来实现的,而存储堆采用的则是数组。 堆是一个完全二叉树,堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值,对于每个节点的值都大于等于子树中每个节点值的堆&#xff0c;我们叫做大顶…

数学建模--MATLAB基本使用

1.线性方程组 这个是一个线性方程组&#xff08;属于线性代数的范畴&#xff09;&#xff0c;Axb类型的方程&#xff0c;如果使用MATLAB进行求解&#xff0c;就需要分别表示A矩阵&#xff08;线性方程组未知数前面的系数&#xff09;&#xff0c;b矩阵&#xff08;表示等式右边…