IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 《码出高效:java开发手册》六-数据结构与集合(一) -> 正文阅读

[数据结构与算法]《码出高效:java开发手册》六-数据结构与集合(一)

前言

本章主要是讲数据结构与集合,这章内容涉及到非常基础的知识,内容相对较多,首先从数组讲起,引申到集合框架,之后再到集合源码,最后介绍了高并发集合框架

集合

集合在代码中是collection,对应英文为set,具有确定性,无序性,互异性的特点。java中的集合元素可以是有序的,也可以是重复的,与数学中的要求不同,这章的内容都是指collection,用来保存各种对象的集合

数据结构

  • 定义:数据结构是一种逻辑上的数据组织和处理方式,这里的逻辑意义很关键,以二叉树为例,它不是像一颗树形进行存储,物理保存时是一个格子存一个节点;数据组织方式就是那些树,图,队列,哈希之类,这些都是组织方式;处理方式指的是以特定的算法进行数据的增加,删除,修改,查找和遍历,这些不同的处理方式间会有性能差异
  • 数据结构的分类:数据结构是算法的基础,如果有缺陷就会造成系统风险高,可拓展性差,根据直接前后继的角度可以把数据结构分为以下四类
    1.线性结构:0到1个直接前驱和后继,非空时有唯一的首尾元素,包括顺序表,链表,栈,队列等
    2.树结构:0到1个直接前驱和0到n个直接后继(n>=2)
    3.图结构:0到n个直接前驱和直接后继
    4.哈希结构:没有直接前驱和后继,通过哈希函数索引,查找效率很高
  • 衡量数据处理性能:时间复杂度和空间复杂度,量级描述有
    在这里插入图片描述
    在这里插入图片描述
    实际场景中数据规模大了以后,算法性能差异会变得很明显

集合框架图

java集合是一种用于存储对象的容器,提供增删改查和遍历方法,下图为java中实际的集合框架图
在这里插入图片描述
蓝色是抽象类,红色是接口,绿色是并发包里的类,灰色是一些线程安全的类,基本已经弃用
其中最主要的就是四个:List,Set,Queue,Map

list集合

List是线性数据结构,存在明确的前驱后继元素,明确的首尾元素,遍历结果稳定,常用集合类有arraylist和linkedlist

  • arraylist容量可改变,线程不安全,支持对元素快速随机访问,但插入删除时很慢,因为需要移动元素
  • linkedlist是双向链表,相比arraylist,它插入删除速度更快,但随机访问很慢,它继承了AbstractList抽象类和Deque接口,Deque接口具有队列和栈的性质
    LinkedList有三个重要成员:size,first,last;size是节点个数,first指向头节点,last指向最后一个节点,LinkedList的优点在于把零散内存单元关联起来,提高了内存利用率

Queue集合

Queue即队列,是一种先进先出的线性表,两端分别只能获取和插入,没有元素称为空队列
BlockingQueue阻塞队列可在高并发的场景下作为数据缓冲区使用

Map集合

Map集合是以Key-value键值对存储元素的哈希结构,key不可重复,值可重复;
KeySet()查看所有key,values()查看所有value,entryset()查看所有键值对,hashtable已经被淘汰,HashMap线程不安全,ConcurrentHashMap线程安全,JDK8中对锁进行了优化,TreeMap是Key有序的Map集合,多线程并发中推荐使用ConcurrentHashMap而非HashMap

Set集合

元素不重复,常用HashSet,TreeSet和LinkedHashSet
HashSet是HashMap把Value固定住,用Key保证集合元素唯一性,不保证有序性
TreeSet是TreeMap实现,底层为树结构,插入时会比较保证有序性
LinkedHashSet继承HashSet,有HashSet的优点,内部用链表保证元素插入顺序

集合初始化

