Java的集合框架总结

Map接口和Collection接口是所有集合框架的父接口:

  1. Collection接口的子接口包括:Set接口和List接口

  1. Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等

  1. Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等

  1. List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等

List接口及其实现

ArrayList

  • 基于动态数组实现

  • 允许快速随机访问元素

  • 插入和删除操作可能需要移动其他元素,因此在中间位置插入和删除的时间复杂度为O(n)

  • 非同步,不是线程安全的,可以使用使用Collections.synchronizedList(new ArrayList<>()) 创建一个同步的 ArrayList

LinkedList
  • 基于双向链表实现

  • 允许快速插入删除元素

  • 不能快速随机访问,访问元素的时间复杂度为O(n)

  • 非同步,不是线程安全的。可以使用 Collections.synchronizedList(new LinkedList<>()) 创建一个同步的 LinkedList

  • 可以用做队列或双向队列

    依赖于两个节点(一个头节点一个尾节点)

    常用方法

    添加

    add(E e):在链表后添加一个元素; 通用方法 addFirst(E e):在链表头部插入一个元素; 特有方法 addLast(E e):在链表尾部添加一个元素; 特有方法

    删除

    removeFirst(E e):删除头,获取元素并删除; 特有方法 removeLast(E e):删除尾; 特有方法

    查看

    getFirst():获取第一个元素; 特有方法 getLast():获取最后一个元素; 特有方法

Stack
  • 基于Vector实现,代表了后进先出()

  • 是同步的,是线程安全的

  • push入栈、peek查看栈顶元素、pop出栈、empty是否为空、size()获取数目

Vector
  • 基于动态数组实现,类似于ArrayList

  • 同步的,是线程安全的

  • 是需要线程安全的动态数组是使用,但是通常使用ArrayListCollections.syschronizedList来代替

Set接口及其实现类

set其实一直在用map那一套

 public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
     private transient HashMap<E,Object> map;
     private static final Object PRESENT = new Object();
 ​
     public HashSet() {
         map = new HashMap<>();
     }
 ​
     public boolean add(E e) {
         return map.put(e, PRESENT) == null;
     }
 ​
     // Other methods delegate to the underlying map
 }
 ​
HashSet
  • 元素存储HashSet 将元素添加到底层的 HashMap 中,键是元素的哈希码,值是一个占位符对象。HashSet的实现是基于HashMap的,他使用HashMap来存储元素,在HashSet中,元素被当作HashMap的键,而HashMap的值则是一个固定的占位符,通常是 PRESENT 对象(一个静态内部类对象)。这样做是为了节省空间,因为 HashSet 只关心元素的唯一性,不需要存储额外的值。

  • 去重HashSet 使用了 HashMap 键的唯一性来确保 HashSet 中不会有重复的元素。

  • 不保证集合的迭代顺序,顺序可能会随时间变化。

  • 方法委派HashSet 的许多方法(如 addremovecontains 等)都是通过调用底层 HashMap 的对应方法来实现的。

  • 性能:由于 HashSet 是基于 HashMap 实现的,所以其性能与 HashMap 类似,添加、删除和查找操作的平均时间复杂度为 O(1)。

  • 允许存储null值。

LinkedHashSet

LinkedHashSetHashSet 的一个子类,它继承了 HashSet 的特性,并且保持了元素的插入顺序。下面是关于 LinkedHashSet 的一些关键点:

  • 继承自HashSet并且使用链表维护元素的插入顺序

  • 保证迭代顺序与插入顺序一致

  • 允许存储null值。

  • 插入、删除、和查找操作的时间复杂度为O(1)。

实现细节

  • 当你向 LinkedHashSet 添加元素时,它会使用 LinkedHashMap 来存储元素。

  • 每个元素被当作 LinkedHashMap 的键,值则是一个固定的占位符对象。

  • LinkedHashSet 通过委派 LinkedHashMap 来实现其 addremovecontains 等方法。

TreeSet

