当前位置:网站首页 > Java基础 > 正文

java架构基础



Java架构核心基础

lecture:波哥

一、数据结构和算法

1.数据结构

  数据结构是、的方式。数据结构是指相互之间存在一种或多种特定关系的的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。接下来分别介绍下常见的数据结构类型。

1.1 线性结构

1.1.1 数组

  数组(Array)是一种线性表数据结构。它用于存储具有固定大小的相同类型的数据元素。在数组中,数据元素按照有序的方式进行排列,可以通过索引访问数组中的任意位置的元素。

 

数组的特点如下:

  1. 顺序存储:数组中的元素按照顺序存储在连续的内存空间中,每个元素都有一个唯一的索引,可以通过索引快速访问。
  2. 大小固定:一旦定义了数组的大小,就不能改变。如果需要更大的存储空间,需要重新定义一个新的数组。
  3. 元素类型相同:数组中的所有元素必须是相同的数据类型。
  4. 无界数组:数组的长度可以是任意的整数,只要内存空间足够。

在这里插入图片描述

数组的优点:

  1. 访问速度快:由于数组是顺序存储的,可以通过索引直接访问数组中的元素,时间复杂度为O(1)。
  2. 易于实现:数组是一种简单的数据结构,容易实现和操作。

数组的缺点:

  1. 大小固定:数组的大小是固定的,不能动态扩展。如果需要更多的存储空间,需要重新定义一个新的数组,这会增加额外的开销。
  2. 空间利用率低:由于数组是连续的内存空间,即使某些位置没有被使用,也不能被其他数据结构使用,导致空间利用率较低。
1.1.2 队列

  队列是一种特殊的数据结构,其特点是遵循先进先出(FIFO)的原则。队列中的元素只能从一端(称为队尾)添加,而从另一端(称为队头)删除。

队列的特点如下:

  1. 先进先出:队列中的元素遵循先进先出的原则,即最早进入队列的元素最先被删除。
  2. 插入和删除操作发生在同端:队列中的插入操作发生在队尾,删除操作发生在队头。
  3. 无界队列:队列的长度可以是任意的整数,只要内存空间足够。

在这里插入图片描述

数据结构演示地址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Java代码的具体实现

 
1.1.3 链表

  链表是一种常见的数据结构,它通过指针将一组零散的内存块串联在一起。链表中的每个内存块被称为节点,每个节点除了存储数据之外,还需要记录链上的下一个节点的地址。

链表的特点是:

  1. 不需要连续的内存空间。
  2. 有指针引用。
  3. 插入、删除数据效率高,时间复杂度为O(1)级别(只需更改指针指向即可);但是,随机访问效率低,时间复杂度O(n)级别(需要从链头至链尾进行遍历)。
  4. 和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

链表包括、和等类型。其中,单向链表的节点只有一个后继指针next指向后面的节点;双向链表的节点除了有一个后继指针next指向后面的节点外,还有一个前驱指针prev指向前面的节点;循环链表与单向链表的唯一区别是尾节点的指针指向头节点,形成一个环。

在这里插入图片描述

在这里插入图片描述

1.1.4 栈

  栈(Stack)是一种后进先出(LIFO)的数据结构,它只能在一端进行插入和删除操作,这一端被称为栈顶,另一端被称为栈底。栈的元素之间存在一种顺序关系,这种顺序关系由元素的插入和删除操作决定。

栈的主要操作有:

  1. 入栈(push):在栈顶添加一个元素。
  2. 出栈(pop):删除栈顶的元素并返回其值。
  3. 判断栈空(is_empty):检查栈是否为空。
  4. 获取栈顶元素(top):返回栈顶的元素值,但不删除它。

在这里插入图片描述

1.2 非线性结构

  非线性表:与线性表对立,在非线性表之中,数据之间并不是简单的前后关系。非线性结构是一种相对复杂的数据结构,它不满足线性结构的数据元素之间的一对一关系。非线性结构包括图结构、树结构、二维数组、广义表、多维数组等。

  在非线性结构中,数据元素之间存在多对多的关系,这种关系可以通过指针、引用等来实现。非线性结构可以用来表示复杂的数据关系,例如网络关系、图形关系等。

  本课程中我们介绍下和Java关联性比较强的非线性结构-树

1.2.1 树

[Tree]是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:

  1. 有且仅有一个特定的称为根[Root]的结点;
  2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、…、Tn,其中每一个集合本身又是一棵树,并且称为根的子树。

  此外,树的定义还需要强调以下两点:

  1. 根结点是唯一的,不可能存在多个根结点,数据结构中的树只能有一个根结点。
  2. 子树的个数没有限制,但它们一定是互不相交的。

如图,是一棵普通树

在这里插入图片描述

度数:结点拥有的子树数目称为结点的

在这里插入图片描述

节点关系:

  • 孩子结点
  • 双亲结点
  • 兄弟结点

节点层次:

  从根开始定义起,根为第一层,根的孩子为第二层,以此类推。

在这里插入图片描述

树的深度:树中结点的最大层次,如上图深度为4