集合初始化需要分配容量,设置参数,比如ArrayList和HashMap,分别是顺序表和哈希结构,从源码可以看到他们的初始化逻辑
ArrayList
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这段代码可以看出:

  • 扩容时,可能超出int的最大值,超出就返回原来的长度
    扩容时是利用位移运算,二进制下右移一位,再加到旧的长度上
    在JDK7之前,扩容方式是旧容量x3÷2+1,也就是1.5倍加1
    初始化时默认为10,那么第一次add后每次扩容都使用array.copyof,会创建一个新的数组再复制,如果是1000个元素,就会扩容13次,很影响性能,但如果初始化1000长度,就不需扩容,对于更大的值,甚至会有oom风险
  • HashMap放1000个元素,需要扩容7次,扩容需要重建hash表,很影响性能,
    HashMap有两个参数,Capacity和LoadFactor;Capacity决定存储容量,默认16,LoadFactor决定填充比例,默认0.75,两者之积是threshold,就是能放入的元素个数
    HashMap不会在new时分配,而是在第一次put时完成创建
    HashMap的容量大小为2的n次方,就是为了在运算时能充分散列,这块详细在之前的面试题里有讲
    初始化ArrayList是10,HashMap是16,默认值最好是预估一个范围,避免扩容造成的损耗

数组与集合

数组是一种顺序表,下标从0开始,这样设计是为了方便计算偏移量,否则就要-1,提倡类型紧挨着中括号,比如int[]来定义数组,就相当于定义数组对象
可以用两种方法定义
在这里插入图片描述
args3是静态初始化,args4是动态初始化,动态初始化new后面要给初始容量,动态数组有Vector和
Arraylist操作,分别是线程安全但性能差,线程不安全但使用频繁
数组遍历优先推荐使用foreach方法,for(元素:数组名),可以不使用下标
需要使用下标可以用for循环,数组用length属性获取长度
也可以用jdk8的函数式接口遍历
在这里插入图片描述

  • 数组与集合的互相转换:Arrays.asList ()可以把数组转换为集合,但注意不能使用修改集合的方法,例如add/remove/clear,否则报Uns upportedOperationException异常,因为aslit方法是一种适配器模式,后台数据仍是原有数组,set方法可以修改,但其他就会抛出异常
  • 在这里插入图片描述

如图,这是arraylist的内部类,实际返回的是这个类,它只实现了部分方法,这个异常由其父类抛出

在这里插入图片描述
实际业务中,为避免数组转集合时添加元素引发异常,可以用java.util.arrayList直接创建一个新集合
,参数就是aslist方法返回的不可变集合
在这里插入图片描述

  • 集合转数组,相对更加可控,通常用于适配别人的数组接口,或者进行局部方法计算
    在这里插入图片描述
    在这里插入图片描述
    如图,不要用toarray()无参方法转换集合,会导致泛型丢失
    也要注意数组容量是否分配足够,书中实验了不同容量对性能影响,结果如下
    在这里插入图片描述
    可见,数组容量正好时,运行最快,使用toArray()时,注意两点
    1,传入类型完全一致的数组
    2.它的容量应该为list.size()

集合和泛型

泛型用在集合上,有很强效果,但也要注意类型转换异常
在这里插入图片描述
这种放入不同类型元素,转换就会出现类型转换异常
在这里插入图片描述
赋给object是可以的,也可以继续添加不同类型的元素
在这里插入图片描述
在这里插入图片描述
但赋给integer后,再赋值不同类型就会不允许
在这里插入图片描述
这里问号在正则表达式里可以匹配任何字符,这个list也就可以接受任何类型引用赋值,可以remove和clear,但不可以添加元素,一般用作为参数接收外部集合或者返回未知类型的集合

  • List只能放置一种类型,不能随意转换,如果需要放置多种受泛型约束的类型,则可以用<? extends T>与<? super T>,前者是get first,适合消费为主的集合,后者是put first,适合生产为主的集合
  • <? extends T>可以赋值给任何T 及T 子类的集合,上界为T 取出来的类型带有泛型限制, 向上强制转型为T。null 可以表示任何类型,所以除null 外,任何元素都不得添加进<? extends T> 集合内。
  • <? super P 可以赋值给任何T 及T 的父类集合,下界为T。在生活中,投票选举类似于<? super T> 的操作。选举代表时,你只能往里投选票,取数据时,根本不知道谁的票,相当于泛型丢失;比如一些评价问卷,提交后不能再访问链接修改评价
  • 总结:extends put受限,super get 受限,如果经常往出取的话,使用extends,经常放的话,使用super