TreeSet 是 Java 中实现 SortedSet 接口的一个集合类,它基于 TreeMap 实现,并且元素是按照自然顺序(或通过提供的比较器)排序的。以下是 TreeSet 的一些关键点:

  • 基于红黑树(自平衡二叉搜索树)实现

  • 元素是有序的,元素按照自然顺序(或通过Comparator指定的顺序)排

  • 不允许存储null值(会抛出NullPointerException

  • 插入、删除、和查找操作的时间复杂度为O(log n)。

Map接口及其实现类
HashMap

  • 基于哈希表实现,调用put方法值,首先将k,v封装到Node对象中,然后底层会调用k的hashCode()方法得到hash值。根据这个值来决定到底该插入数组下标的哪个位置,如果有两个值的哈希值一样,就会调用equals方法进行比较,如果哈希值一样但是不相等,就会形成链表插入 ,如果相等那么相等的这个节点的value将会被覆盖。如果没有元素占用位置,就直接放入即可。(通过数组加链表形式)

  • 在Java8对hashmap进行了优化,如果相同哈希值,链表的长度超过8,就从链表转换成红黑树。第一次添加元素的时候,默认初期长度为16,当往map中继续添加元素的时候,通过hash值跟数组长度取“与”来决定放在数组的哪个位置,如果出现放在同一个位置的时候,优先以链表的形式存放,在同一个位置的个数又达到了8个(代码是>=7,从0开始,及第8个开始判断是否转化成红黑树),如果数组的长度还小于64的时候,则会扩容数组。如果数组的长度大于等于64的话,才会将该节点的链表转换成树。在扩容完成之后,如果某个节点的是树,同时现在该节点的个数又小于等于6个了,则会将该树转为链表(只有当数据量大于64才会有红黑树+链表)

  • HashMap内部结构是数组(Node[] table)和链表结合组成的复合结构,数组被分成一个个桶(bucket)或槽,通过哈希值决定键值对在这个数组的寻址;哈希值相同的键值对,则以链表形式存储。当链表大小超过阈值(TREEIFY_THRESHOLD = 8)时,链表就会被改造成树形结构。(查询效率变高)

  • Java8不再像Java7中那样需要满足两个条件,Java8中扩容只需要满足一个条件:当前存放新值(注意不是替换已有元素位置时)的时候已有元素的个数大于等于阈值(已有元素等于阈值,下一个存放后必然触发扩容机制)且扩容发生在存放后,即是数据存放后(先存放后扩容),判断当前存入对象的个数,如果大于阈值则进行扩容。

  • 允许存储null键和null值。

  • 插入、删除、和查找操作的时间复杂度为O(1)。

  • 非同步,不是线程安全的。

LinkedHashMap

  • 通过hashmap跟双向链表实现,可以确保按照插入顺序迭代链表

  • 遍历性能: 与普通的HashMap相比,在迭代LinkedHashMap时,性能更加稳定。因为它不需要遍历整个桶,而是按照链表顺序遍历元素。

  • 实现方式: 在内部实现上,LinkedHashMap在每个条目中保留了前一个和后一个条目的引用,以实现双向链表。这使得在插入、删除和遍历元素时的性能表现良好。

TreeMap

  • 基于红黑树实现

  • 键按照自然顺序(或通过Comparator指定的顺序)排序。

  • 不允许存储Null键

  • 插入、删除、和查找操作的时间复杂度为O(log n)。

Hashtable
  • 也是使用哈希表还有链表实现

  • 同步的,是线程安全的。

  • 不允许存储null键和null值。

  • 插入、删除、和查找操作的时间复杂度为O(1)。

Properties
  • 继承自Hashtable,表示一个持久化的属性集。

  • 每个键及其对应值都是一个字符串。

  • 常用于读取和写入配置文件。

ConcurrentHashMap
  • 不允许存储null键和null值。

  • 插入、删除、和查找操作的时间复杂度为O(1)。

  • 在多线程环境下,使用HashMap进行put操作时存在丢失数据的情况,为了避免这种bug的隐患,强烈建议使用ConcurrentHashMap代替HashMap。

  • HashTable是一个线程安全的类,它使用synchronized来锁住整张Hash表来实现线程安全,即每次锁住整张表让线程独占,相当于所有线程进行读写时都去竞争一把锁,导致效率非常低下。ConcurrentHashMap可以做到读取数据不加锁,并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小,允许多个修改操作并发进行,其关键在于使用了锁分段技术。它使用了多个锁来控制对hash表的不同部分进行的修改。

分段锁(Segment Locking)机制

早期版本的ConcurrentHashMap(Java 7及之前)使用分段锁机制,具体如下:

  • ConcurrentHashMap内部将整个哈希表分为多个段(Segment),每个段都是一个独立的哈希表,并拥有自己的锁。

  • 这种机制允许多个线程同时访问不同段的元素,从而提高并发度。

  • ConcurrentHashMap 为了提高本身的并发能力,在内部采用了一个叫做 Segment 的结构,一个 Segment 其实就是一个类 Hash Table 的结构,Segment 内部维护了一个链表数组,我们用下面这一幅图来看下 ConcurrentHashMap 的内部结构,从下面的结构我们可以了解到,ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作,第一次 Hash 定位到 Segment,第二次 Hash 定位到元素所在的链表的头部,因此,这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长,但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可,不会影响到其他的 Segment,这样,在最理想的情况下,ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作(刚好这些写操作都非常平均地分布在所有的 Segment上),所以,通过这一种结构,ConcurrentHashMap 的并发能力可以大大的提高。

CAS操作和分段锁

在Java 8中,ConcurrentHashMap使用了一种新的机制,结合了CAS(Compare-And-Swap)操作和细粒度的分段锁。

  • 使用CAS操作来保证对单个节点的原子性操作,减少锁的使用。

  • 在插入、删除和更新操作中,如果CAS操作失败(即另一个线程同时修改了相同的位置),则退而使用锁进行操作。

  • 在Java 8中,ConcurrentHashMap取消了分段锁的概念,直接在哈希桶(bucket)级别进行锁定,使用CAS操作和synchronized块来保证并发安全。这使得数据结构更加简单,且操作更加直观。

  • 为了优化哈希冲突情况下的查找性能,Java 8引入了红黑树。当链表的长度超过一定阈值(默认是8)时,链表会转换为红黑树。这样,在高冲突情况下,查找操作的时间复杂度从O(n)降到了O(log n),极大地提高了性能。

  • CAS 操作通过比较当前值与预期值,如果两者相等则更新为新值,否则重试该操作。

数据结构

ConcurrentHashMap在Java 8中的内部数据结构有以下几个关键组成部分:

  • 数组(Node<K,V>[] table):哈希表的核心数组,存储链表或红黑树的头节点。

  • 链表和红黑树:数组中的每个桶(bucket)最初是一个链表。当链表长度超过阈值(8)时,链表会转换为红黑树,以提高查询效率。

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

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

相关文章

【CH32V305FBP6】USBD HS 描述符修改

文章目录 前言设备描述符完整描述符配置描述符CDC 描述符接口关联描述符接口描述符功能描述符端点描述符接口描述符端点描述符 HID 描述符接口描述符 新增一个 HID 设备 前言 USB HS 复合设备&#xff0c;CDCHID 功能&#xff1a;串口、DAP、CAN-HID、RS485 设备描述符 htt…

远程抄表系统方案

一、远程抄表系统简述 远程抄表系统&#xff0c;是一种智能化的自动化数据收集技术性&#xff0c;主要运用于电力工程、供水公司、天然气等公共服务行业&#xff0c;完成对消费者表计数据的远程、即时、智能采集。这类系统不但降低了成本&#xff0c;降低了人力抄表错误&#…

手部出现这4种症状,可能是糖尿病先兆!务必及时监测血糖

糖尿病来袭&#xff0c;手部或先知&#xff01;出现这 4 种症状&#xff0c;务必尽快监测血糖 第一&#xff0c;手指麻木感明显&#xff0c;当持续性的高血糖损害手部血管与神经末梢时&#xff0c;便会导致手指产生麻木以及刺痛之感。而且随着血糖不断升高&#xff0c;受损的血…

Soildworks学习笔记(一)

1.如何添加M3,M4等螺丝孔&#xff1a; 有时候异形孔向导显示灰色是因为没有退出草图选项卡&#xff0c;选择异形孔向导就可以进行异形孔的设定和放置&#xff1a; solidwork放置螺丝孔以及显示螺纹的问题_.16-m3 solidwork-CSDN博客 2.如何修剪线条&#xff1a; 如何倒圆角或…

Hack The Box-Blurry

总体思路 CVE-2024-24590->修改脚本/劫持python库 信息收集&端口利用 nmap -sSVC blurry.htbStarting Nmap 7.94SVN ( https://nmap.org ) at 2024-06-10 21:40 EDT Nmap scan report for app.blurry.htb (10.10.11.19) Host is up (0.20s latency).PORT STATE S…

网络仿真方法综述

目录 1. 引言 2.仿真器介绍 2.1 NS-2 2.2 NS-3 2.3 OPNET 2.4 GNS3 3.仿真对比 4.结论 参考文献 1. 引言 网络仿真是指使用计算机模拟网络系统的行为和性能的过程。在网络仿真中&#xff0c;可以建立一个虚拟的网络环境&#xff0c;并通过模拟各种网络设备、协议和应用程…

Java 的循环

Java 有三种循环&#xff1a;for&#xff0c;while&#xff0c;do while。 for 基本语法&#xff1a; for (循环变量初始化; 循环条件; 循环变量迭代){循环语句; }程序示例&#xff1a; public static void main(String[] args) {for (int i 0, j 0; i < 3; i, j--) {…

大神出新品,吴恩达开源机器翻译智能体项目

节前&#xff0c;我们星球组织了一场算法岗技术&面试讨论会&#xff0c;邀请了一些互联网大厂朋友、参加社招和校招面试的同学。 针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。 合集&#x…

Clion控制台打印中文乱码

第一步 第二步 第三步 ctrlaltshift/ 把run.processes,with.pty

教育小程序开发:技术实现与实践案例

随着信息技术的不断进步&#xff0c;教育小程序在教育领域的应用越来越广泛。教育小程序开发不仅可以提高教学效率&#xff0c;还能够提供个性化的学习体验。本文将以技术代码为例&#xff0c;详细介绍教育小程序开发的关键技术和实践案例&#xff0c;帮助开发者更好地理解和实…

小公司要求真高

大家好&#xff0c;我是白露啊。 最近看到一个爽文帖&#xff0c;标题就是——“小公司要求真高”。 事情是这样的&#xff0c;一家的小公司在拿到简历之后&#xff0c;HR直接对楼主说&#xff1a;“你不合适&#xff0c;简历不行。” 言外之意就是嫌弃简历单薄&#xff0c;看…

IntelliJ IDEA 2024.1最新安装 亲测有效2099年

标题一&#xff1a;IDEA官方下载 ①如题&#xff0c;先到IDEA官方下载&#xff0c;简简单单 ②IDEA官方&#xff1a;IntelliJ IDEA – the Leading Java and Kotlin IDE 标题二&#xff1a;获取脚本 点这里获取 &#x1f31f;获取完后压缩&#xff0c;推荐与IDEA放在同一目…

白酒:茅台镇白酒的地域特色菜肴与搭配建议

在中国的美食文化中&#xff0c;酒与菜一直是密不可分的。茅台镇作为中国白酒的发源地&#xff0c;其白酒与地域特色菜肴的搭配更是有着深厚的历史底蕴。云仓酒庄作为茅台镇的知名酒庄&#xff0c;其豪迈白酒与当地特色菜肴的搭配&#xff0c;更是让人回味无穷。 茅台镇的菜肴以…

delmia中机器人末端固定工具

1 需要在工具上面建立点 在Device Building模式下 2 然后通过 set tool可以设置

Shell脚本 if语句

条件测试&#xff1a; $? 返回码 判断命令或者脚本是否执行成功&#xff08;最近的一条&#xff09; 0 true 为真就是成功 成立 非0 false 失败或者异常 test命令 可以进行条件测试 然后根据的是返回值来判断条件是否成立。 -e 测试目录或者文件是否存在 exist -d 测试…

宝兰德受邀出席第八届丝绸之路网络安全论坛

近日&#xff0c;2024第八届丝绸之路网络安全论坛在陕西宾馆会议中心成功举办&#xff0c;本次论坛以“汇聚万千智慧 夯实安全堤坝”为主题&#xff0c;由主论坛及密码技术与密评、教育行业网络安全、卫健行业网络安全三个平行分论坛组成&#xff0c;论坛邀请业内专家学者、企业…

MyBatisPlus代码生成器(交互式)快速指南

引言 本片文章是对代码生成器(交互)快速配置使用流程&#xff0c;更多配置方法可查看官方文档&#xff1a; 代码生成器配置官网 如有疑问欢迎评论区交流&#xff01; 文章目录 引言演示效果图引入相关依赖创建代码生成器对象引入Freemarker模板引擎依赖支持的模板引擎 MyBat…

HBase中Master初始化错误~

ERROR&#xff1a;org.apache.hadoop.hbase.PleaseHoldException:Master is initializing 1、停止HBase运行 2、启动zookeeper中的zkCli.sh服务 ./zookeeper/bin/zkCli.sh 3、执行完毕显示以下结果,删除habse文件夹 4、重新启动HBase即可。

如何关闭端口被占用的进程

如何关闭端口被占用的进程 操作步骤一、打开命令提示符&#xff08;Command Prompt&#xff09;二、查看占用端口的进程三、kill杀死占用端口的进程 操作步骤 一、打开命令提示符&#xff08;Command Prompt&#xff09; 使用 win R 打开命令行模式 然后在命令行窗口输入下…

基于机器学习和奇异值分解SVD的电池剩余使用寿命预测(Python)

采用k-最近邻KNN和随机森林算法建立预测模型。 import pandas as pd from sklearn.model_selection import train_test_split from sklearn.svm import SVC # Support Vector Classifier from sklearn.preprocessing import StandardScaler from sklearn.metrics import accu…