根据不同的分类方式,树可以分为不同的类型:

  1. 根据树分支的数量限制:可以分为二叉树和多叉树。二叉树最多只有两个子节点,而多叉树一个节点可以有多于两个的子节点。
  2. 根据树节点的有序性:可以分为查找树和无序树。查找树的基本特征为任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值。无序树则没有特定的键值大小关系。
  3. 根据具体用途和特征:例如、、、等。是一种自平衡二叉查找树,也是一种自平衡二叉查找树,它要求任何节点的两个子树的高度差最大为1。平衡二叉树和平衡二叉搜索树则是为了平衡树的左右子树的高度差。
  4. 根据树的完整性和是否包含空值:可以分为完全二叉树、满二叉树、完全二叉搜索树、满二叉搜索树等。完全二叉树和满二叉树是包含所有节点的二叉树,而完全二叉搜索树和满二叉搜索树则是所有节点都按照一定顺序排列的二叉搜索树。
1.2.2 二叉树

  每个子节点只有两个节点的树,每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

在这里插入图片描述

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵树具有如下性质:

  1. 任意节点左子树不为空,则左子树的值均小于根节点的值
  2. 任意节点右子树不为空,则右子树的值均大于于根节点的值
  3. 任意节点的左右子树也分别是二叉查找树
  4. 没有键值相等的节点

二叉树又分为:

  • 完美二叉树
  • 完全二叉树
  • 完满二叉树

完美二叉树:又称为 满二叉树 ,除了叶子节点之外的每一个节点都有两个孩子节点,每层都被完全填充

在这里插入图片描述

完全二叉树:除了最后一层之外的其他每一层都被完全填充,并且所有的节点都保持向左对齐

在这里插入图片描述

完满二叉树:除了叶子节点之外的每一个节点都有两个孩子节点。

在这里插入图片描述

二叉树的遍历操作

二叉树中的遍历规则有如下三种:

中序遍历:所谓的中序遍历就是先访问左节点,再访问根节点,最后访问右节点,即左-根-右遍历

先序遍历:所谓的前序遍历就是先访问根节点,再访问左节点,最后访问右节点,即根-左-右遍历(前序)

后序遍历:所谓的后序遍历就是先访问左节点,再访问右节点,最后访问根节点。即左-右-根遍历

在这里插入图片描述

查找最小值:沿着根节点的左子树一路查找,直到最后一个不为空的节点,该节点就是当前这个树的最小节点

查找最大值:沿着根节点的右子树一路查找,直到最后一个不为空的节点,该节点就是当前这个树的最大节点

查找前驱节点 :小于当前节点的最大值

查找后继节点 :大于当前节点的最小值

在这里插入图片描述

二叉树的删除操作:

二叉树中的删除节点:本质上是找前驱节点或者后继节点来替代

  • 叶子节点直接删除
  • 只有一个子节点的用子节点替代(本质上就是找的前驱节点或者后继节点,左节点就是前驱节点,右节点就是后继节点)
  • 有两个子节点的,需要找到替代节点(替代节点就是前驱节点或者后继节点)

二叉树的查找的局限性:

一个二叉查找树是由n个节点随机构成,所以,对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图:

在这里插入图片描述

1.2.3 AVL树

  BST存在的问题是,树在插入的时候会导致倾斜,不同的插入顺序会导致数的高度不一样,而树的高度直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上,这样树的高度为N。基于BST存在的问题,平衡查找二叉树(Balanced BST)产生了。平衡树的插入和删除的时候,会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树(高度平衡树,具备二叉搜索树的全部特性,而且左右子树高度差不超过1)和红黑树。

AVL树是如何实现平衡的呢?,具体是通过左旋或者右旋来实现的。具体如下图:

在这里插入图片描述

  虽然AVL可以解决二叉树所存在的问题,但是AVL树要求太过严格,左旋和右旋的开销会比较大,这时出现了红黑树,只要求黑色节点平衡即可.

1.2.4 2-3-4树

  是四阶的 B树(Balance Tree),他属于一种多路查找树,它的结构有以下限制:所有叶子节点都拥有相同的深度。节点只能是 2-节点、3-节点、4-节点之一。

  • 2-节点:包含 1 个元素的节点,有 2 个子节点;
  • 3-节点:包含 2 个元素的节点,有 3 个子节点;
  • 4-节点:包含 3 个元素的节点,有 4 个子节点;

  所有节点必须至少包含1个元素,元素始终保持排序顺序,整体上保持二叉查找树的性质,即父结点大于左子结点,小于右子结点;而且结点有多个元java架构基础素时,每个元素必须大于它左边的和它的左子树中元素。

下图是一个典型的 2-3-4树:
在这里插入图片描述

生成的过程
  接下来我们通过演示来看看2-3-4树生成的过程
第一次插入—2节点

在这里插入图片描述

插入第二个节点–3节点 合并

在这里插入图片描述

插入第三个节点—4节点 合并

在这里插入图片描述

插入第4个节点—需要分裂

在这里插入图片描述

插入6

在这里插入图片描述

插入7

在这里插入图片描述

插入8

在这里插入图片描述

插入9

在这里插入图片描述

插入10

在这里插入图片描述

插入11

在这里插入图片描述

插入12

在这里插入图片描述

最后我们插入1来看看效果

在这里插入图片描述

  到这儿相信大家对于2-3-4树应该有了个直观的认知了。然后来看看和的对应关系。这个能帮助我们更好的理解红黑树.

  红黑树起源于2-3-4树,它的本质就是2-3-4树。

:一个2节点对应的红黑树节点就是一个黑色节点

在这里插入图片描述

:一个三节点可以有两种情况的红黑树节点,一种是右倾,一种是左倾,所以一个2-3-4树可以有多个红黑树

在这里插入图片描述

原则:上黑下红