元素的比较

  • comparable和comparator
    java元素的排序经常用到比较,比较有两个常用接口:Comparable和Comparator,分别用compare to和compare方法实现比较
    自然排序,也就是123,abc这种,Integer和String中实现的就是Comparable自然排序,有时需要自己定义排序规则,就可这样做
    在这里插入图片描述
    在这里插入图片描述
    实现Comparable,可以加上泛型限定,这样就可以在编译期间检查传入参数是否是SearchResult对象,免去类型检查和强转,如果是封包类或者是开闭原则,就可以利用外部比较器,Comparator,代码如下
    在这里插入图片描述
    JDK中Arrays.sort的比较器参数排序就是Comparator实现的
    在这里插入图片描述
    在这里插入图片描述
    这里的<? super T>是泛型限制为T及其父类,直到Object

两个比较器返回值都是小于-1,等于0,大于1;在集合中比较器排序,直接使用正负返回比较结果
在这里插入图片描述

  • 上面的TimSort方法是归并排序加插入排序,避免了两者缺点,减少了归并次数,引入了二分排序概念,加快了效率,对于部分有序的数组,时间复杂度可达O(n),随机排序数组则是nlogn,它主要有两个优化
    1.归并排序的分段不再从单个元素开始,而是每次先查找最大的有序数组片段run,然后利用二分排序,将该run与其他有序的run进行归并
    2.引入二分排序,使得插入排序中每次不再从后向前比较,时间复杂度由n降低到nlogn

hashCode和equals

这两个方法用来判断两个对象是否相同,通常协同工作,首先Object.hashcode生成哈希值,相同则进一步比较equals,不同则直接返回不同
如下是object类对这两个方法的要求
在这里插入图片描述在这里插入图片描述

如上是HashMap的get方法代码判断,先比较hash值,后执行阴影部分,equals一般不要求hashcode相同,但hashcode散列充分,降低冲突,有利于提高执行效率
在这里插入图片描述
如上是没有重写hashcode的案例,之后放到hashset里
在这里插入图片描述
本该结果是,但执行结果是3,说明不重写hashcode,重写了equals毫无意义,如果想要存储不重复元素,重写hashcode版本如下
在这里插入图片描述

这个name是String类型,自带hashcode重写,直接调用即可

  • equals的判定逻辑与类的具体情况有关,在这里插入图片描述
    在这里插入图片描述
    上面代码的var就是动态类型,jdk10引入的语法糖,它会检测右边类型,并应用于左侧
    第2处可能抛出空指针npe异常,推荐使用jdk7自带equals方法,代码如下
    在这里插入图片描述

在这里插入图片描述
上面这段代码可以看出它是类型可变化的,也有类型限定格式

