首页 > 编程语言 >Java之集合底层-数据结构

Java之集合底层-数据结构

时间:2024-07-20 23:28:15浏览次数:18  
标签:Java 链表 哈希 红黑树 数据结构 数据 节点 底层

Java集合之数据结构

1 概述

数据结构是计算机科学中研究数据组织、存储和操作的一门学科。它涉及了如何组织和存储数据以及如何设计和实现不同的数据操作算法和技术。常见的据结构有线性数据结构(含数组、链表、栈和队列等),非线性数据结构(树、图等)。

注意:不同的数据结构适用于不同的场景和问题,选择合适的数据结构可以提高算法的效率和性能。

Java集合框架中不同的实现类底层借助不同数据结构来存储输出,常见的数据结构有:

  1. 数组(Array):有序集合,可以包含重复的元素,常见实现类有ArrayList、Vector
  2. 链表(LinkedList):链表是一种动态数据结构,通过节点之间的链接来组织数据。常见的链表实现类是LinkedList
  3. 集合(Set):集合是不允许包含重复元素的无序集合。常见的集合实现类有HashSet、LinkedHashSet和TreeSet
  4. 映射(Map):映射是一种键值对的集合,每个键只能对应一个值。常见的映射实现类有HashMap、LinkedHashMap和TreeMap
  5. 队列(Queue):队列是一种先进先出(FIFO)的数据结构。常见的队列实现类有LinkedList和PriorityQueue
  6. 栈(Stack):栈是一种后进先出(LIFO)的数据结构。常见的栈实现类是Stack
  7. 树(Tree):树是一种具有分层结构的数据结构,常见的树实现类有BinaryTree和BinarySearchTree

2 数组

数组(array),内存中一块连续的空间,元素数据在其中按照下标索引依次存储,比较常用的数据结构。

其特点是:通过下标索引,可以快速访问指定位置的元素,但是在数组中间位置添加数据或者删除数据会比较慢,因为数组中间位置的添加和删除元素,为了元素数据能紧凑的排列在一起,那么就会引起其后面的元素移动位置。

所以,数组查询元素较快,中间位置的插入、删除元素较慢。

在这里插入图片描述> 可以看出,数组中间添加数据后,之后的数据都要依次移动位置。同理,中间位置删除的时候也是这样

3 链表

链表(linked list),是由一个一个node节点组成,每个node节点中包含两项数据:指针域、数据域。数据域存储了一个数据,指针域存储指向下一个node节点对象的引用(单向链表)。

如果是双向链表的话,指针域会存储2个引用,一个指向前一个node节点对象,另一个指向了下一个node节点对象。

在这里插入图片描述

单链表插入、删除节点:
在这里插入图片描述

链表特点:

  • 查找元素慢,因为需要通过连接的节点,依次向后查找指定元素(没有直接的下标索引)

  • 新增和删除元素较快,例如删除,只需要让当前node节点中的引用指向另一个节点对象即可,原来的指向的node节点就相当于删除了

可以看出,只需要将数据2节点中的引用,指向数据4的节点对象即可

head表示链表的头部,tail表示链表的尾部

思考,是否能根据单向链表的特点,想象出双向链表的特点?

在这里插入图片描述

4 栈

栈(stack),又称堆栈,仅允许在栈的一端进行插入和删除操作,并且不允许在其他任何位置进行操作。

其特点是:先进后出,最先存进去的元素,最后才能取出来

例如,薯片存在薯片桶中,我们当前只能取出最上面的一个薯片,而最早存放到薯片桶的薯片,反而是我们最后吃到的一片。

在这里插入图片描述

注意1,入栈也称为压栈,把数据存入到栈的顶端位置

注意2,出栈也称为弹栈,把栈顶位置的数据取出

思考,JVM中的栈区中,为什么把main方法标注在最底端位置?

5 队列

队列(queue),仅允许在队列的一端进行插入,而在队列的另一端进行删除。

其特点是:先进先出,最先存进去的元素,可以最先取出来

例如,火车穿过山洞的时候,第一节车厢先进去山洞的一端,并且这节车厢优先从山洞的另一端出来,后面的车厢依次从一端进入并另一端出来。

队列的入口、出口分别在队列的俩端:
在这里插入图片描述

6 红黑树

二叉树(Binary tree)是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树,且有左右之分。

二叉树顶上的叫根结点,两边被称作“左子树”和“右子树”。

在这里插入图片描述

二叉树中有一种叫做红黑树(Red/Black Tree),它最早被称为平衡二叉B树(symmetric binary B-trees),后来被称为红黑树。

红黑树是一种特殊化的平衡二叉树,它可以在进行插入和删除的时候,如果左右子数的高度相差较大,那么就通过特定操作(左旋、右旋)保持二叉查找树的平衡(动态平衡),从而获得较高的查找性能。

红黑树的每一个节点的左子树的所有数据都比自己小,而右子树的所有数据都比自己大,并且左右子树的高度近似。

红黑树的约束:

  1. 根节点必须是黑色
  2. 其他节点可以是红色的或者黑色
  3. 叶子节点(特指null节点)是黑色的
  4. 每个红色节点的子节点都是黑色的
  5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

注意,红黑树的指定颜色的目的,是利用颜色值作为二叉树的平衡对称性的检查

例如,从空树开始演示一个案例:

数字插入顺序为 9、8、12、7、6,对于一个节点来说,新数据如果小于本节点,会被放在左节点的位置,反之则放在右节点的位置

在这里插入图片描述