:一个四节点转换的情况只有一种,中间节点黑色,左右节点红色

在这里插入图片描述

:还有就是在2-3-4树中存在的裂变状态。转换为红黑树后会先变色(不能有两个相邻的红色节点)。

在这里插入图片描述

:接下来具体看看一个2-3-4树是如何转换为对应的红黑树的,

原始的2-3-4树:

在这里插入图片描述

  按照右倾规则来转换为:

在这里插入图片描述

在这里插入图片描述

  通过对2-3-4树和红黑树的等价关系,对于我们后面分析红黑树的内容会非常有帮助!!!

1.2.5 红黑树

  红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST),树上的每个节点都遵循下面的规则:

  1. 每个节点要么是黑色,要么是红色。
  2. 根节点是黑色。
  3. 每个叶子节点(NIL)是黑色。
  4. 每个红色结点的两个子结点一定都是黑色。
  5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

  红黑树能自平衡,它靠的是什么?三种操作:左旋、右旋和变色

操作描述左旋以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,
右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。右旋以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,
左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变。变色结点的颜色由红变黑或由黑变红。

  左旋:以某个节点作为旋转点,其右子节点变为旋转节点的父节点,右子节点的左子节点变为旋转节点的右子节点,左子节点保持不变。

请添加图片描述

在这里插入图片描述

  右旋:以某!个节点作为旋转点,其左子节点变为旋转节点的父节点,左子节点的右子节点变为旋转节点的左子节点,右子节点保持不变。

请添加图片描述

在这里插入图片描述

Java代码实现旋转

  先进行类结构定义

 

左旋代码实现

 

右旋实现:

 

:https://www.processon.com/view/link/60c21e25e401fd34a1514d25

  2-3-4树中结点添加需要遵守以下规则:

  • 插入都是向最下面一层插入
  • 升元:将插入结点由 2-结点升级成 3-结点,或由 3-结点升级成 4-结点;
  • 向 4-结点插入元素后,需要将中间元素提到父结点升元,原结点变成两个 2-结点,再把元素插入2-结点中,如果父结点也是 4-结点,则递归向上层升元,至到根结点后将树高加1;

  而将这些规则对应到红黑树里,就是:

  • 新插入的结点颜色为 红色 ,这样才可能不会对红黑树的高度产生影响。
  • 2-结点对应红黑树中的单个黑色结点,插入时直接成功(对应 2-结点升元)。
  • 3-结点对应红黑树中的 黑+红 子树,插入后将其修复成 红+黑+红 子树(对应 3-结点升元);
  • 4-结点对应红黑树中的 红+黑+红 子树,插入后将其修复成 红色祖父+黑色父叔+红色孩子 子树,然后再把祖父结点当成新插入的红色结点递归向上层修复,直至修复成功或遇到 root 结点;

  公式:红黑树+新增一个节点(红色)=对等的2-3-4树+新增一个节点

新增节点案例

​   我们通过新增2-3-4树的过程来映射对应的红黑树的节点新增

在这里插入图片描述

1.新增一个节点,2 节点

在这里插入图片描述

2.新增一个节点,与2节点合并,直接合并

在这里插入图片描述

3.新增一个节点,与3节点合并,直接合并

插入的值的位置会有3种情况

在这里插入图片描述

对应的红黑树为:

在这里插入图片描述

4.新增一个节点,与4节点合并,此时需要分裂

在这里插入图片描述

插入值的位置可能是

在这里插入图片描述

对应的红黑树的结构为:

在这里插入图片描述

新增代码实现

  红黑树的新增规则我们理清楚了,接下来就可以通过Java代码来具体的实现了。

先实现插入节点,这就是一个普通的二叉树的插入

 

然后再根据红黑树的特点来实现调整(旋转,变色)

 

红黑树的删除操作:

  红黑树的节点的删除其实也分为两步:

  1. 先删除节点(这步和普通的二叉树删除是一样的)
  2. 然后再调整

  要删除这个节点先需要找到这个节点,找到节点就是普通的二分查找,具体代码如下

 

在这里插入图片描述

情况一

在这里插入图片描述

情况2:删除的是非情况1的节点,根据我们前面介绍的删除的规则,会找到对应的前驱和后继节点,那么最终删除的还是叶子节点

在这里插入图片描述

首先删除节点的代码为:

 

然后就是需要调整红黑树的平衡了。

删除后的平衡调整

1.情况一:自己能搞定的,对应叶子节点是3节点和4节点

在这里插入图片描述

2.情况二:自己搞不定,需要兄弟借,但是兄弟不借,找父亲借,父亲下来,然后兄弟找一个人去代替父亲当家

这种情况就是兄弟节点是3节点或者4节点

找兄弟节点

在这里插入图片描述

如果找到的兄弟节点是红色其实还要调整

在这里插入图片描述

执行如下调整先,先变色,然后左旋

在这里插入图片描述

在这里插入图片描述

找兄弟节点借

在这里插入图片描述

然后沿着7节点左旋

在这里插入图片描述

3.情况三:跟兄弟借,兄弟也没有(情同手足,同时自损)

兄弟节点是2节点,同时当前节点的父节点是红色节点的情况

在这里插入图片描述

删除后直接变色就可以了

兄弟节点是2节点,同时当前节点的父节点是黑色节点

在这里插入图片描述

变更操作为如下,如果继续有父节点那么还要递归处理

在这里插入图片描述

分析清楚了删除的3中情况,我们就可以撸处删除的调整的代码了

 