fail-fast机制

  • fail-fast机制是一种错误检测机制,主要用于遍历集合元素过程中

  • 书中举了个例子,班长点全班同学的名,这里是遍历的意思,然后有人进进出出,就老是需要重新点名,这就是fail-fast机制
    多线程时,维护一个expectedModCount,记录已经修改的次数,进入遍历前把实时修改次数modCount付给eMC,如果两个值不同就报异常

  • java.util包下都是fail-fast,concurrent下都是fail-safe,failsafe就是相当于班长直接拍照,然后用照片点名,不管进出

  • 比如arraylist.sublist(),获取子列表时,主列表的元素变化会引起子列表的遍历和元素增删,进而出现fail-fast异常
    -
    如上代码,通常比较常见的是修改子列表会影响父列表,但比较少见的是父列表改动会导致子列表操作异常
    subList返回Sublist类的对象,它是ArrayList的内部类,没有实现序列化接口,无法网络传输

  • 在foreach循环中测试fail-fast机制,如下

  • 在这里插入图片描述这段代码运行没有报异常,这是一个特例,因为游标遍历到size的时候,退出了遍历,执行remove后,size=size-1=2,这时cursor也等于2,执行hasnext时值为false,也就不会执行next()的checkForComodification方法,这个方法就是用来判断expectedMod和modcount的,不同会抛异常,都没有执行,也就不报异常

  • 在这里插入图片描述

  • 为了避免删除元素引起fail-fast,可以用Iteator进行遍历时删除,多线程并发时,还需要加锁,如下

  • 在这里插入图片描述- 也可以使用并发容器CopyOnWriteArrayList代替ArrayList,内部对迭代器进行了加锁操作
    它的原理是读写分离,在写操作时分出一个新集合,在里面操作添加删除,之后把原集合引用指向新集合,用COW的时候要注意1.设置合理初始值,扩容代价较大2.添加删除可以攒一下,积累一些再操作,避免频繁复制整个几个,导致内存占用,进而频繁GC影响服务器性能
    在这里插入图片描述如上代码,20万次循环数据插入花费了97.8秒,ArrayList只需39毫秒,这样就得不偿失了,所以COW只适合于读多写少的场景

  • COW是fail-safe的,并发包中的集合都是这种机制实现的,也就是在安全的副本中遍历,集合修改与副本遍历无关,缺点就是读取不到最新数据,这反映了一致性和可用性的矛盾

Map集合

Map是与Collection平级的一个借口,它也与Collection有关联:部分方法比如values()会返回Collection视图,一个vaule的列表。Map集合的存储单位是KV键值对,就是用哈希算法做一组比较均匀的Key,然后把Vaule挂在上面
特点有:
取代了Dictionary类,性能更好
Key不重复,Vaule可重复
Vaule可以试List,Map,Set类对象
KV是否允许为空,以实现类约束为准

  • Map接口除了crud,还有KeySet,values,EntrySet方法
  • 在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    这些返回的视图支持删除,但修改添加元素会报异常,因为AbstractCollection没有add操作,但有remove,clear等操作
    在这里插入图片描述这些集合类见证了java进化的过程,线程不安全到线程安全
    使用时,直接用ConcurrentHashMap代替HashMap大多数时间可行,性能差别不大,线程安全,但是尽量要避免设置KV为空值或者做好空值判断,避免NPE

红黑树

首先介绍树,树是一种有限节点(结点)组成的层次集合,数据存在节点中,顶层的唯一节点称为根节点,底层没有分支的称为叶子节点,。从某节点出发,到叶子节点为止,最长简单路径上的条数称为该节点的高度,从根节点出发,到某节点边的条数,称为该节点的深度
在这里插入图片描述
这棵树,根节点高度为5,深度为0,节点2的深度是1.高度是4
树结构有五个特点
( I )一个节点,即使只有根节点,也可以是一棵树。
( 2 )其中任何一个节点与下方所有节点构成的树称为子树。
( 3 )根节点没有父节点,而子节点没有父节点。
( 4 )除根币点外任何节点有且仅有个1父节点。
( 5 )任何节点可以有0 ~ n 个子节点(0-n叉树)。
在二叉树世界中,最重要的是平衡二叉树,二叉查找树,红黑树

平衡二叉树

如果把一棵树的树枝砍到只剩一条路径,那么它就变成一个类似链表,约束一棵树具有层次结构,就是平衡二叉树
平衡二叉树的性质如下
( 1 )树的左右高度差不能超过1。
( 2 )任何往下递归的左子树与右子树,必须符合第一条性质。
( 3 )没有任何节点的空树或只有根节点的树也是平衡二叉树。
在这里插入图片描述

