Java集合相关的List、Set、Map基础知识

目录

一、集合介绍

二、List

三、Map

HashMap的数据结构

如何理解红黑树

四、set


一、集合介绍

在Java中,集合是一种用于存储对象的数据结构,它提供了一种更加灵活和强大的方式来处理和操作数据。Java集合框架提供了一系列接口和类,用于表示和操作不同类型的集合

图片来源:《面渣逆袭手册》V1.1

其中 Collection 是集合 List Set 的父接口,它主要有两个子接口:
        List :存储的元素有序,可重复。(相当于是个篮子,临时给你放数据用的
        Set :存储的元素无序,不可重复。(去重的List,放进去的东西如果一样,后面的会把前面的覆盖掉,得到的是个无重复值的列表
        Map 是另外的接口,是键值对映射结构的集合。(Map是个键值对,可以实现用a来搜b的作用,比如用用户的id搜用户的名称之类的操作

以下是Java中常见的集合:

  1. List(列表)

    • ArrayList:基于数组实现的动态数组,支持快速随机访问元素,但插入和删除操作效率较低。
    • LinkedList:基于链表实现的双向列表,插入和删除操作效率较高,但访问元素的效率较低。
    • Vector:与 ArrayList 类似,但是线程安全的,不推荐在新代码中使用。
    • Stack:基于 Vector 实现的栈,通常用于实现后进先出(LIFO)的数据结构。
  2. Set(集合)

    • HashSet:基于哈希表实现的集合,不保证元素的顺序。
    • TreeSet:基于红黑树实现的有序集合,可以按照自然顺序或者自定义顺序对元素进行排序。
    • LinkedHashSet:具有预期插入顺序的集合,内部使用链表维护元素的顺序。
  3. Map(映射)

    • HashMap:基于哈希表实现的映射,键值对无序。
    • TreeMap:基于红黑树实现的有序映射,键值对按照键的自然顺序或者自定义顺序进行排序。
    • LinkedHashMap:具有预期插入顺序的映射,内部使用链表维护键值对的顺序。
  4. Queue(队列)

    • PriorityQueue:基于堆实现的优先级队列,按照元素的优先级顺序进行排序。

此外,Java集合框架还包括一些接口和抽象类,如 CollectionMapIterator 等,它们提供了一组通用的操作和方法,可以方便地对集合进行操作和遍历。

二、List

在 Java 中,ArrayList 和 LinkedList 是两种常见的集合实现,它们有以下主要区别:

  1. 内存分配
    • ArrayList:使用连续的内存空间来存储元素。
    • LinkedList:使用链式存储结构,内存空间不连续,它们在空间占用上都有一些额外的消耗
    • ArrayList 是预先定义好的数组,可能会有空的内存空间,存在一定空间浪费
      LinkedList 每个节点,需要存储前驱和后继,所以每个节点会占用更多的空间
  2. 随机访问
    • ArrayList基于数组,所以它可以根据下标查找,支持快速的随机访问,通过索引可以快速获取元素。
    • LinkedList基于链表,所以它没法根据序号直接获取元素,在随机访问方面效率较低。
  3. 插入和删除
    • 多数情况下,ArrayList更利于查找,LinkedList更利于增删。
    • ArrayList 基于数组实现, get(int index) 可以直接通过数组下标获取,时间复杂度
      O(1) LinkedList 基于链表实现, get(int index) 需要遍历链表,时间复杂度是
      O(n) ;当然, get(E element) 这种查找,两种集合都需要遍历,时间复杂度都是
      O(n)
    • ArrayList增删如果是数组末尾的位置,直接插入或者删除就可以了,但是如果插
      入中间的位置,就需要把插入位置后的元素都向前或者向后移动,甚至还有可能
      触发扩容;双向链表的插入和删除只需要改变前驱节点、后继节点和插入节点的
      指向就行了,不需要移动元素。
    • 图片来源:《面渣逆袭手册》V1.1
  4. 内存占用
    • ArrayList:需要预先分配一定的内存空间,如果元素数量超过容量,需要进行扩容。
      基于数组的集合,数组的容量是在定义的时候确定的,如果数组满了,
      再插入,就会数组溢出。所以在插入时候,会先检查是否需要扩容,如果当前容量
      +1 超过数组长度,就会进行扩容。
    • ArrayList的扩容是创建一个1.5的新数组,然后把原数组的值拷贝过去。
    • LinkedList:不需要预先分配固定的内存空间。
  5. 遍历方式
    • ArrayList:可以通过索引或迭代器进行遍历。
    • LinkedList:还可以通过指针依次访问元素。
      示例代码如下:
    • import java.util.ArrayList;
      import java.util.LinkedList;
      import java.util.List;public class CollectionExample {public static void main(String[] args) {// 使用 ArrayListList<String> arrayList = new ArrayList<>();arrayList.add("Apple");arrayList.add("Banana");arrayList.add("Orange");System.out.println("使用 ArrayList 遍历:");for (String item : arrayList) {System.out.println(item);}// 使用 LinkedListList<String> linkedList = new LinkedList<>();linkedList.add("Apple");linkedList.add("Banana");linkedList.add("Orange");System.out.println("\n 使用 LinkedList 遍历:");for (String item : linkedList) {System.out.println(item);}}
      }

三、Map

在 Java 中,常见的 Map 实现有 HashMap 和 TreeMap 。

HashMap 基于哈希表实现,它的数据结构如下:

  • 存储键值对。
  • 通过哈希函数计算键的哈希值,以确定元素在哈希表中的存储位置。

TreeMap 基于红黑树实现,它的数据结构如下:

  • 按照键的自然顺序进行排序。
  • 提供有序的键值对访问。

HashMap的数据结构

JDK1.8 的数据结构是 数组 + 链表 + 红黑树

数据结构示意图如下:

图片来源:《面渣逆袭手册》V1.1

其中,桶数组是用来存储数据元素,链表是用来解决冲突, 红黑树 是为了提高查询
的效率。
数据元素通过映射关系,也就是散列函数,映射到桶数组对应索引的位置
如果发生冲突,从冲突的位置拉一个链表,插入冲突的元素
如果链表长度  > 8 &  数组大小  >= 64  ,链表转为红黑树
如果红黑树节点个数  < 6 ,转为链表

哈希表的基本原理是通过哈希函数将键映射到特定的存储位置,以实现快速的插入、查找和删除操作。


哈希函数用于计算键的哈希值,并根据哈希值确定元素在哈希表中的存储位置。哈希表通常包含以下组件:

  1. 数组:用于存储元素。
  2. 哈希函数:将键转换为数组的索引。
  3. 冲突处理机制:处理不同键可能映射到相同索引的冲突。

在插入元素时,通过哈希函数计算键的哈希值,确定存储位置。如果该位置为空,则直接插入元素;如果存在冲突,使用冲突处理机制解决。

在查找元素时,同样通过哈希函数计算哈希值,找到对应的位置进行查找。

哈希表的优点包括:

  1. 快速的插入、查找和删除操作。
  2. 不需要按照特定顺序存储元素。

如何理解红黑树

红黑树本质上是一种二叉查找树,为了保持平衡,它又在二叉查找树的基础上增加了一些规则:
  1. 颜色规则:每个节点要么是红色,要么是黑色
  2. 特性规则:
    • 根节点是黑色的。
    • 如果一个节点是红色的,那么它的子节点必须是黑色的。
    • 从每个叶子节点到根节点的所有路径上,黑色节点的数量相同。
      在进行插入或删除操作时,红黑树会通过一系列的旋转和颜色调整来保持这些规则,以确保树的平衡性。

图片来源:《面渣逆袭手册》V1.1

旋转操作包括左旋和右旋,用于调整树的结构。

红黑树有两种方式保持平衡: 旋转 染色 通过保持红黑树的平衡性,可以提高搜索、插入和删除操作的效率,避免出现最坏情况下的线性搜索。

有关HashMap的知识点非常多,这里不做详述,后面会单独写一篇有关HashMap的相关内容。

哈希表在以下场景中比较适用:

  1. 快速查找:当需要快速查找数据时,哈希表可以提供高效的查找性能。
  2. 存储和检索数据:适用于需要频繁地插入、删除和查找数据的场景。
  3. 缓存:可以用于缓存数据,以提高系统的性能。
  4. 统计频率:用于统计元素的出现频率。
  5. 数据去重:去除重复的数据。
  6. 关联数据:建立键值对的关联。
    例如,在以下场景中可能会使用哈希表:
  7. 数据库索引:加速数据的查询。
  8. 缓存系统:提高数据的访问速度。
  9. 网页搜索引擎:快速检索和索引网页。
  10. 数据处理和分析:高效地处理大量数据。

四、set

HashSet 是 Java 中的一个集合类,它不允许存储重复的元素。HashSet 底层就是基于 HashMap 实现的。( HashSet 的源码⾮常⾮常少,因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外,其他⽅法都是直接调⽤ HashMap 中的⽅法。

HashSet的add方法,直接调用HashMap的put方法,将添加的元素作为key,new一个 Object作为value,直接调用HashMap的put方法,它会根据返回值是否为空来判断是否插入元素成功。

以下是 HashSet 的一些特点:

  1. 无序性:元素的存储顺序是无序的。
  2. 不允许重复元素:确保每个元素在集合中唯一。
  3. 基于哈希表实现:提供快速的插入、查找和删除操作。

参考

《面渣逆袭手册》V1.1.pdf

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

表格的单元格合并和表头的合并——vxe-table

vxe-table的官网&#xff1a;https://vxetable.cn/#/table/advanced/mergeCell在你的项目中下载安装完成后&#xff0c;先在main.js文件中引入&#xff1a; import VXETable from vxe-table import vxe-table/lib/style.css Vue.use(VXETable)一、单元格合并 效果图&#xff…

Linux驱动开发——(七)Linux阻塞和非阻塞IO

目录 一、阻塞和非阻塞IO简介 二、等待队列 2.1 等待队列头 2.2 等待队列项 2.3 将队列项添加/移除等待队列头 2.4 等待唤醒 2.5 等待事件 三、轮询 四、驱动代码 4.1 阻塞IO 4.2 非阻塞IO 一、阻塞和非阻塞IO简介 IO指的是Input/Output&#xff0c;也就是输入/输…

JavaWeb--06Vue组件库Element

Element 1 Element组件的快速入门1.1 Table表格 1 Element组件的快速入门 https://element.eleme.cn/#/zh-CN Element是饿了么团队开发的 接下来我们来学习一下ElementUI的常用组件&#xff0c;对于组件的学习比较简单&#xff0c;我们只需要参考官方提供的代码&#xff0c;然…

SSH新功能揭秘:远程工作提升指南【AI写作】

首先&#xff0c;这篇文章是基于笔尖AI写作进行文章创作的&#xff0c;喜欢的宝子&#xff0c;也可以去体验下&#xff0c;解放双手&#xff0c;上班直接摸鱼~ 按照惯例&#xff0c;先介绍下这款笔尖AI写作&#xff0c;宝子也可以直接下滑跳过看正文~ 笔尖Ai写作&#xff1a;…

同态加密原理解析

目录 1.数学介绍2.使用多项式环进行加密2.1 私钥和公钥的产生2.2 加密2.3 解密 3.同态计算3.1 同态加法3.2 同态乘法 1.数学介绍 同态加密方案基于一个难以计算的问题Ring Learning with Errorsred。这些方案中的数据在加密和未加密时都用多项式表示。 这里举一个简单的多项式…

什么是IIoT?

什么是IIoT? IIoT&#xff0c;即工业物联网&#xff08;Industrial Internet of Things&#xff09;&#xff0c;是指将物联网技术应用到工业领域&#xff0c;通过微型低成本传感器、高带宽无线网络等技术手段&#xff0c;实现工业设备、系统和服务的互联互通&#xff0c;从而…

ChatGPT/GLM API使用

模型幻觉问题 在自然语言处理领域&#xff0c;幻觉&#xff08;Hallucination&#xff09;被定义为生成的内容与提供的源内容无关或不忠实&#xff0c;具体而言&#xff0c;是一种虚假的感知&#xff0c;但在表面上却似乎是真实的。产生背景 检索增强生成&#xff08;RAG&…

基于MLP算法实现交通流量预测(Pytorch版)

在海量的城市数据中&#xff0c;交通流量数据无疑是揭示城市运行脉络、洞察出行规律的关键要素之一。实时且精准的交通流量预测不仅能为交通规划者提供科学决策依据&#xff0c;助力提升道路使用效率、缓解交通拥堵&#xff0c;还能为公众出行提供参考&#xff0c;实现个性化导…

算法 || 二分查找

目录 二分查找 在排序数组中查找元素的第一个和最后一个位置 搜索插入位置 一个数组经过划分后具有二段性的都可以用二分查找 二分查找 704. 二分查找 - 力扣&#xff08;LeetCode&#xff09; ​ 暴力解法&#xff1a;直接遍历数组&#xff0c;找到 target 便返回下标&am…

原型链prototype、__proto、constructor的那些问题整理

再了解原型链之前,我们先来看看构造函数和实例对象的打印结构 - 函数 这里我们定义一个构造函数Fn,然后打印它的结构吧 function Fn(){} console.dir(Fn)控制台得到结构 从上面结构我们能看的出来,函数有两种原型,一种是作为函数特有的原型:prototype,另一种是作为对象的__…

低代码技术的全面应用:加速创新、降低成本

引言 在当今数字化转型的时代&#xff0c;企业和组织面临着不断增长的应用程序需求&#xff0c;以支持其业务运营和创新。然而&#xff0c;传统的软件开发方法通常需要大量的时间、资源和专业技能&#xff0c;限制了企业快速响应市场变化和业务需求的能力。在这样的背景下&…

chrome浏览器安装elasticsearch的head可视化插件

head插件简介 elasticsearch-head被称为是弹性搜索集群的web前端&#xff0c;head插件主要是用来和elastic Cluster交互的Web前端 head插件历史 elasticsearch-head插件在0.x-2.x版本的时候是集成在elasticsearch内的&#xff0c;由elasticsearch的bin/elasticsearch-plugin…

区块链 | OpenSea 相关论文:Toward Achieving Anonymous NFT Trading(一)

​ &#x1f951;原文&#xff1a; Toward Achieving Anonymous NFT Trading &#x1f951;写在前面&#xff1a; 本文对实体的介绍基于论文提出的方案&#xff0c;而非基于 OpenSea 实际采用的方案。 其实右图中的 Alice 也是用了代理的&#xff0c;不过作者没有画出来。 正文…

基于SpringBoot + Vue实现的校园(通知、投票)管理系统设计与实现+毕业论文(12000字)+答辩PPT+指导搭建视频

目录 项目介绍 运行环境 技术栈 效果展示 论文展示 总结 项目介绍 本系统包含管理员、用户、院校管理员三个角色。 管理员角色&#xff1a;用户管理、院校管理、单位类别管理、院校管理员管理、单位管理、通知推送管理、投票信息管理、通知回复管理等。 用户角色&#…

sqlite 附加(attach database)加密数据库时,返回26是什么原因呢?

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…

数据结构—单链表

含义 1.顺序表的回顾 之前的文章已经谈到了顺序表&#xff0c;关于顺序表&#xff0c;有一下的几种特点 1.中间&#xff0c;头部的删除&#xff0c;复杂度为O(N); 2.增容会有申请新的空间&#xff0c;拷贝数据&#xff0c;释放旧的空间&#xff0c;会有不小的消耗&#xff…

数据结构:最小生成树(Prim算法和Kruskal算法)、图的最短路径(Dijkstra算法和Bellman-Ford算法)

什么是最小生成树&#xff1f;Prim算法和Kruskal算法是如何找到最小生成树的&#xff1f; 最小生成树是指在一个连通图中&#xff0c;通过连接所有节点并使得总权重最小的子图。 Prim算法和Kruskal算法是两种常用的算法&#xff0c;用于寻找最小生成树。 Prim算法的步骤如下&…

mysql的多表查询和子查询

多表查询&#xff1a;查询数据时&#xff0c;需要使用多张表来查询 多表查询分类&#xff1a; 1.内连接查询 2.外连接查询 3.子查询 笛卡尔积&#xff1a; create table class (id int primary key auto_increment,name varchar(10) ); create table student (id int primar…

学习STM32第十六天

RTC实时时钟 一、简介 RTC是一个独立的BCD格式定时器&#xff0c;提供一个时钟日历&#xff0c;两个可编程报警中断&#xff0c;一个具有中断功能周期性可编程唤醒标志&#xff0c;RTC和时钟配置系统处于后备区域。 通过两个32位寄存器以BCD格式实现秒、分钟、小时&#xff08…

stable-diffusion-webui安装与使用过程中的遇到的error合集

stable-diffusion-webui1.9.2踩坑安装 1. 安装过程1.1 stable-diffusion-webui1.2 在win11或win10系统安装&#xff0c;需修改两个启动脚本1.2.1 修改webui-user.bat1.2.2 修改webui.bat 1.3 双击 webui-user.bat 启动脚本1.3.1 no module xformers. Processing without on fre…