好了。红黑树的内容大家应该搞清楚了。同时TreeMap的代码大家也搞清楚了。你可以看看TreeMap的代码其实和我们上面写的代码是一样的

1.2.6 B树

在这里插入图片描述

B Tree的查找规则是什么样的呢?
  比如我们要在这张表里面查找30。
  因为30小于36,走左边。
  因为30大于23,走右边。
  在磁盘块7里面就找到了30,只用了3次IO。

这个效率会比AVL树的效率更高

1.2.7 B+树

  加强版多路平衡查找树
  因为B Tree的这种特性非常适合用于做索引的数据结构,所以很多文件系统和数据库的索引都是基于B Tree的。
  但是实际上,MySQL里面使用的是B Tree的改良版本,叫做B+Tree(加强版多路平衡查找树)。

B+树的存储结构:

在这里插入图片描述

MySQL中的B+Tree有几个特点:

  1. 它的关键字的数量是跟路数相等的;
  2. B+Tree的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。InnoDB 中 B+ 树深度一般为 1-3 层,它就能满足千万级的数据存储。搜索到关键字不会直接返回,会到最后一层的叶子节点。比如我们搜索id=28,虽然在第一层直接命中了,但是全部的数据在叶子节点上面,所以我还要继续往下搜索,一直到叶子节点。
  3. B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

在这里插入图片描述

总结一下, B+Tree的特点带来的优势:

  1. 它是B Tree的变种,B Tree能解决的问题,它都能解决。B Tree解决的两大问题是什么?(每个节点存储更多关键字;路数更多)
  2. 扫库、扫表能力更强(如果我们要对表进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵B+Tree拿到所有的数据)
  3. B+Tree的磁盘读写能力相对于B Tree来说更强(根节点和枝节点不保存数据区,所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多)
  4. 排序能力更强(因为叶子节点上有下一个数据区的指针,数据形成了链表)
  5. 效率更加稳定(B+Tree永远是在叶子节点拿到数据,所以IO次数是稳定的)

2.算法

  看完了基本的数据结构后我们还需要看看常用的一些算法。数据结构加算法就等于程序。

2.1 排序

  用于将一组数据按照特定的规则进行排序。排序算法可以分为内部排序和外部排序两种。

  1. 内部排序算法:
    • 冒泡排序(Bubble Sort):重复比较相邻的两个元素,如果顺序错误就交换位置,直到整个序列有序。
    • 插入排序(Insertion Sort):将待排序的元素插入已经排好序的序列中的正确位置,直到整个序列有序。
    • 选择排序(Selection Sort):每次从待排序序列中选择最小(或最大)的元素放到已排序序列的末尾,直到整个序列有序。
    • 快速排序(Quick Sort):选择一个基准元素,将比基准元素小的元素放在基准元素的左边,比基准元素大的元素放在基准元素的右边,然后递归地对左右两个子序列进行快速排序。
    • 归并排序(Merge Sort):将待排序序列划分为两个子序列,分别对两个子序列进行归并排序,然后将排序好的两个子序列合并成一个有序序列。
    • 堆排序(Heap Sort):将待排序序列构建成一个最大堆(或最小堆),然后依次取出堆顶元素,再对剩余元素进行堆调整,直到整个序列有序。
  2. 外部排序算法:
    • 多路归并排序:将待排序的数据分为多个有序的子序列,然后通过多次归并操作将这些子序列合并为一个有序序列。
    • 基于置换的排序:通过多次置换操作将待排序的数据重新排列成有序的序列。
    • 多层归并排序:将待排序的数据分成多个层次,每个层次都进行归并排序操作,最终得到一个有序序列。

不同的排序算法在时间复杂度、空间复杂度和稳定性等方面有所差异,选择合适的排序算法取决于具体的应用场景和数据规模。

2.2 查找

查找算法,也称为搜索算法,是一种用于在数据集中查找特定元素的算法。查找算法可以应用于各种数据结构,如数组、链表、树等。

常用的查找算法包括:

  1. 线性查找:顺序遍历数据集,逐个比较元素,直到找到目标元素或遍历完整个数据集。时间复杂度为O(n),其中n为数据集的大小。
  2. 二分查找:仅适用于已经排序的数据集。从数据集的中间元素开始比较,如果目标元素小于中间元素,则在左半部分继续查找;如果目标元素大于中间元素,则在右半部分继续查找;如果目标元素等于中间元素,则找到目标元素。时间复杂度为O(log n)。
  3. 哈希查找:通过哈希函数将目标元素映射到一个位置,然后在该位置进行查找。哈希查找的平均时间复杂度为O(1),但是在处理哈希冲突时可能需要线性查找。
  4. 二叉查找树:将数据集构建成二叉查找树,其中每个节点的左子树的值小于节点的值,右子树的值大于节点的值。通过比较目标元素和节点的值,可以在二叉查找树中进行快速查找。
  5. 平衡二叉查找树:在二叉查找树的基础上,通过旋转操作保持树的平衡,以提高查找效率。常用的平衡二叉查找树有红黑树、AVL树等。
  6. B树和B+树:适用于大规模数据的查找,将数据集分散存储在多个节点中,通过多级索引进行查找。B树和B+树的高度较小,能够减少磁盘I/O操作,提高查找效率。
  7. 字符串匹配算法:用于在文本中查找特定的字符串。常用的字符串匹配算法有暴力匹配算法、KMP算法、Boyer-Moore算法等。