当插入数字6的时候,对于红黑树来说整个结构失去平衡,需要通过自旋来调整,最后结果如下:
在这里插入图片描述

红黑树在线演示

可以通过在线工具,进行节点的添加,查看红黑树的动态调整的动画效果,建议使用chrome浏览器打开:

在这里插入图片描述

7 哈希表

**复习回顾:Object中hashCode**方法、Hash值的特点、以及和对象之间关系

哈希表也称散列表,是一种使用‌哈希函数组织数据的数据结构,它允许存储的数据元素以‌键值对(key-value)的形式存在,并通过直接访问对应的值

哈希函数也称为散列函数,即Object类中hashCode方法,借助该函数,可以将key-value映射到表中一个位置,从而加快查找的速度。

1)JDK8之前

Java中的哈希表(hash),JDK8之前是采用数组+链表进行实现,根据数据的哈希值,把数据存在数组中,但是当前哈希值冲突的时候,再使用链表进行存储,那么在数组中,同一hash值的数据都存在一个链表里。

例如,如果数据的哈希值相同,在数组使用使用链表存储哈希值相同的几个数据

注意:当链表中元素过多,即hash值相等的元素较多时,查找的效率会变低!

实际存储案例:

在这里插入图片描述

2)JDK8及其以后

JDK8中,哈希表存储采用数组+链表+红黑树进行实现,当链表长度超过**阈值(8)**时,将链表转换为红黑树,这样可以大大提高查找的性能。

例如,

在这里插入图片描述

标签:Java,链表,哈希,红黑树,数据结构,数据,节点,底层
From: https://blog.csdn.net/u012135697/article/details/140579541

相关文章

  • 每周JAVA学习总结
    一、隐式转换和强制转换隐式转换(自动类型转换)隐式转换是指编译器在程序运行时自动将一种数据类型转换为另一种数据类型,而无需程序员干预。隐式转换遵循以下规则:(1)数据范围小的类型可以自动转换为数据范围大的类型(低精度转高精度)。(2)转换过程中不会丢失精度。例如:inta=10;......
  • 《JavaSE》---19.<补充:内部类&匿名内部类>
    目录前言一、内部类1.1内部类的概念 1.2内部类的分类①实例内部类 【注意事项】②静态内部类(相比实例内部类用的更多)③局部内部类(几乎不用)④匿名内部类(在下面讲)二、匿名内部类2.1匿名内部类简单介绍前言本篇博客主要讲解Java基础语法中的一、内部类内部类......
  • Java面向对象程序三大特性:封装、继承、多态
    目录 引言一.封装二.继承三.多态四.结论 引言 在现代软件开发中,面向对象编程(OOP)已成为一种流行且有效的编程范式,其中Java语言以其高效性和灵活性深受开发者的喜爱。面向对象编程的核心在于其三大特性:封装、继承和多态。这些特性不仅提高了代码的重用性和可维......
  • Java 语言及其常用集合类的操作,以及反射机制与注解
    目录一、Java语言概述二、Java集合框架ArrayList操作示例:HashMap操作示例:三、反射机制1.反射的示例五、总结Java是一种广泛使用的高级编程语言,因其平台独立性、简洁性及丰富的API而备受开发者青睐。一、Java语言概述 Java语言由JamesGosling等人......
  • Java线程池ForkJoinPool原理分析
    目录1.由一道算法题引发的思考2.基于归并排序算法实现2.1什么是归并排序2.2归并排序动图演示2.3使用归并排序实现上面的算法题单线程实现归并排序Fork/Join并行归并排序2.4并行实现归并排序的优化和注意事项3.Fork/Join框架介绍3.1什么是Fork/Join3.2应用......
  • springboot基于Java的人力资源管理系统的设计与实现人事管理工资员工管理系统(源码+lw
    具体实现截图技术栈后端框架SpringBoot采用springboot作为后台的框架,java框架具有简化配置和开发的效率。Spring框架目前是很多java开发者的首选框架,Spring主要有两大功能,控制反转和面向切面的编程。控制反转(IOC)可以实现代码的依赖注入,减少代码......
  • springboot基于Java的企业人才引进服务平台的设计与实现(源码+lw+部署文档+讲解等)
    具体实现截图技术栈后端框架SpringBoot采用springboot作为后台的框架,java框架具有简化配置和开发的效率。Spring框架目前是很多java开发者的首选框架,Spring主要有两大功能,控制反转和面向切面的编程。控制反转(IOC)可以实现代码的依赖注入,减少代......
  • Java工具库——Hutool的常用方法
    Hutool-All(或简称Hutool)是一个功能强大的Java编程工具库,旨在简化Java应用程序的开发。它提供了大量的工具类和方法,涵盖了各种常见任务,包括字符串处理、日期时间操作、文件操作、网络通信、加密解密、数据转换、图像处理、JSON操作、Excel处理、邮件发送等等。以下是Hutool-All的......
  • Java学习日历(static,工具类,继承)
    staticstatic表示静态,是Java中的一个修饰符,可以修饰成员方法,成员变量。特点:被该类所有对象共享不属于对象,属于类随着类的加载而加载,优先于对象存在调用方式:类名调用(推荐)对象名调用工具类帮助我们做一些事情的,但是不描述任何事物的类类名见名知意私有化构造方法......
  • JAVA学习篇(1)初学JAVA
    一.了解JAVAJava是一门面向对象的编程语言,不仅吸收了C++语言的各种优点,还摒弃了C++里难以理解的多继承、指针等概念,因此Java语言具有功能强大和简单易用两个特征。Java具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点。Java可以编写桌......