二叉查找树
  • 二叉查找树又称二叉搜索树,BST(BinarySearchTree),或者Sort,二叉排序树,节点的左子树比它小,右子树比它大。
    从根节点开始,大于往右,小于往左,直到叶子节点就是没找到。
    遍历所有节点的方法有三种:前序遍历,中序遍历,后序遍历
    这些遍历规律有:1.任何遍历,左节点一定先于右节点2.前中后序,指的是根节点在遍历序列中的位置
    前序就是根左右,中序就是左根右,后序就是左右根,下面这张图非常直观
    在这里插入图片描述
    下面是一个普通树转换为二叉查找树的过程,它的子树也是查找树
    在这里插入图片描述
    二叉查找树的元素有增删时可能会失衡,比如用AVL树,红黑树,SRB,树堆就是用来解决这个问题的
AVL树

avl树是一种平衡二叉树算法,可以让二叉树的使用效率最大化,增删元素后,就会通过旋转重新达到平衡。
下图展示了右旋和左旋的过程,一般是左长右短右旋,反之左旋,有一些右边的左子树失衡,需要lr或者rl旋转,比较复杂
在这里插入图片描述

在这里插入图片描述

红黑树

72年发明了对称二叉B树,后来改名为红黑树,主要特征是每个节点有一个颜色属性,红或者黑色
红黑树也是插入删除后进行旋转保持平衡,但它的平衡不是左右高度差不大于1,而是从根节点到叶子节点的最长路径不超过最短路径的二倍
它有五个约束条件
1、节点都是红或者黑色
2、根节点必须是黑色
3、所有NIL(叶子节点下挂的两个虚节点)节点都是黑色
4、一条路径不能有两个红节点相连
5、任何递归子树中,根节点到叶子节点的黑节点数目相等
总结:有红必有黑,红红不相连,这些条件的意义在于可以控制最坏时间复杂度为logn,红黑树任何旋转均可在三次内

红黑树与AVL树相比

红黑树的黑深度满足Black Depth小于等于 height / 2,也就是含有n个节点的红黑树,根节点高度一定小于2log2( n + l )
常规BST的操作,时间复杂度为h,取决于树高度
红黑树平衡性不如AVL树,它维持的是大致的平衡,而失衡时恢复也比avl更简单,最差时间复杂度更低
结论:频繁插入删除时,红黑树更好;低频修改,大量查询时,AVL树更好
如下图是按顺序插入36.34.37.33.35.32
在这里插入图片描述
可以看到红黑树不是绝对平衡的

TreeMap

TreeMap用Key的排序重新组织了Map的结构,相比ConcurrentHashMap和HashMap,插入删除效率降低了,但在要求Key排序的场景下,TreeMap更加高效,它与另外两个都继承与AbstractMap抽象类
在这里插入图片描述
TreeMap有继承这两个接口:SortedMap和NavigableMap,前者Key是有序不可重复的,插入Key时需要比较,所以key不可为空,value可空
NavigableMap接口继承了继承了SortedMap,根据搜索条件提供适合的KV元素,同时TreeMap可以不重写Hashcode和equals来去重Key
在这里插入图片描述
在这里插入图片描述

上面的代码hashmap下size是1,因为两者使用的去重办法不同,如果要用TreeMap要对Key排序,调用方法如下
在这里插入图片描述
Comparator为空则调用compareto方法,不为空调用compare方法
都不满足就抛出异常:在这里插入图片描述
TreeMap的crud操作的最好最坏时间复杂度均为(logn),特点是key有序
在这里插入图片描述
在这里插入图片描述
TreeMap通过put和deleteEntry方法实现红黑树的增删节点操作,删除类似插入,只讲插入操作
需要调整的新节点一定是红色的
插入的新节点是黑色的,无需调整
插入新节点是红色的,由于红黑树不能红红相邻,就要重着色,或者左右旋转
在这里插入图片描述
根节点直接退出,设置为黑色即可,不是根节点且父节点是红色,则一直调整直到退出循环
TreeMap的插入操作是正常比较,小于向左,按照二叉查找树规则,无需关心颜色平衡,后续会调整
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

插入时要之前为非空树并且新节点的Key和任何节点都不同,才能运行到FixAfterInsertion进行着色并且旋转

后记

这篇字数已经一万三左右,后续写在第二篇

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:38:25 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/25 13:37:35-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码