二、HashMap源码

1. 设计原理

  HashMap 基于哈希表的 Map 接口实现,是以 key-value 存储形式存在,即主要用来存放键值对。HashMap 的实现不是同步的,这意味着它不是线程安全的。它的 key、value 都可以为 null,此外,HashMap 中的映射不是有序的。

  jdk1.8 之前 HashMap 由 组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突(两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用)而存在的(“拉链法”解决冲突)。jdk1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为 8 )并且当前数组的长度大于 64 时,此时此索引位置上的所有数据改为使用存储。

补充:将链表转换成红黑树前会判断,即便阈值大于 8,但是数组长度小于 64,此时并不会将链表变为红黑树,而是选择逬行数组扩容。

  这样做的目的是因为数组比较小,尽量避开红黑树结构,这种情况下变为红黑树结构,反而会降低效率,因为红黑树需要逬行左旋,右旋,变色这些操作来保持平衡。同时数组长度小于64时,搜索时间相对要快些。所以结上所述为了提高性能和减少搜索时间,底层阈值大于8并且数组长度大于64时,链表才转换为红黑树,具体可以参考 treeifyBin() 方法。

  当然虽然增了红黑树作为底层数据结构,结构变得复杂了,但是阈值大于 8 并且数组长度大于 64 时,链表转换为红黑树时,效率也变的更高效。

HashMap 特点:

  1. 存储无序的。
  2. 键和值位置都可以是 null,但是键位置只能存在一个 null。
  3. 键位置是唯一的,是底层的数据结构控制的。
  4. jdk1.8 前数据结构是链表+数组,jdk1.8 之后是链表+数组+红黑树。
  5. 阈值(边界值)> 8 并且数组长度大于 64,才将链表转换为红黑树,变为红黑树的目的是为了高效的查询。

JDK1.7的结构

在这里插入图片描述

JDK1.8的结构

在这里插入图片描述

扩容的结构

在这里插入图片描述

在这里插入图片描述

2.源码分析

2.1 成员变量

  先来看看在HashMap中定义的相关成员变量

https://www.processon.com/view/link/654b410ccf851f1bbdc5f5ce

在这里插入图片描述

2.2 构造方法

  然后来看看相关构造方法做了什么操作

HashMap()

构造一个空的HashMap,默认初始容量(16)和默认负载因子(0.75)

 

HashMap(int initialCapacity)

构造一个具有指定的初始容量和默认负载因子(0.75)HashMap 。

 

HashMap(int initialCapacity, float loadFactor)

构造一个具有指定的初始容量和负载因子的 HashMap。

 

在这里插入图片描述

HashMap(Map<? extends K, ? extends V> m)

包含另一个 “Map” 的构造函数

 

最后调用了 putMapEntries(),来看一下方法实现:

 

注意:

float ft = ((float)s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F ?

s/loadFactor 的结果是小数,加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数。所以 + 1.0F 是为了获取更大的容量。

例如:原来集合的元素个数是 6 个,那么 6/0.75 是8,是 2 的n次幂,那么新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了,这样会导致在存储元素的时候,容量不够,还得继续扩容,那么性能降低了,而如果 +1 呢,数组长度直接变为16了,这样可以减少数组的扩容。

2.3 put方法

put方法的实现文字说明:

  1. 先通过 hash 值计算出 key 映射到哪个桶;
  2. 如果桶上没有碰撞冲突,则直接插入;
  3. 如果出现碰撞冲突了,则需要处理冲突:
    • a 如果该桶使用红黑树处理冲突,则调用红黑树的方法插入数据;
    • b 否则采用传统的链式方法插入。如果链的长度达到临界值,则把链转变为红黑树;
  4. 如果桶中存在重复的键,则为该键替换新值 value;
  5. 如果 size 大于阈值 threshold,则进行扩容;

图解过程:https://www.processon.com/view/link/654b42c1a0f05033c951e305

在这里插入图片描述

put方法的源码说明

 

上面的源码中使用到了hash方法,我们来看下hash方法的源码

 

从上面可以得知 HashMap 是支持 key 为空的,而 HashTable 是直接用 Key 来获取hashCode 所以 key 为空会抛异常。

(n - 1) & hash 的实现介绍:

  • key.hashCode();返回散列值也就是 hashcode,假设随便生成的一个值。
  • n 表示数组初始化的长度是 16。
  • &(按位与运算):运算规则:相同的二进制数位上,都是 1 的时候,结果为 1,否则为0。
  • ^(按位异或运算):运算规则:相同的二进制数位上,数字相同,结果为 0,不同为 1。

在这里插入图片描述

2.4 treeifyBin()方法

  结点添加完成之后判断此时结点个数是否大于 TREEIFY_THRESHOLD 临界值 8,如果大于则将链表转换为红黑树,转换红黑树的方法 treeifyBin,整体代码如下:

 

treeifyBin 方法如下所示

 

小结:

  1. 根据哈希表中元素个数确定是扩容还是树形化。
  2. 如果是树形化遍历桶中的元素,创建相同个数的树形结点,复制内容,建立起联系。
  3. 然后让桶中的第一个元素指向新创建的树根结点,替换桶的链表内容为树形化内容。

2.5 扩容方法

扩容机制:

什么时候才需要扩容

  当 HashMap 中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时,就会进行数组扩容,loadFactor 的默认值是 0.75。

HashMap 的扩容是什么

  进行扩容,会伴随着一次重新 hash 分配,并且会遍历 hash 表中所有的元素,是非常耗时的。在编写程序中,要尽量避免 resize。HashMap 在进行扩容时,使用的 rehash 方式非常巧妙,因为每次扩容都是翻倍,与原来计算的 (n - 1) & hash 的结果相比,只是多了一个 bit 位,所以结点要么就在原来的位置,要么就被分配到 “原位置 + 旧容量” 这个位置。

例如我们从 16 扩展为 32 时,具体的变化如下所示:

在这里插入图片描述

因此元素在重新计算 hash 之后,因为 n 变为 2 倍,那么 n - 1 的标记范围在高位多 1bit(红色),因此新的 index 就会发生这样的变化。

在这里插入图片描述

说明:

  5 是假设计算出来的原来的索引。这样就验证了上述所描述的:扩容之后所以结点要么就在原来的位置,要么就被分配到 “原位置 + 旧容量” 这个位置。

  因此,我们在扩充 HashMap 的时候,不需要重新计算 hash,只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了,是 0 的话索引没变,是 1 的话索引变成 “原位置 + 旧容量” 。可以看看下图为 16 扩充为 32 的 resize 示意图:

在这里插入图片描述

  正是因为这样巧妙的 rehash 方式,既省去了重新计算 hash 值的时间,而且同时,由于新增的 1bit 是 0 还是 1 可以认为是随机的,在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数,保证了 rehash 之后不会出现更严重的 hash 冲突,均匀的把之前的冲突的结点分散到新的桶中了。

resize源码分析

 

2.6 remove方法

  删除方法就是首先先找到元素的位置,如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除,树小于 6 的时候要转链表。

 

removeNode() 方法:

 

2.7 get方法

  查找方法,通过元素的 key 找到 value,这个方法就比较好理解了

 

get 方法主要调用的是 getNode 方法,代码如下:

 

三、IO基础核心

IO:1. 磁盘IO 2.网络IO

1.Java IO

  Java IO(Input/Output)是Java编程语言中用于处理输入和输出的一组类和接口。它提供了一种在Java程序中读取和写入数据的方法。

Java IO包括两个主要的部分:

  • 字节流:以字节为单位进行操作,字节流适用于处理二进制数据.
  • 字符流。以字符为单位进行操作,而字符流适用于处理文本数据。

  Java IO的核心类是InputStream和OutputStream,它们分别用于从输入源读取数据和向输出目标写入数据。另外,Reader和Writer类是用于读取和写入文本数据的字符流的基类。

在这里插入图片描述

2. IO模型讲解

https://www.processon.com/view/link/64a8d8d01906bf

3.select、poll和epoll讲解

https://www.processon.com/view/link/654cba3a2a499a6f61dac0c2

在这里插入图片描述

https://www.processon.com/view/link/654cba44833cbe82bb

在这里插入图片描述

https://www.processon.com/view/link/654cba4d7aad1de

在这里插入图片描述

四、Java线程核心

1.进程和线程

进程:进程的本质是一个正在执行的程序,程序运行时系统会创建一个进程,并且给每个进程分配独立的内存地址空间保证每个进程地址不会相互干扰。同时,在 CPU 对进程做时间片的切换时,保证进程切换过程中仍然要从进程切换之前运行的位置出开始执行。所以进程通常还会包括程序计数器、堆栈指针。

线程:有时被称为轻量级进程(Lightweight Process,LWP),是程序执行流的最小单元。线程是程序中一个单一的顺序控制流程。进程内一个相对独立的、可调度的执行单元,是系统独立调度和分派 CPU 的基本单位指运行中的程序的调度单位。在单个程序中同时运行多个线程完成不同的工作,称为多线程。

2.线程的创建方式

创建的方式有三种:

  1. 继承Thread
  2. 实现Runnable接口
  3. Callable/Future
 

3.线程的生命周期

  • 新建状态(New):线程对象被创建后,但还没有调用start()方法时的状态。
  • 就绪状态(Runnable):线程对象调用start()方法后进入就绪状态,表示线程可以被调度执行。
  • 运行状态(Running):线程被调度执行后进入运行状态。
  • 等待状态(WAITING): 线程需要等待其他线程做出一些特定动作(通知或中断)
  • 阻塞状态(Blocked):线程在执行过程中可能因为某些原因被阻塞,例如等待输入输出、线程休眠等。
  • 结束状态(Terminated):线程执行完任务后进入结束状态。

https://www.processon.com/view/link/654f18e06a2ff722ead4cd2c

在这里插入图片描述

4.线程的启动和终止

4.1 启动线程

  启动线程是start方法,非run方法

4.2 线程的终止

使用退出标志退出线程

一般 run()方法执行完,线程就会正常结束,然而,常常有些线程是伺服线程。它们需要长时间的运行,只有在外部某些条件满足的情况下,才能关闭这些线程。使用一个变量来控制循环

例如:最直接的方法就是设一个boolean 类型的标志,并通过设置这个标志为 true或 false 来控制 while循环是否退出。定义了一个退出标志 exit,当 exit 为 true 时,while 循环退出,exit 的默认值为 false.在定义 exit时,使用了一个 Java 关键字 volatile,这个关键字的目的是使 exit 同步,也就是说在同一时刻只能由一个线程来修改 exit 的值。

 

Interrupt方法结束线

线程处于阻塞状态:如使用了 sleep,同步锁的 wait,socket 中的 receiver,accept 等方法时,会使线程处于阻塞状态。当调用线程的 interrupt()方法时,会抛出 InterruptException 异常。阻塞中的那个方法抛出这个异常,通过代码捕获该异常,然后 break 跳出循环状态,从而让我们有机会结束这个线程的执行。通常很多人认为只要调用 interrupt 方法线程就会结束,实际上是错的, 一定要先捕获 InterruptedException 异常之后通过 break 来跳出循环,才能正常结束 run 方法。

 
 

线程未处于阻塞状态:使用 isInterrupted()判断线程的中断标志来退出循环。当使用interrupt()方法时,中断标志就会置 true,和使用自定义的标志来控制循环是一样的道理。

stop 方法终止线程

程序中可以直接使用 thread.stop()来强行终止线程,但是 stop 方法是很危险的,就象突然关闭计算机电源,而不是按正常程序关机一样,可能会产生不可预料的结果,不安全主要是:thread.stop()调用之后,创建子线程的线程就会抛出 ThreadDeatherror 的错误,并且会释放子线程所持有的所有锁。一般任何进行加锁的代码块,都是为了保护数据的一致性,如果在调用thread.stop()后导致了该线程所持有的所有锁的突然释放(不可控制),那么被保护数据就有可能呈现不一致性,其他线程在使用这些被破坏的数据时,有可能导致一些很奇怪的应用程序错误。因此,并不推荐使用 stop 方法来终止线程。

5.线程间通信

  1. wait()和notify()方法:wait()方法使线程进入等待状态,直到其他线程调用notify()或notifyAll()方法将其唤醒。notify()方法唤醒一个等待中的线程,notifyAll()方法唤醒所有等待中的线程。
  • wait(long timeout)和notify()方法:wait(long timeout)方法使线程进入等待状态,直到其他线程调用notify()方法将其唤醒,或者等待时间超过指定的timeout时间。notify()方法唤醒一个等待中的线程。
  • join()方法:join()方法使一个线程等待另一个线程执行完毕。当一个线程调用另一个线程的join()方法时,当前线程将被阻塞,直到另一个线程执行完毕。
  • Lock和Condition接口:Lock接口提供了比synchronized关键字更灵活的锁机制,Condition接口提供了更灵活的等待/通知机制。通过Lock接口的lock()方法获取锁,unlock()方法释放锁;通过Condition接口的await()方法使线程等待,signal()方法唤醒一个等待中的线程,signalAll()方法唤醒所有等待中的线程。
  • BlockingQueue阻塞队列:BlockingQueue是一个支持阻塞操作的队列,当队列为空时,获取元素的线程将被阻塞,直到队列中有可用元素;当队列满时,插入元素的线程将被阻塞,直到队列有空闲位置。

6.线程池

6.1 线程池原理

提交一个任务到线程池中,线程池的处理流程如下:

  1. 判断线程池里的核心线程是否都在执行任务,如果不是(核心线程空闲或者还有核心线程没有被创建)则创建一个新的工作线程来执行任务。如果核心线程都在执行任务,则进入下个流程。
  2. 线程池判断工作队列是否已满,如果工作队列没有满,则将新提交的任务存储在这个工作队列里。如果工作队列满了,则进入下个流程
  3. 判断线程池里的线程是否都处于工作状态,如果没有,则创建一个新的工作线程来执行任务。如果已经满了,则交给饱和策略来处理这个任务。

线程池的好处:

  • 降低资源消耗:通过重复利用已创建的线程降低线程的创建和销毁造成的不必要资源消耗
  • 提高响应速度:当任务到达时,任务可以不需要等到线程创建就立即开始执行
  • 提高线程的可管理性:统一分配、监控、调优

6.2 常见的线程池实现

线程池说明newCachedThreadPool创建一个可根据需要创建新线程的线程池,但是在以前构造的线程可用时将重用它们。对于执行
很多短期异步任务的程序而言,这些线程池通常可提高程序性能。调用 execute 将重用以前构造
的线程(如果线程可用)。如果现有线程没有可用的,则创建一个新线程并添加到池中。终止并
从缓存中移除那些已有 60 秒钟未被使用的线程。因此,长时间保持空闲的线程池不会使用任何资
源。newFixedThreadPool创建一个可重用固定线程数的线程池,以共享的无界队列方式来运行这些线程。在任意点,在大
多数 nThreads 线程会处于处理任务的活动状态。如果在所有线程处于活动状态时提交附加任务,
则在有可用线程之前,附加任务将在队列中等待。如果在关闭前的执行期间由于失败而导致任何
线程终止,那么一个新线程将代替它执行后续的任务(如果需要)。在某个线程被显式地关闭之
前,池中的线程将一直存在。newScheduledThreadPool创建一个线程池,它可安排在给定延迟后运行命令或者定期地执行。newSingleThreadExecutorExecutors.newSingleThreadExecutor()返回一个线程池(这个线程池只有一个线程),这个线程
池可以在线程死后(或发生异常时)重新启动一个线程来替代原来的线程继续执行下去!

6.3 ThreadPoolExecutor

  系统提供的线程池的实现都有各自的优缺点。我们在实际的使用中更多的是自定义线程池的实现

 

各个参数的含义:

corePoolSize:线程池核心线程数量
maximumPoolSize:线程池最大线程数量
keepAliverTime:当活跃线程数大于核心线程数时,空闲的多余线程最大存活时间
unit:存活时间的单位
workQueue:存放任务的队列
handler:超出线程范围和队列容量的任务的处理程序

使用的是阻塞队列:

  • ArrayBlockingQueue
  • LinkedBlockingQueue
  • SynchronousQueue
  • PriorityBlockingQueue

拒绝策略分类:

  • AbortPolicy:直接抛出异常,默认策略
  • CallerRunsPolicy:用调用者所在的线程来执行任务
  • DiscardOldestPolicy:丢弃阻塞对类中靠最前的任务,并执行当前任务
  • DiscardPolicy:直接丢弃任务

提交一个任务到线程池中,线程池的处理流程如下:

  1. 判断线程池里的核心线程是否都在执行任务,如果不是(核心线程空闲或者还有核心线程没有被创建)则创建一个新的工作线程来执行任务。如果核心线程都在执行任务,则进入下个流程。
  2. 线程池判断工作队列是否已满,如果工作队列没有满,则将新提交的任务存储在这个工作队列里。如果工作队列满了,则进入下个流程。
  3. 判断线程池里的线程是否达到最大线程数,如果没有,则创建一个新的工作线程来执行任务。如果已经满了,则交给饱和策略来处理这个任务。

在这里插入图片描述

6.4 线程池调优

要想合理地配置线程池,就必须首先分析任务特性,可以从以下几个角度来分析。

  • 任务的性质:CPU密集型任务、IO密集型任务和混合型任务
  • 任务的优先级:高中低
  • 任务的执行时间:长中短
  • 任务 的依赖性;是否依赖其他系统资源
  • CPU密集型任务应配置尽可能小的线程,如配置NCPU+1个线程的线程池,
  • IO密集型任务线程并不是一直在执行任务 ,则应配置尽可能多的线程,如2*NCPU 。

7.Synchronized

  同步、重量级锁,synchronized可以保证方法或者代码块在运行时,同一时刻只有一个方法可以进入临界区,同时还可以保证共享变量的内存可见性(单台JVM内)

synchronized锁对象:

  • 普通同步方法,锁的是当前实例对象
  • 静态同步方法,锁的是当前类的class对象
  • 同步代码块,锁的是括号里的对象(实例对象或者class对象)

synchronized的锁优化

  • 无锁
  • 偏向锁:为了在无多线程竞争的情况下尽量减少不必要的轻量级锁执行路径,主要尽可能避免不必须要的CAS操作,如果竞争锁失败,则升级为轻量级锁
  • 轻量级锁:自旋方式,该线程等待一段时间,不会被立即挂起,看持有锁的线程是否会很快释放锁(循环方式)
  • 重量级锁:阻塞方式
  • 锁消除: 有些代码明明不用加锁,结果还给加上锁,这时编译器会判断锁没有什么必要,就直接把锁去掉了
  • 锁粗化:将多个连续的加锁、解锁操作连接在一起,扩展成一个范围更大的锁。例如for循环内部获取锁

8.AQS

AbstractQueuedSynchronizer,同步器,实现JUC核心基础组件,解决了子类实现同步器时涉及到的大量细节性问题,例如:同步状态、FIFO同步队列等,采用模板方法模式,AQS实现了大量的通用方法,子类通过继承方式实现其抽象方法来管理同步状态

同步锁获取与释放:

  • 独占式
  • 共享式
 

在这里插入图片描述

https://www.processon.com/view/link/5f805d597d9c0806f26a1533

在这里插入图片描述

9.ThreadLocal

  一种解决多线程环境下成员变量的问题的方案,但是与线程同步无关,其思路就是为每个线程创建一个单独的变量副本。从而每个线程都可以独立的改变自己所拥有的变量副本,而不会影响其他线程对应的变量副本 , ThreadLocal不是用于解决共享变量的问题,也不是为了协调线程同步而存在,而是为了方便每个线程处理自己的状态而引入的一个机制

  ThreadLocal可以理解为线程本地变量,他会在每个线程都创建一个副本,那么在线程之间访问内部副本变量就行了,做到了线程之间互相隔离,相比于synchronized的做法是用空间来换时间。

  ThreadLocal有一个静态内部类ThreadLocalMap,ThreadLocalMap又包含了一个Entry数组,Entry本身是一个弱引用,他的key是指向ThreadLocal的弱引用,Entry具备了保存key value键值对的能力。

  弱引用的目的是为了防止内存泄露,如果是强引用那么ThreadLocal对象除非线程结束否则始终无法被回收,弱引用则会在下一次GC的时候被回收。

  但是这样还是会存在内存泄露的问题,假如key和ThreadLocal对象被回收之后,entry中就存在key为null,但是value有值的entry对象,但是永远没办法被访问到,同样除非线程结束运行。

  但是只要ThreadLocal使用恰当,在使用完之后调用remove方法删除Entry对象,实际上是不会出现这个问题的。

  • 上一篇: java基础api训练
  • 下一篇: java基础186
  • 版权声明


    相关文章:

  • java基础api训练2025-04-28 19:18:04
  • java基础实战练习2025-04-28 19:18:04
  • 毕向东java基础25天视频教程2025-04-28 19:18:04
  • java基础题库学院2025-04-28 19:18:04
  • 学完了Java基础2025-04-28 19:18:04
  • java基础1862025-04-28 19:18:04
  • java 基础入门2025-04-28 19:18:04
  • java基础模拟试题2025-04-28 19:18:04
  • java基础演讲素材2025-04-28 19:18:04
  • java基础英语发音2025-04-28 19:18:04