Wetts's blog

Stay Hungry, Stay Foolish.

0%

e.g.

这是 exampli gratia(“for example; for instance;such as”: 举例如) 的缩写。

例句1: Buy some vegetables, e.g., carrots.

使用中,不仅e后的“.”常常被漏掉(如写成eg.),而且也经常与下面的缩写混淆。

为了方便记忆,你可把 “e.g.” 与 “example given” 联想起来。

最好把 e.g. 连同它的例子放在括号中,如

例句2:I like quiet activities (e.g., reading)

etc.

这是 et cetera (“and so forth; and the others; and other things; and the rest; and so on”:等等) 的缩写。它放在列表的最后,表示前面的例子还没列举完,最后加个词“等等”。

例句3: I need to go to the store and buy some pie, milk, cheese, etc.

etc. 常常被误写为 ect.,这是因为很多英语的c在t前(c在t后的很少)。etc. 前面要有逗号。

不要在 e.g. 的列表最后用 etc( 在including后的列表后也不宜使用etc),这是因为 e.g. 表示泛泛的举几个例子,并没有囊括所有的实例,其中就已经包含“等等”,如果再加一个 etc. 就多余了,例如这是错的: Writing instructors focus on a number of complex skills that require extensive practice (e.g., organization, clear expression, logical thinking, etc.)

et al.

这是et alia(“and others; and co-workers”:等它人) 的缩写。它几乎都是在列文献作者时使用,即把主要作者列出后,其它作者全放在et al. 里面。

例句4: These results agree with the ones published by Pelon et al. (2002).

人的场合用 et al,而无生命的场合用 etc.(et cetera)。

et 后不要加“.”,因为 et 不是缩写。另外,与 etc. 不同,et al. 的前面不要逗号。

i.e.

这是id est(“that is” , “in other words”:也就是) 的缩写。目的是用来进一步解释前面所说的观点(不是像e.g.那样引入实例来形象化),意思是“那就是说,换句话说”。

例句5:In 2005, American had the lowest personal saving rate since 1933. In fact it was outright negavetive—i.e., consumers spent more money that they made.

例句6:There are three meals in the day (i.e., breakfast, lunch, and dinner)

使用中,i.e.的第一个”.”也常常被错误地漏掉了。它后面紧跟着一个逗号,再跟一个解释。

如同e.g., i.e.也最好放入括号中,如同例句6那样。

比较下面两个例句。

例句7:I like to eat boardwalk food, i.e., funnel cake and french fries.

例句8:I like to eat boardwalk food, e.g., funnel cake and french fries.

例句7表示只有 funnel cake and french fries这两样boardwalk食物,我喜欢。例句8表示我喜欢boardwalk食物,比如 funnel cake and french fries;其实snow cones and corn dogs等其他类型,我也喜欢。

为了方便记忆,你可把”i.e.” 与 “in essence” 联想起来。

viz.

这是 videlicet(“namely”, “towit”, “precisely”, “that is to say”:即) 的缩写,与 e.g. 不同,viz. 位于同位列表之前,要把它前面单词所包含的项目全部列出。

例句9:“Each symbol represents one of the four elements, viz. earth, air, fire, and water.”(每个符号代表如下四个元素之一,即: 地球,空气,火焰和水)。

例句10: The noble gases, viz. helium, neon, argon, xenon, krypton and radon, show a non-expected behaviour when exposed to this new element.

注意 viz.后面无逗号。

Introduction

知识图谱(Knowledge Graph),在图书情报界称为知识域可视化或知识领域映射地图,是显示知识发展进程与结构关系的一系列各种不同的图形,用可视化技术描述知识资源及其载体,挖掘、分析、构建、绘制和显示知识及它们之间的相互联系。

A KG is a multi-relational graph composed of entities (nodes) and relations (different types of edges). Each edge is represented as a triple of the form (head entity, relation, tail entity), also called a fact, indicating that two entities are connected by a specific relation, e.g., (AlfredHitchcock, DirectorOf, Psycho). Although effective in representing structured data, the underlying symbolic nature of such triples usually makes KGs hard to manipulate.

To tackle this issue, a new research direction known as knowledge graph embedding has been proposed and quickly gained massive attention.

Knowledge graph (KG) embedding is to embed components of a KG including entites and relations into continuous vector spaces, so as to simplify the manipulation while preserving the inherent structure of the KG. Those entity and relation embeddings can further be used to benefit all kinds of tasks, such as KG completion, relation extraction, entity classification, and entity resolution.

technique

A typical KG embedding technique generally consists of three steps:

  1. representing entities and relations,
  2. defining a scoring function, and
  3. learning entity and relation representations.

We roughly categorize such embedding techniques into two groups: translational distance models and semantic matching models. The former use distance-based scoring functions, and the latter similarity-based ones.

Translational Distance Models

Translational distance models exploit distance-based scoring functions. They measure the plausibility of a fact as the distance between the two entities, usually after a translation carried out by the relation.

TransE and Its Extensions

TransE

Despite its simplicity and efficiency, TransE has flaws in dealing with 1-to-N, N-to-1, and N-to-N relations.

To overcome the disadvantages of TransE in dealing with 1-to-N, N-to-1, and N-to-N relations, an effective strategy is to allow an entity to have distinct representations when involved in different relations.

TransH

TransH follows this general idea, by introducing relation-specific hyperplanes.

Knowledge Graph Embedding: A Survey of Approaches and Applications
Quan Wang , Zhendong Mao , Bin Wang, and Li Guo

转自:https://blog.csdn.net/qq_23947237/article/details/78265026

一个例子搞清楚(先验分布/后验分布/似然估计)

preface:

无论是《通信原理》、《信息论》、《信道编码》还是《概率与统计理论》,或者在现在流行的《模式识别》和《Machine Learning》中总会遇到这么几个概念:先验分布/后验分布/似然估计。

如果大家不熟悉这几个词,相信大家熟知贝叶斯公式,该公式涉及到了以上几个概念。但是学完本科课程,也会算题,就是在实际情境中总感觉理不清这几个概念的关系,最近上课老被老师讲的先验、后验搞得晕头转向。因此,如果您和我遇到类似的囧事,这篇文章很适合您。

声明:本文主要内容修改整理于知乎回答。

本文目标:

  • 一个隔壁小哥的故事
  • 故事中的因果和三个概念
  • 贝叶斯公式的角色
  • 最大似然估计和贝叶斯的关系

隔壁小哥的故事

隔壁小哥要去15公里外的一个公园,他可以选择步行走路,骑自行车或者开辆车,然后通过其中一种方式花了一段时间到达公园。

首先在这个事里边,大家不要关注隔壁小哥去干嘛,也许去送外卖吧:) 。言归正传,这件事中 __采用哪种交通方式是因,花了多长时间是果__。俗话说瓜熟蒂落,皆是因果;因果循环,报应不爽。要理解即将提到的概念,何为因何为果先要搞清楚。

三个概念之后验(知果求因)

隔壁小哥去公园的故事才刚刚开始,假设在这里您已经牢记住这个故事的因和果。故事仍然要接着讲,顺便带出我们的概念。

假设我们 __已经知道小哥花了1个小时到了公园__,那么你猜他是怎么去的(走路or坐车or自行车),事实上我们 __不能百分百确定他的交通方式__,我们正常人的思路是他 很大可能 是骑车过去的,当然也不排除开车过去却由于堵车严重花了很长时间,当然还有可能他是个赛跑的运动员自己一路飞跑过去的。

假设 __已经知道小哥花了3个小时才到公园__,这个时候我们猜的时候会觉得他 很大可能 是静静地走路过去的。但是假设已经 __知道小哥只花了20分钟才到公园__,那么正常人会觉得他 最大可能 是开车奔驰而去。

这种预先 __已知结果__(路上花的时间),然后根据结果 __估计(猜)原因__(交通方式)的概率分布即 __后验概率__。

例子问题公式化:P(交通方式∣花费的时间)

修改成一般的公式:P(因∣果)

公式正规化:P(θ∣x)

(公式中的 “∣|∣”读作 _given_,即给定的意思。如 P(A∣B) 即 A given B 的概率)

[解释]:看到这里估计大家很奇怪为什么要用 x、 θ 这样的字母表示,而不是熟悉的 x、 y。这样表示自然是有原因的。在这里大家只需要先暂时记住 θ 代表因、 x 代表果,后面的贝叶斯我们将会具体介绍这些字母的含义。

三个概念之先验概率(由历史求因)

换个情景,我们 不再考虑 隔壁小哥去公园的 结果 了。假设隔壁小哥还没去,大早上刚起床,打算吃完早饭再去。

假设我们比较了解小哥的个人习惯,别管怎么了解的:) 。小哥是个健身爱好者就喜欢跑步运动,这个时候我们可以猜测他更可能倾向于走路过去。

当然我的隔壁小哥是个大死肥宅,懒得要命!这个时候我们猜测他更可能倾向于坐车,连骑自行车的可能性都不大。

这个情景中隔壁小哥的交通工具选择与花费时间不再相关。因为我们是 在结果发生前 就开始猜的,根据历史规律确定 原因 (交通方式)的概率分布即 __先验概率__。

例子问题公式化:P(交通方式)

一般化:P(因)

正规化:P(θ)

三个概念之似然估计(由因求果)

换个情景,我们先重新考虑隔壁小哥去公园的交通方式。

假设隔壁小哥步行走路去,15公里的路到公园,一般情况下小哥大概要用2个多小时,当然很小的可能性是小哥是飞毛腿,跑步过去用了1个小时左右,极为小的可能是小哥是隐藏的高手,10分钟就轻功跑酷到了。

小哥决定开车,到公园半个小时是非常可能的,非常小的概率是小哥因为途径的路上有车祸堵了3个小时。

这种 __先定下来原因__,根据原因来 估计结果 的概率分布即 __似然估计__。根据原因来统计各种可能结果的概率即似然函数。

似然函数问题公式化:P(时间∣交通方式)

一般化:P(果∣因)

正规化:P(x∣θ)

贝叶斯公式

我们熟知的贝叶斯公式是这样的:贝叶斯公式原始

但在这里我们采用如下形式:贝叶斯公式变换

贝叶斯公式文字

[注]:P(x) 即 evidence。隔壁小哥去公园很多次,忽略交通方式是什么,只统计每次到达公园的时间 x,于是得到了一组时间的概率分布。这种不考虑原因,只看结果的概率分布即 evidence,它也称为样本发生的概率分布的证据。

evidence 在故事中如下表示:P(时间)P(果)

深入贝叶斯推断

在这里相信大多数人已经很好地理解了先验概率,后验概率,证据以及和似然估计的概念了。接下来我们将接着讲故事,隔壁小哥到公园以后去做一个游戏,游戏内容如下:

在小哥面前有两个一模一样的宝箱,一号箱子里面有3颗水果糖和1颗巧克力糖;二号箱子里面有2颗水果糖和2颗巧克力糖。

  1. 现在小哥将随机选择一个箱子,从中摸出一颗糖。请问小哥选择一号箱子的概率有多大?
  2. 现在小哥将随机选择一个箱子,从中摸出一颗糖发现是水果糖。请问这颗水果糖来自一号箱子的概率有多大?

球

暂且不去算这道题,在这个看似无聊的事情中,从哪个箱子去抓是 因;抓到的糖是什么糖为 结果。再去回顾我们之前的贝叶斯公式:贝叶斯公式变换

[解释]:其中 x 是观测得到的结果数据。P(x) 是观测结果数据的概率分布。如下表:

x 水果糖 巧克力糖
P(x) 5/8 3/8

[解释]:其中 θ 是决定观测结果数据分布的参数。P(θ) 是先验概率,没有观测数据的支持下 θ 发生的概率。如下表:

θ 一号箱 二号箱
P(θ) 1/2 1/2

[解释]:P(θ∣x) 是后验概率,有观测数据的支持下 θ 发生的概率。在上面的故事中第二问是小哥随机选择一个箱子,从中摸出一颗糖发现是水果糖。这颗水果糖来自一号箱子的概率就是后验概率:P(θ=一号箱∣x=水果糖)

[解释]:P(x∣θ) 是似然函数,给定某参数 θ 时结果数据的概率分布。

其中,P(θ=一号箱) 就是先验概率,根据贝叶斯公式,需求证据 P(x=水果糖) 和似然函数 _P(x=水果糖∣θ=一号箱)_。

题目1

我们再考虑上面的计算:

(1) 现在小哥将随机选择一个箱子,从中摸出一颗糖。请问小哥选择一号箱子的概率。根据明显的先验知识我们就可以知道
题目2

(2) 现在小哥将随机选择一个箱子,从中摸出一颗糖发现是水果糖。请问这颗水果糖来自一号箱子的概率。后验概率为
题目3

我们为什么要在这里连续计算两道题呢,并不是为了单纯的计算,而是去比较计算结果得到贝叶斯推断的意义。

大家可以看到:没有做实验之前我们推断 P(θ=一号箱)=1/2 这个先验概率;而有了参考结果数据“从中摸出一颗糖发现是水果糖“,我们便可以得到 P(θ=一号箱∣x=水果糖)=3/5 这个后验概率。也就是说推断是一号箱的概率,在取出水果糖前和后,【θ=一号箱】事件的可能性得到了增强(1/2<3/5)。

我们可以用小哥在公园的第二个奇遇来解释【贝叶斯估计】的意义:

小哥在公园里玩飞镖,附近有个陌生人说他是一个专业的飞镖玩家,假设你现在是小哥,你可能最开始会假设这家伙在开玩笑忽悠我吧。

首先你对这个人几乎什么都不了解,但遇到一个真正的专业飞镖玩家的概率是很小的。 因为澳大利亚的专业飞镖玩家也不过大约15个。

如果这个陌生人为了证明自己,开始扔飞镖并且第一次正中靶心,但这个数据可能还是不能令你非常信服,因为你觉得这可能只是运气。

但如果这个人连续十次都正中靶心,多个观测样本让你会倾向于接受他的专业说法。

在这件事当中,你对【陌生人是专业玩家】的先验置信度就被累积的实验数据所覆盖而增强变大,贝叶斯定理起作用了。

MAP/ML/贝叶斯估计

给定一些数据样本 x,假定我们知道样本是从某一种分布中随机取出的,但我们不知道这个分布具体的参数 θ。

最大似然估计(ML,Maximum Likelihood)可以估计模型的参数。其目标是找出一组参数 θ,使得模型产生出观测数据 x 的概率最大:最大似然估计1

假如这个参数有一个先验概率,那么参数该怎么估计呢?这就是MAP要考虑的问题。 最大后验估计(MAP-Maxaposterior)。MAP优化的是一个后验概率,即给定了观测值后使概率最大:最大后验概率1

前两种都是假设参数是个确定值,但贝叶斯估计假设参数是个随机数。

贝叶斯估计,假定把待估计的参数看成是符合某种先验概率分布的随机变量,而不是确定数值。在样本分布上,计算参数所有可能的情况,并通过计算参数的期望,得到后验概率密度。

支持向量机(support vector machines, SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;支持向量机还包括核技巧,这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划(convex quadratic programming)的问题,也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机学习方法包含构建由简至繁的模型:线性可分支持向量机(linear support vector machine in linearly separable case)、线性支持向量机(linear support vector machine)及非线性支持向量机(non-linear support vector machine)。当训练数据线性可分时,通过硬间隔最大化(hard margin maximization),学习一个线性的分类器,即线性可分支持向量机,又称为硬间隔支持向量机;当训练数据近似线性可分时,通过软间隔最大化(soft margin maximization),也学习一个线性的分类器,即线性支持向量机,又称为软间隔支持向量机;当训练数据线性不可分时,通过使用核技巧(kernel trick)及软间隔足底阿花,学习非线性支持向量机。

当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时,核函数(kernel funciton)表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机,等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法成为核技巧。核方法(kernel method)是比支持向量机更为一般的机器学习方法。

线性可分支持向量机与硬间隔最大化

线性可分支持向量机

学习的目标是在特征空间中找到一个分离超平面,能将实例分到不同的类。分离超平面对应于方程 wx+b=0,它由法向量 w 和 截距 b 决定,可用 (w, b) 来表示。分离超平面将特征空间划分为两部分,一部分是正类,一部分是负类。法向量指向的一侧为正类,另一侧为负类。

一般地,当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小策略,求得分离超平面,不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面,这时,解是唯一的。

线性可分支持向量机

函数间隔和几何间隔

函数间隔

函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时,只有函数间隔还不够。因为只要成比例地改变 w 和 b,例如将它们改为 2w 和 2b,超平面并没有改变,但函数间隔却成为原来的 2 倍。

可以对分离超平面的法向量 w 加某些约束,如规范化,||w||=1,使得间隔是确定的。这时函数间隔成为几何间隔(geometric margin)。

几何间隔

函数间隔和几何间隔有下面的关系:
函数间隔和几何间隔关系

间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言,线性可分分离超平面有无穷多个(等价于感知机),但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化(与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应)。

间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说,不仅将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

最大间隔分离超平面

最大间隔最优化问题1

考虑几何间隔和函数间隔的关系式,可将这个问题改写为:
最大间隔最优化问题2

最大间隔最优化问题3

这是一个凸二次规划(convex quadratic programming)问题。

凸优化问题

最大间隔法

最大间隔分离超平面的存在唯一性

最大间隔分离超平面的存在唯一性

支持向量与间隔边界

在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(support vector)。支持向量是使约束条件式(7.14)等号成立的点。

支持向量

在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用。如果移动支持向量将改变所求的解;但是如果在间隔边界以外移动其他实例点,甚至去掉这些点,则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用,所以将这种分类模型称为支持向量机。支持向量的个数一般很少,所以支持向量机由很少的“重要的”训练样本确定。

学习的对偶算法

为了求解线性可分支持向量机的最优化问题,将它作为原始最优化问题,应用拉格朗日对偶性,通过求解对有问题(dual problem)得到原始问题(primal problem)的最优解,这就是线性可分支持向量机的对偶算法(dual algorithm)。这样做的优点,一是对偶问题往往更容易求解;二是自然引入核函数,进而推广到非线性分类问题。

拉格朗日1
拉格朗日2

对偶求解1
对偶求解2-1
对偶求解2-2
对偶问题的解
支持向量

线性支持向量机与软间隔最大化

线性支持向量机

假设训练数据集不是线性可分的,通常情况是,训练数据中有一些特异点(outlier),将这些特异点除去后,剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点不能满足函数间隔大于等于 1 的约束条件。为了解决这个问题,可以对每个样本点引进一个松弛变量 松弛变量,使函数间隔加上松弛变量大于等于 1.这样,约束条件变为 加入松弛变量后的约束条件

同时,对每个松弛变量 松弛变量,支付一个代价 松弛变量。表表函数由原来的 SVM目标函数 变成 加入松弛变量的目标函数

这里,C>0 称为惩罚参数,一般由应用问题决定,C 值大时对误分类的惩罚增大,C 值小时对误分类的惩罚减小。最小化目标函数包含两层含义:使 SVM目标函数 尽量小即间隔尽量大,同时使误分类点的个数尽量小,C 是调和两者的系数。

有了上面的思路,可以和训练数据集线性可分时一样来考虑训练数据集线性不可分时的线性支持向量机学习问题。相应于硬间隔最大化,它称为软间隔最大化。

线性不可分的线性支持向量机的学习问题变成如下凸二次规划(convex quadratic programming)问题(原始问题):
线性支持向量机原始问题

线性支持向量机

学习的对偶算法

线性支持向量机学习算法

支持向量

线性支持向量机支持向量

合页损失函数

经验风险

合页损失函数

非线性支持向量机与核函数

核技巧

非线性分类问题

用线性分类方法求解非线性分类问题分为两步:首先使用一个变换将原空间的数据映射到新空间;然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

核函数的定义

仿射函数即由 1 阶多项式构成的函数,一般形式为 f(x)=Ax+b,这里,A 是一个 m×k 矩阵,x 是一个 k 向量,b 是一个 m 向量,实际上反映了一种从 k 维到 m 维的空间映射关系。设 f 是一个矢性(值)函数,若它可以表示为 f(x1,x2,…,xn)=A1x1+A2x2+…+Anxn+b,其中 Ai 可以是标量,也可以是矩阵,则称f是仿射函数。其中的特例是,标性(值)函数 f(x)=ax+b,其中 a、x、b 都是标量。此时严格讲,只有 b=0 时,仿射函数才可以叫“线性函数”(“正比例”关系)。

在约束最优化问题中,常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题,通常解对偶问题而得到原始问题的解。该方法应用在许多统计学习方法中,例如,最大熵模型与支持向量机。

原始问题

原始问题

原始问题2

原始问题3

原始问题4

对偶问题

对偶问题

原始问题和对偶问题的关系

原始问题与对偶问题最优值

原始问题与对偶问题推论1

原始问题与对偶问题定理2

原始问题与对偶问题定理3-1

原始问题与对偶问题定理3-2

转自:https://www.cnblogs.com/wlzy/p/8007045.html

前提及说明

第一次遇见矩阵求导,大多数人都是一头雾水,而搜了维基百科看也还是云里雾里,一堆的名词和一堆的表格到底都是什么呢?这里总结了我个人的学习经验,并且通过一个例子可以让你感受如何进行矩阵求导,下次再遇到需要进行矩阵求导的地方就不会措手不及。

在进行概念的解说之前,首先大家需要先知道下面的这个前提:

前提: 若 x 为向量,则默认 x 为列向量, xT 为行向量

布局的概念

布局简单地理解就是分子 y 、分母 x 是行向量还是列向量。

  • 分子布局(Numerator-layout):分子为 y 或者分母为 xT (即,分子为列向量或者分母为行向量)
  • 分母布局(Denominator-layout):分子为 yT 或者分母为 x (即,分子为行向量或者分母为列向量)

为了更加深刻地理解两种布局的特点和区别,下面是从维基百科中布局部分拿来的例子

分子布局

  • 标量/向量:分子布局-标量d向量(分母的向量为行向量)
  • 向量/标量:分子布局-向量d标量(分子的向量为列向量)
  • 向量/向量:分子布局-向量d向量(分子为列向量横向平铺,分母为行向量纵向平铺)
  • 标量/矩阵:分子布局-标量d矩阵(注意这个矩阵部分是转置的,而下面的分母布局是非转置的)
  • 矩阵/标量:分子布局-矩阵d标量

分母布局

  • 标量/向量:分母布局-标量d向量(分母的向量为列向量)
  • 向量/标量:分母布局-向量d标量(分子的向量为行向量)
  • 向量/向量:分母布局-向量d向量(分子为行向量纵向平铺,分母为列向量横向平铺)
  • 标量/矩阵:分母布局-标量d矩阵(矩阵部分为原始矩阵)

一个求导的例子

问题

问题

说明: y、w为列向量,X为矩阵

式子演化

看到这个例子不要急着去查表求导,先看看它的形式,是 式子演化 的形式,这种形式一般求导较为复杂,因此为了简化运算,我们先把式子展开成下面的样子(注意:式子演化2 : )

式子演化3

然后就可以写成四个部分求导的形式如下(累加后求导=求导后累加):

式子演化4

求导

  • 求导1

说明:分子部分为标量,分母部分为向量,找到维基百科中的Scalar-by-vector identities表格,在表格中匹配形式到第1行的位置,因为分母为列向量,因此为分母布局,对应的求导结果就是 0 。

  • 求导2

说明:同样的,在维基百科中的Scalar-by-vector identities表格,在表格中匹配形式到第11行的位置。

  • 求导3

说明:因为分子为标量,标量的转置等于本身,所以对分子进行转置操作,其等价于第二部分。

  • 求导4

说明:同样的,在维基百科中的Scalar-by-vector identities表格,在表格中匹配形式到第13行的位置。

整合

把四个部分求导结果进行相应的加减就可以得到最终的结果:

  • 整合

  • 分子布局,即按照 y 和xT (相比较于x)的布局。(求导结果中分子保持原始形式,分母为转置形式)

  • 分母布局, 即按照 yT 和 x (相比较于y)。(求导结果中分子为转置形式,分母保持原始形式)

  • 表格1

  • 表格2

  • 表格3

  • 表格4

  • 表格5

  • 表格6

  • 表格7

  • 表格8

  • 表格9

  • 表格10

  • 表格11


附录:公式推导

公式一

对任意行向量 $\mathbf{w} = (w_1, w_2, \cdots w_n)$ 都有
$$
\left.\frac{\partial(\mathbf{w} \mathbf{x})}{\partial \mathbf{x}}=\left[\begin{array}{c}{\frac{\partial(\mathbf{w} \mathbf{x})}{x_{1}}} \ {\frac{\partial(\mathbf{w} \mathbf{x})}{x_{2}}} \ {\vdots} \ {\frac{\partial(\mathbf{w} \mathbf{x})}{x_{n}}}\end{array}\right]=\left[\begin{array}{c}{\frac{\partial\left(w_1 x_1+w_2 x_{2}+\cdots+w_{n} x_{n}\right)}{x_{1}}} \ {\frac{\partial\left(w_{1} x_{1}+w_{2} x_{2}+\cdots+w_{n} x_{n}\right)}{x_{2}}} \ {\vdots} \ {\frac{\partial\left(w_1 x_1+w_2 x_{2}+\cdots+w_{n} x_{n}\right)}{x_{n}}}\end{array}\right]=\left[\begin{array}{c}{w_{1}} \ {w_{2}} \ {\vdots} \ {w_{n}}\end{array}\right]=\mathbf{w}^{T}\right.
$$
同时注意,如果 $\mathbf{w}$ 表示一个列向量,则
$$
\frac{\partial\left(\mathbf{x}^{\mathrm{T}} \mathbf{w}\right)}{\partial \mathbf{x}}=\mathbf{w}
$$

公式二

$\mathbf{A}$ 表示一个矩阵,其中 $\mathbf{a_1, a_2, \cdots a_n}$ 表示行向量
$$
\mathbf{A}=\left(\mathbf{a}{\mathbf{1}}, \mathbf{a}{2}, \cdots, \mathbf{a}{\mathbf{n}}\right)^{T}
$$
都有
$$
\frac{\partial(\mathbf{A} \mathbf{x})}{\partial \mathbf{x}}=\frac{\partial\left(\mathbf{a}
{1} \mathbf{x}, \mathbf{a}{2} \mathbf{x}, \cdots, \mathbf{a}{\mathbf{n}} \mathbf{x}\right)^{T}}{\partial \mathbf{x}}=\left(\mathbf{a}{1}^{T}, \mathbf{a}{2}^{T}, \cdots, \mathbf{a}{\mathbf{n}}^{T}\right)=\mathbf{A}^{T}
$$
$\mathbf{B}$ 表示一个矩阵,其中 $\mathbf{b_1, b_2, \cdots b_n}$ 表示列向量
$$
\mathbf{B}=\left(\mathbf{b}
{\mathbf{1}}, \mathbf{b}{2}, \cdots, \mathbf{b}{\mathbf{n}}\right)
$$
都有
$$
\frac{\partial\left(\mathbf{x}^{\mathrm{T}} \mathbf{B}\right)}{\partial \mathbf{x}}=\frac{\partial\left(\mathbf{x}^{\mathrm{T}} \mathbf{b}{1}, \mathbf{x}^{\mathrm{T}} \mathbf{b}{2}, \cdots, \mathbf{x}^{\mathrm{T}} \mathbf{b}{\mathbf{n}}\right)}{\partial \mathbf{x}}=\left(\mathbf{b}{1}, \mathbf{b}{2}, \cdots, \mathbf{b}{\mathbf{n}}\right)=\mathbf{B}
$$

公式三

$$
\frac{\partial\left(\mathbf{x}^{\mathrm{T}} \mathbf{x}\right)}{\partial \mathbf{x}}=\left[\begin{array}{c}{\frac{\partial \mathbf{x}^{\mathrm{T}} \mathbf{x}}{x_{1}}} \ {\frac{\partial \mathbf{x}^{\mathrm{T}} \mathbf{x}}{x_2}} \ {\vdots} \ {\frac{\partial \mathbf{x}^{\mathrm{T}} \mathbf{x}}{x_{n}}}\end{array}\right]=\left[\begin{array}{c}{\frac{\partial\left(x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}\right)}{x_{1}}} \ {\frac{\partial\left(x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}\right)}{x_{2}}} \ {\vdots} \ {\frac{\partial\left(x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}\right)}{x_{n}}}\end{array}\right]=\left[\begin{array}{c}{2 x_{1}} \ {2 x_{2}} \ {\vdots} \ {2 x_{n}}\end{array}\right]=2 \mathbf{x}
$$

JVM

JDK

  • JDK1.8
    • Lambda 表达式
    • 函数式接口
    • 法引用和构造器调用
    • Stream API
    • 接口中的默认方法和静态方法
    • 新时间日期 API

编译

  • 前端编译:源代码到字节码
    • 把 Java 源码文件(.java)编译成 Class 文件(.class)的过程。
    • JDK 的安装目录里有一个 javac 工具,就是它将 Java 代码翻译成字节码,这个工具我们叫做编译器。相对于后面要讲的其他编译器,其因为处于编译的前期,因此又被成为前端编译器。
    • 编译器的处理过程:
      1. 词法、语法分析
        • 在这个阶段,JVM 会对源代码的字符进行一次扫描,最终生成一个抽象的语法树。简单地说,在这个阶段 JVM 会搞懂我们的代码到底想要干嘛。就像我们分析一个句子一样,我们会对句子划分主谓宾,弄清楚这个句子要表达的意思一样。
      2. 填充符号表
        • 我们知道类之间是会互相引用的,但在编译阶段,我们无法确定其具体的地址,所以我们会使用一个符号来替代。在这个阶段做的就是类似的事情,即对抽象的类或接口进行符号填充。等到类加载阶段,JVM 会将符号替换成具体的内存地址。
      3. 注解处理
        • 我们知道 Java 是支持注解的,因此在这个阶段会对注解进行分析,根据注解的作用将其还原成具体的指令集。
      4. 分析与字节码生成
        • 到了这个阶段,JVM 便会根据上面几个阶段分析出来的结果,进行字节码的生成,最终输出为 class 文件。
    • 常见的前端编译器有 Sun 的 javac,Eclipse JDT 的增量式编译器(ECJ)。
  • 后端编译/即时(JIT)编译:字节码到机器码
    • 在运行时把 Class 文件字节码编译成本地机器码的过程。
    • 当源代码转化为字节码之后,其实要运行程序,有两种选择。一种是使用 Java 解释器解释执行字节码,另一种则是使用 JIT 编译器将字节码转化为本地机器代码。前者启动速度快但运行速度慢,而后者启动速度慢但运行速度快
    • 解释器不需要像 JIT 编译器一样,将所有字节码都转化为机器码,自然就少去了优化的时间。而当 JIT 编译器完成第一次编译后,其会将字节码对应的机器码保存下来,下次可以直接使用。而我们知道,机器码的运行效率肯定是高于 Java 解释器的。所以在实际情况中,为了运行速度以及效率,我们通常采用两者相结合的方式进行 Java 代码的编译执行。
    • 通过 java -version 可以看到 JVM 都是 mixed mode(混合模式,也就是解释器和编译器混合使用)。
    • 现在主流的商用虚拟机(如 Sun HotSpot、IBM J9)中几乎都同时包含解释器和编译器(三大商用虚拟机之一的 JRockit 是个例外,它内部没有解释器,因此会有启动相应时间长之类的缺点,但它主要是面向服务端的应用,这类应用一般不会重点关注启动时间)。
    • 与前端编译相比,二者各有优势
      • 当程序需要迅速启动和执行时,解释器可以首先发挥作用,省去编译的时间,立即执行;当程序运行后,随着时间的推移,编译器逐渐会返回作用,把越来越多的代码编译成本地代码后,可以获取更高的执行效率。解释执行可以节约内存,而编译执行可以提升效率。
      • 两种情况,编译器都是以整个方法作为编译对象,这种编译也是虚拟机中标准的编译方式。
    • 要知道一段代码或方法是不是热点代码,是不是需要触发即时编译,需要进行 Hot Spot Detection(热点探测)。目前主要的热点判定方式有以下两种:
      • 基于采样的热点探测
        • 采用这种方法的虚拟机会周期性地检查各个线程的栈顶,如果发现某些方法经常出现在栈顶,那这段方法代码就是“热点代码”。这种探测方法的好处是实现简单高效,还可以很容易地获取方法调用关系,缺点是很难精确地确认一个方法的热度,容易因为受到线程阻塞或别的外界因素的影响而扰乱热点探测。
      • 基于计数器的热点探测
        • 采用这种方法的虚拟机会为每个方法,甚至是代码块建立计数器,统计方法的执行次数,如果执行次数超过一定的阀值,就认为它是“热点方法”。这种统计方法实现复杂一些,需要为每个方法建立并维护计数器,而且不能直接获取到方法的调用关系,但是它的统计结果相对更加精确严谨。
        • 两个计数器
          • 方法调用计数器
            • 方法调用计数器用来统计方法调用的次数,在默认设置下,方法调用计数器统计的并不是方法被调用的绝对次数,而是一个相对的执行频率,即一段时间内方法被调用的次数。
          • 回边计数器
            • 回边计数器用于统计一个方法中循环体代码执行的次数(准确地说,应该是回边的次数,因为并非所有的循环都是回边),在字节码中遇到控制流向后跳转的指令就称为“回边”。
        • 在确定虚拟机运行参数的前提下,这两个计数器都有一个确定的阀值,当计数器的值超过了阀值,就会触发JIT编译。触发了 JIT 编译后,在默认设置下,执行引擎并不会同步等待编译请求完成,而是继续进入解释器按照解释方式执行字节码,直到提交的请求被编译器编译完成为止(编译工作在后台线程中进行)。当编译工作完成后,下一次调用该方法或代码时,就会使用已编译的版本。
    • JIT 工作流程
      • Java_JVM_JIT编译流程
    • JIT 编译器在运行程序时有两种编译模式可以选择,并且其会在运行时决定使用哪一种以达到最优性能。这两种编译模式的命名源自于命令行参数(eg: -client 或者 -server)。JVM Server 模式与 client 模式启动,最主要的差别在于:-server 模式启动时,速度较慢,但是一旦运行起来后,性能将会有很大的提升。原因是:当虚拟机运行在 -client 模式的时候,使用的是一个代号为 C1 的轻量级编译器,而 -server 模式启动的虚拟机采用相对重量级代号为 C2 的编译器。C2 比 C1 编译器编译的相对彻底,服务起来之后,性能更高。
      • RednaxelaFX 大佬
        • JIT 编译
          • 全称 just-in-time compilation,按照其原始的、严格的定义,是每当一部分代码准备要第一次执行的时候,将这部分代码编译,然后跳进编译好的代码里执行。这样,所有执行过的代码都必然会被编译过。早期的 JIT 编译系统对同一个块代码只会编译一次。
          • JIT 编译的单元也可以选择是方法/函数级别,或者别的,例如 trace。
        • 严格说 JIT 编译与自适应编译相比:
          • 前者的编译时机比后者早:第一次执行之前 vs 已经被执行过若干次
          • 前者编译的代码比后者多:所有执行过的代码 vs 一部分代码
        • JIT 编译与自适应编译都属于“动态编译”(dynamic compilation),或者叫“运行时编译”的范畴。特点是在程序运行的时候进行编译,而不是在程序开始运行之前就完成了编译;后者也叫做“静态编译”(static compilation)或者 AOT 编译(ahead-of-time compilation)。
        • 现在“JIT 编译”这个名词已经被泛化为等价于“动态编译”,所以包含了严格的 JIT 编译和自适应编译。就这个角度说,HotSpot VM 仍然在使用“JIT 编译”;里面的 Client Compiler(C1)和 Server Compiler(C2)也常被称为“JIT 编译器“。要注意,这样的说法已经不是指严格意义上的“JIT”了。
    • 以下是具有代表性的 HotSpot 虚拟机的即时编译器在生成代码时采用的代码优化技术:
      • 公共子表达式消除(语言无关的经典优化技术之一)
        • 如果一个表达式 E 已经计算过了,并且从先前的计算到现在 E 中所有变量的值都没有发生变化,那么 E 的这次出现就成为了公共子表达式。对于这种表达式,没必要花时间再对它进行计算,只需要直接使用前面计算过的表达式结果代替 E 就可以了。
        • 例子
          • int d = (c*b) * 12 + a + (a+ b * c) -> int d = E * 12 + a + (a+ E)
      • 数组范围检查消除(语言相关的经典优化技术之一)
        • 在 Java 语言中访问数组元素的时候系统将会自动进行上下界的范围检查,超出边界会抛出异常。对于虚拟机的执行子系统来说,每次数组元素的读写都带有一次隐含的条件判定操作,对于拥有大量数组访问的程序代码,这无疑是一种性能负担。Java 在编译期根据数据流分析可以判定范围进而消除上下界检查,节省多次的条件判断操作。
      • 方法内联(最重要的优化技术之一)
        • 简单的理解为把目标方法的代码“复制”到发起调用的方法中,消除一些无用的代码。只是实际的 JVM 中的内联过程很复杂,在此不分析。
      • 逃逸分析(最前沿的优化技术之一)
        • 逃逸分析的基本行为就是分析对象动态作用域:当一个对象在方法中被定义后,它可能被外部方法所引用,例如作为调用参数传递到其他方法中,称为方法逃逸。甚至可能被外部线程访问到,譬如赋值给类变量或可以在其他线程中访问的实例变量,称为线程逃逸
        • 对象的逃逸状态
          • 全局逃逸(GlobalEscape)
            • 即一个对象的作用范围逃出了当前方法或者当前线程,有以下几种场景:
              • 对象是一个静态变量
              • 对象是一个已经发生逃逸的对象
              • 对象作为当前方法的返回值
          • 参数逃逸(ArgEscape)
            • 即一个对象被作为方法参数传递或者被参数引用,但在调用过程中不会发生全局逃逸,这个状态是通过被调方法的字节码确定的。
          • 没有逃逸
            • 即方法中的对象没有发生逃逸。
        • 如果能证明一个对象不会逃逸到方法或线程之外,也就是别的方法或线程无法通过任何途径访问到这个对象,则可以为这个变量进行一些高效的优化:
          • 栈上分配
            • 将不会逃逸的局部对象分配到栈上,那对象就会随着方法的结束而自动销毁,减少垃圾收集系统的压力。
          • 同步消除
            • 如果该变量不会发生线程逃逸,也就是无法被其他线程访问,那么对这个变量的读写就不存在竞争,可以将同步措施消除掉(同步是需要付出代价的)
          • 标量替换
            • 标量是指无法在分解的数据类型,比如原始数据类型以及 reference 类型。而聚合量就是可继续分解的,比如 Java 中的对象。标量替换如果一个对象不会被外部访问,并且对象可以被拆散的话,真正执行时可能不创建这个对象,而是直接创建它的若干个被这个方法使用到的成员变量来代替。这种方式不仅可以让对象的成员变量在栈上分配和读写,还可以为后后续进一步的优化手段创建条件。
  • 静态提前编译(Ahead Of Time,AOT 编译):源代码到机器码
    • 优点是编译不占用运行时间,可以做一些较耗时的优化,并可加快程序启动。但因为 Java 语言的动态性(如反射)带来了额外的复杂性,影响了静态编译代码的质量。一般静态编译不如 JIT 编译的质量,这种方式用得比较少。
    • 目前 Java 体系中主要还是采用前端编译+JIT编译的方式,如 JDK 中的 HotSpot 虚拟机。

VM

  • HotSpot VM
    • 这个 JVM 最初由 Longview/Animorphic 实现,随着公司被 Sun/JavaSoft 收购而成为 Sun 的 JVM,并于 JDK 1.3.0 开始成为 Sun 的 Java SE 的主要 JVM。在 Sun 被 Oracle 收购后,现在 HotSpot VM 是 Oracle 的 Java SE 的主要 JVM。
    • HotSpot VM 得名于它得混合模式执行引擎:这个执行引擎包括解释器和自适应编译器(adaptive compiler)。
    • 执行流程
      • 默认配置下,一开始所有 Java 方法都由解释器执行。解释器记录着每个方法得调用次数和循环次数,并以这两个数值为指标去判断一个方法的“热度”。显然,HotSpot VM 是以“方法”为单位来寻找热点代码。
      • 等到一个方法足够“热”的时候,HotSpot VM 就会启动对该方法的编译。这种在所有执行过的代码里只寻找一部分来编译的做法,就叫做自适应编译(adaptive compilation)。
  • JRockit VM
    • 这个 JVM 使用纯编译的执行引擎,没有解释器。
    • 它有多层编译:第一次执行某个方法之前会用非常低的优化级别去 JIT 编译,然后等到某个方法足够热之后再用较高的优化级别重新编译它。
    • 这种系统既是严格意义上的 JIT 编译(第一次执行某个方法前编译它),又是自适应编译(找出热点再进行编译)。
  • IBM J9

双亲委派模型

  • 工作机制:当类加载器接收到类加载的请求时,它不会自己去尝试加载这个类,而是把这个请求委派给父加载器去完成,只有当父类加载器反馈自己无法完成这个加载请求时,子加载器才会尝试自己去加载类。
  • 加载流程:
    1. 当类加载器接收到类加载的请求时,首先检查该类是否已经被当前类加载器加载;
    2. 若该类未被加载过,当前类加载器会将加载请求委托给父类加载器去完成;
    3. 若当前类加载器的父类加载器(或父类的父类……向上递归)为 null,会委托启动类加载器完成加载;
    4. 若父类加载器无法完成类的加载,当前类加载器才会去尝试加载该类。
    • Java_双亲委托模型_类加载流程
  • 类加载器分类:
    • 启动类加载器 Bootstrap ClassLoader
      • 是所有类加载器的”老祖宗”,是由 C++ 实现的,不继承于 java.lang.ClassLoader 类。 它在虚拟机启动时会由虚拟机的一段 C++ 代码进行加载,所以它没有父类加载器,在加载完成后,它会负责去加载扩展类加载器和应用类加载器。
      • 用于加载 Java 的核心类——位于 <JAVA_HOME>\lib 中,或者被 -Xbootclasspath 参数所指定的路径中,并且是虚拟机能够识别的类库(仅按照文件名识别,如 rt.jar、tools.jar,名字不符合的类库即使放在 lib 目录中也不会被加载)。
    • 拓展类加载器 Extension ClassLoader
      • 拓展类加载器继承于 java.lang.ClassLoader 类,它的父类加载器是启动类加载器,而启动类加载器在 Java 中的显示就是 null。
      • 拓展类加载器负责加载 <JAVA_HOME>\lib\ext 目录中的,或者被 java.ext.dirs 系统变量所指定的路 径的所有类。
      • 需要注意的是扩展类加载器仅支持加载被打包为 .jar 格式的字节码文件。
    • 应用类/系统类加载器 App/System ClassLoader
      • 应用类加载器继承于 java.lang.ClassLoader 类,它的父类加载器是扩展类加载器。
      • 应用类加载器负责加载用户类路径 classpath 上所指定的类库。
      • 如果应用程序中没有自定义的类加载器,一般情况下应用类加载器就是程序中默认的类加载器。
    • 自定义类加载器 Custom ClassLoader
      • 自定义类加载器继承于 java.lang.ClassLoader 类,它的父类加载器是应用类加载器。
      • 这是自定义的类加载器,可加载指定路径的字节码文件。
      • 自定义类加载器需要继承 java.lang.ClassLoader 类并重写 findClass 方法(下文有说明为什么不重写 loadClass 方法)用于实现自定义的加载类逻辑。
  • 双亲委派模型的好处:
    • 基于双亲委派模型规定的这种带有优先级的层次性关系,虚拟机运行程序时就能够避免类的重复加载。
    • 双亲委派模型能够避免核心类篡改。一般我们描述的核心类是 rt.jar、tools.jar 这些由启动类加载器加载的类,这些类库在日常开发中被广泛运用,如果被篡改,后果将不堪设想。
  • 双亲委派模型的不足:
    • 由于历史原因(ClassLoader 类在 JDK1.0 时就已经存在,而双亲委派模型是在 JDK1.2 之后才引入的),在未引入双亲委派模型时,用户自定义的类加载器需要继承 java.lang.ClassLoader 类并重写 loadClass() 方法,因为虚拟机在加载类时会调用 ClassLoader#loadClassInternal(String) 方法。而这个方法会调用自定义类加载重写的 loadClass() 方法。而在引入双亲委派模型后,ClassLoader#loadClass 方法实际就是双亲委派模型的实现,如果重写了此方法,相当于打破了双亲委派模型。为了让用户自定义的类加载器也遵从双亲委派模型, JDK 新增了 findClass 方法,用于实现自定义的类加载逻辑。
    • 由于双亲委派模型规定的层次性关系,导致子类类加载器加载的类能访问父类类加载器加载的类,而父类类加载器加载的类无法访问子类类加载器加载的类。为了让上层类加载器加载的类能够访问下层类加载器加载的类,或者说让父类类加载器委托子类类加载器完成加载请求,JDK 引入了线程上下文类加载器,藉由它来打破双亲委派模型的屏障。
      • 线程上下文类加载器
        • 线程上下文类加载器是定义在 Thread 类中的一个 ClassLoader 类型的私有成员变量,它指向了当前线程的类加载器。这个类加载器可以通过 java.lang.Thread 类的 setContextClassLoaser() 方法进行设置,如果创建线程时还未设置,它将会从父线程中继承一个,如果在应用程序的全局范围内都没有设置过的话,那这个类加载器默认就是应用程序类加载器。
        • 父 ClassLoader 可以使用当前线程 Thread.currentThread().getContextClassLoader() 所指定的 classloader 加载的类。
    • 当用户需要程序的动态性,比如代码热替换、模块热部署等时,双亲委派模型就不再适用,类加载器会发展为更为复杂的网状结构。
  • SPI(Service Provider Interface)
    • 它允许服务商编写具体的代码逻辑来完成该接口的功能。
    • 但是 Java 提供的 SPI 接口是在核心类库中,由启动类加载器加载的,厂商实现的具体逻辑代码是在 classpath 中,是由应用类加载器加载的,而启动类加载器加载的类无法访问应用类加载器加载的类,也就是说启动类加载器无法找到 SPI 实现类,单单依靠双亲委派模型就无法实现 SPI 的功能了,所以线程上下文类加载器应运而生。
  • 相关问题
    • Class.forName 和 classloader 的区别?
      • Class.forName() 执行初始化过程执行静态代码化。
        • 内部实际调用的方法是 Class.forName(className, true, classloader);
      • ClassLoader.loadClass 不执行初始化过程。
        • 内部实际调用的方法是 ClassLoader.loadClass(className, false);

类、对象内存相关

  • 类加载
    • 加载时机
      1. 遇到 new、getstatic、putstatic、invokestatic 这四条字节码指令的时候。
      2. 使用 java.lang.reflect 进行反射调用的时候。
      3. 当初始化一个类的时候,发现其父类还没有初始化,那么先去初始化它的父类。
      4. 当虚拟机启动的时候,需要初始化 main 函数所在的类。
    • 加载流程
      1. 编译:.java 文件编译后生成 .class 字节码文件
      2. 加载:获取类的二进制字节流,将其静态存储结构转化为方法区的运行时数据结构
      3. 连接:细分三步
        1. 校验:文件格式验证,元数据验证,字节码验证,符号引用验证
        2. 准备:在方法区中对类的 static 变量分配内存并设置类变量数据类型默认的初始值,不包括实例变量,实例变量将会在对象实例化的时候随着对象一起分配在 Java 堆中
        3. 解析:将常量池内的符号引用替换为直接引用的过程
      4. 连接初始化:为类的静态变量赋予正确的初始值(Java 代码中被显式地赋予的值)
  • 对象创建
    • 创建过程
      • Java_JVM_创建对象的过程
      1. 首先进行类加载的检查
        • 虚拟机遇到 new 指令的时候,首先去检查该指令的参数是否能够在常量池中定位到这个类的符号引用,并且检查该符号引用代表的类是否已经被加载过、解析和初始化过。若没有,必须先执行相应的类加载的过程。
      2. 分配内存
        • 类加载检查通过之后,虚拟机为对象分配内存。(内存大小在类加载完后就能确定)。分配的方式有“指针碰撞”和“空闲列表”两种,若 Java 堆是规整的,采用“指针碰撞”;反之采用空闲列表。
      3. 初始化零值
        • 内存分配完之后,虚拟机将分配到的内存空间初始化为零值。保证了对象的实例字段在 Java 代码中可以不赋初值就直接使用。
      4. 设置对象头
        • 始化零值之后,虚拟机要对对象进行必要的设置:对象头的设置。
      5. 执行 init 方法
        • 最后,虚拟机的视角来看,新的对象已经产生了。但是从 Java 程序的视角来看,init 方法还没有执行,所有字段还都是零。一般来说,执行 new 指令之后就会接着执行 init 方法,把对象按照程序员的意愿进行初始化。真正可用的对象就完全产生了。
    • 对象初始化方法执行流程
      1. 父类的静态成员赋值和静态块
      2. 子类的静态成员和静态块
      3. 父类的构造方法
      4. 父类的成员赋值和初始化块
      5. 父类的构造方法中的其它语句
      6. 子类的成员赋值和初始化块
      7. 子类的构造方法中的其它语句
    • 内存分配
      • Java_JVM_创建对象内存分配流程
      • 栈上分配(JIT 性能优化之一)
        • 如果确定一个对象的作用域不会逃逸出方法之外,那可以将这个对象分配在栈上,这样,对象所占用的内存空间就可以随栈帧出栈而销毁。在一般应用中,不会逃逸的局部对象所占的比例很大,如果能使用栈上分配,那大量的对象就会随着方法的结束而自动销毁了,无须通过垃圾收集器回收,可以减小垃圾收集器的负载。
        • 技术基础:
          • 逃逸分析
            • 逃逸分析的目的是判断对象的作用域是否有可能逃逸出函数体。
          • 标量替换
            • 允许将对象打散分配在栈上,比如若一个对象拥有两个字段,会将这两个字段视作局部变量进行分配。
        • 设置方法
          • 只能在 server 模式下才能启用逃逸分析,参数 -XX:DoEscapeAnalysis 启用逃逸分析,参数 -XX:+EliminateAllocations 开启标量替换(默认打开)。Java SE 6u23 版本之后,HotSpot 中默认就开启了逃逸分析,可以通过选项 -XX:+PrintEscapeAnalysis 查看逃逸分析的筛选结果。
      • 堆上分配
        • 选择那种分配方式由 Java 堆是否规整决定,而 Java 堆是否规整又由所采用的垃圾收集器是否带有压缩整理功能决定。
        • 分配方式有“指针碰撞”和“空闲列表”两种
          • Java_JVM_创建对象内存分配方式
          • 指针碰撞
            • Java_JVM_创建对象内存分配方式_指针碰撞
          • 空闲列表
            • Java_JVM_创建对象内存分配方式_空闲列表
        • 并发问题
          • 单线程下,“指针碰撞”和“空闲列表”分配内存不会有线程安全问题,实际开发过程中,创建对象是很频繁的事情,而且是多线程环境,作为虚拟机来说,必须要保证线程是安全的。
          • 通常来讲,虚拟机采用两种方式来保证线程安全:
            • CAS + 失败重试
              • CAS 是乐观锁的一种实现方式。所谓乐观锁就是,每次不加锁而是设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止。虚拟机采用 CAS 配上失败重试的方式保证更新操作的原子性。
            • TLAB
              • 为每一个线程预先在 Eden 区分配一块儿内存,JVM 在给线程中的对象分配内存时,首先在 TLAB 分配,当对象大于 TLAB 中的剩余内存或 TLAB 的内存已用尽时,再采用上述的 CAS 进行内存分配。
              • TLAB 的全称是 Thread Local Allocation Buffer,即线程本地分配缓存区,这是一个线程专用的内存分配区域。相当于线程的私有对象。
              • 特点
                • 堆是 JVM 中所有线程共享的,因此在其上进行对象内存的分配均需要进行加锁,这也导致了 new 对象的开销是比较大的
                • Sun Hotspot JVM 为了提升对象内存分配的效率,对于所创建的线程都会分配一块独立的空间 TLAB(Thread Local Allocation Buffer),其大小由 JVM 根据运行的情况计算而得,在 TLAB 上分配对象时不需要加锁,因此 JVM 在给线程的对象分配内存时会尽量的在 TLAB 上分配,在这种情况下 JVM 中分配对象内存的性能和 C 基本是一样高效的,但如果对象过大的话则仍然是直接使用堆空间分配
                • TLAB 仅作用于新生代的 Eden Space,因此在编写 Java 程序时,通常多个小的对象比大的对象分配起来更加高效
              • 设置方法
                • 如果设置了虚拟机参数 -XX:UseTLAB,在线程初始化时,同时也会申请一块指定大小的内存,只给当前线程使用,这样每个线程都单独拥有一个空间,如果需要分配内存,就在自己的空间上分配,这样就不存在竞争的情况,可以大大提升分配效率。
                • TLAB 空间的内存非常小,缺省情况下仅占有整个 Eden 空间的 1%,也可以通过选项 -XX:TLABWasteTargetPercent 设置 TLAB 空间所占用 Eden 空间的百分比大小。
              • 原理
                • TLAB 的本质其实是三个指针管理的区域:start、top 和 end,每个线程都会从 Eden 分配一块空间,例如说 100KB,作为自己的 TLAB,其中 start 和 end 是占位用的,标识出 eden 里被这个 TLAB 所管理的区域,卡住 eden 里的一块空间不让其它线程来这里分配。
                • 当一个 TLAB 用满(分配指针 top 撞上分配极限 end 了),就新申请一个 TLAB,而在老 TLAB 里的对象还留在原地什么都不用管——它们无法感知自己是否是曾经从 TLAB 分配出来的,而只关心自己是在 eden 里分配的。
              • TLAB 只是让每个线程有私有的分配指针,但底下存对象的内存空间还是给所有线程访问的,只是其它线程无法在这个区域分配而已。从这一点看,它被翻译为线程私有分配区更为合理一点。
              • 分配流程
                • JAVA_JVM_TLAB分配流程图
                1. 从线程当前 TLAB 分配
                  • 如果启用了 TLAB(默认是启用的, 可以通过 -XX:-UseTLAB 关闭),则首先从线程当前 TLAB 分配内存,如果分配成功则返回,否则根据当前 TLAB 剩余空间与当前最大浪费空间限制大小进行不同的分配策略。
                2. 重新申请 TLAB 分配
                  • 如果当前 TLAB 剩余空间大于当前最大浪费空间限制(这个初始值为 期望大小/TLABRefillWasteFraction),直接在堆上分配。否则,重新申请一个 TLAB 分配。
                    • 为什么需要最大浪费空间呢?
                      • 当重新分配一个 TLAB 的时候,原有的 TLAB 可能还有空间剩余。原有的 TLAB 被退回堆之前,需要填充好 dummy object。由于 TLAB 仅线程内知道哪些被分配了,在 GC 扫描发生时返回 Eden 区,如果不填充的话,外部并不知道哪一部分被使用哪一部分没有,需要做额外的检查,如果填充已经确认会被回收的对象,也就是 dummy object,GC 会直接标记之后跳过这块内存,增加扫描效率。反正这块内存已经属于 TLAB,其他线程在下次扫描结束前是无法使用的。这个 dummy object 就是 int 数组。为了一定能有填充 dummy object 的空间,一般 TLAB 大小都会预留一个 dummy object 的 header 的空间,也是一个 int[] 的 header,所以 TLAB 的大小不能超过 int 数组的最大大小,否则无法用 dummy object 填满未使用的空间。
                      • 但是,填充 dummy 也造成了空间的浪费,这种浪费不能太多,所以通过最大浪费空间限制来限制这种浪费。
                      • 新的 TLAB 大小,取如下两个值中较小的那个:
                        • 当前堆剩余给 TLAB 可分配的空间,大部分 GC 的实现其实就是对应的 Eden 区剩余大小
                        • TLAB 期望大小 + 当前需要分配的空间大小
                3. 直接从堆上分配
                  • 直接从堆上分配是最慢的分配方式。一种情况就是,如果当前 TLAB 剩余空间大于当前最大浪费空间限制,直接在堆上分配。并且,还会增加当前最大浪费空间限制,每次有这样的分配就会增加 TLABWasteIncrement 的大小,这样在一定次数的直接堆上分配之后,当前最大浪费空间限制一直增大会导致当前 TLAB 剩余空间小于当前最大浪费空间限制,从而申请新的 TLAB 进行分配。
  • 对象的访问
    • Java 程序通过栈上的 reference(引用)数据来操作堆上的具体对象。
    • 主流的访问方式
      • 使用句柄
        • 如果使用句柄的话,那么 Java 堆中将会划分出一块内存来作为句柄池,reference 中存储的就是对象的句柄地址,而句柄中包含了对象实例数据与类型数据各自的具体地址信息
        • Java_JVM_对象访问_使用句柄
        • 使用句柄来访问的最大好处是 reference 中存储的是稳定的句柄地址,在对象被移动时只会改变句柄中的实例数据指针,而 reference 本身不需要修改。
      • 直接指针
        • 如果使用直接指针访问,那么 Java 堆对象的布局中就必须考虑如何放置访问类型数据的相关信息,而 reference 中存储的直接就是对象的地址
        • Java_JVM_对象访问_直接指针
        • 使用直接指针访问方式最大的好处就是速度快,它节省了一次指针定位的时间开销。
  • 对象在内存中分为三块区域
    • Java_JVM_对象在内存中的布局
    • 对象头
      • Mark Word(标记字段):默认存储对象的 HashCode,分代年龄和锁标志位信息。它会根据对象的状态复用自己的存储空间,也就是说在运行期间 Mark Word 里存储的数据会随着锁标志位的变化而变化。
        • Java_Mark_Word
        • 64 bit
      • Klass Point(类型指针):对象指向它的类元数据的指针,虚拟机通过这个指针来确定这个对象是哪个类的实例。
        • 64 bit
    • 实例数据
      • 这部分主要是存放类的数据信息,父类的信息。
    • 对其填充
      • 由于虚拟机要求对象起始地址必须是8字节的整数倍,填充数据不是必须存在的,仅仅是为了字节对齐。
        • Tip:不知道大家有没有被问过一个空对象占多少个字节?就是8个字节,是因为对齐填充的关系哈,不到8个字节对其填充会帮我们自动补齐。

内存模型

  • 内存分区
    • 方法区(Method Area)
      • 《深入理解Java虚拟机》书中对方法区(Method Area)存储内容描述如下:
        • 它用于存储已被虚拟机加载的类型信息、常量、静态变量、即时编译器编译后的代码缓存等。
      • 方法区结构
        • 类型信息
          • 对每个加载的类型(类 class、接口 interface、枚举 enum、注解 annotation),JVM 必须在方法区中存储以下类型信息:
            1. 这个类型的完整有效名称(全名=包名.类名)
            2. 这个类型直接父类的完整有效名(对于interface或是java.lang.Object,都没有父类)
            3. 这个类型的修饰符(public,abstract,final的某个子集)
            4. 这个类型直接接口的一个有序列表
        • 域(Field)信息
          • JVM必 须在方法区中保存类型的所有域的相关信息以及域的声明顺序。
          • 域的相关信息包括:
            • 域名称
            • 域类型
            • 域修饰符(public,private,protected,static,final,volatile,transient 的某个子集)
          • 域信息特殊情况
            • non-final 类型的类变量
              • 静态变量和类关联在一起,随着类的加载而加载,他们成为类数据在逻辑上的一部分
              • 类变量被类的所有实例共享,即使没有类实例时,你也可以访问它
            • 全局常量:static final
              • 全局常量就是使用 static final 进行修饰
              • 被声明为final的类变量的处理方法则不同,每个全局常量在编译的时候就会被分配了。
        • 方法(Method)信息
          • JVM必须保存所有方法的以下信息,同域信息一样包括声明顺序:
            • 方法名称
            • 方法的返回类型(包括 void 返回类型),void 在 Java 中对应的类为 void.class
            • 方法参数的数量和类型(按顺序)
            • 方法的修饰符(public,private,protected,static,final,synchronized,native,abstract 的一个子集)
            • 方法的字节码(bytecodes)、操作数栈、局部变量表及大小(abstract 和 native 方法除外)
            • 异常表(abstract和native 方法除外),异常表记录每个异常处理的开始位置、结束位置、代码处理在程序计数器中的偏移地址、被捕获的异常类的常量池索引
      • 常量池、运行时常量池
        • 常量池、运行时常量池
          • 方法区,内部包含了运行时常量池
          • 字节码文件,内部包含了常量池
          • 要弄清楚方法区,需要理解清楚 ClassFile,因为加载类的信息都在方法区。
          • 要弄清楚方法区的运行时常量池,需要理解清楚 ClassFile 中的常量池。
        • 常量池
          • 一个有效的字节码文件中除了包含类的版本信息、字段、方法以及接口等描述符信息外
          • 还包含一项信息就是常量池表(Constant Pool Table),包括各种字面量和对类型、域和方法的符号引用
          • 常量池中有啥
            • 数量值
            • 字符串值
            • 类引用
            • 字段引用
            • 方法引用
        • 运行时常量池
          • 运行时常量池(Runtime Constant Pool)是方法区的一部分。
          • 常量池表(Constant Pool Table)是 Class 字节码文件的一部分,用于存放编译期生成的各种字面量与符号引用,这部分内容将在类加载后存放到方法区的运行时常量池中。
          • 运行时常量池,在加载类和接口到虚拟机后,就会创建对应的运行时常量池。
          • JVM 为每个已加载的类型(类或接口)都维护一个常量池。池中的数据项像数组项一样,是通过索引访问的。
          • 运行时常量池中包含多种不同的常量,包括编译期就已经明确的数值字面量,也包括到运行期解析后才能够获得的方法或者字段引用。此时不再是常量池中的符号地址了,这里换为真实地址。
          • 运行时常量池,相对于 Class 文件常量池的另一重要特征是:具备动态性。
          • 运行时常量池类似于传统编程语言中的符号表(symbol table),但是它所包含的数据却比符号表要更加丰富一些。
          • 当创建类或接口的运行时常量池时,如果构造运行时常量池所需的内存空间超过了方法区所能提供的最大值,则 JVM 会抛 OutofMemoryError 异常。
      • 版本区别
        • 在 JDK1.7 及之前,HotSpot VM 的实现就是将其放在永久代中,这样的好处就是可以直接使用堆中的 GC 算法来进行管理,但坏处就是经常会出现内存溢出,即 PermGen Space 异常。
          • JDK1.6及以前
            • 有永久代(permanent generation),静态变量存储在永久代上
          • JDK1.7
            • 有永久代,但已经逐步“去永久代”,字符串常量池,静态变量移除,保存在堆中
        • 在 JDK1.8 中,HotSpot VM 取消了永久代,用元空间取而代之,元空间直接使用本地内存,理论上电脑有多少内存它就可以使用多少内存,所以不会再出现 PermGen Space 异常。引用类型的常量,只会在堆上(Java8)
        • JVM内存空间_1
        • JVM内存空间_2
        • JVM内存空间_3
    • 堆(Heap)
      • 几乎所有对象、数组等都是在此分配内存的,在 JVM 内存中占的比例也是极大的,也是 GC 垃圾回收的主要阵地
      • 可以处于物理上不连续但逻辑上连续的空间
      • 分区
        • 新生代
          • Eden
          • From Survivor、To Survivor
        • 老年代
        • 永久代【HotSpot VM 取消了永久代】
    • 虚拟机栈(Java Stack)
      • 当 JVM 在执行方法时,会在此区域中创建一个栈帧来存放方法的各种信息,比如返回值,局部变量表和各种对象引用等,方法开始执行前就先创建栈帧入栈,执行完后就出栈。【虚拟机栈描述的是 Java 方法执行的内存模型:每个方法被执行的时候都会同时创建一个栈帧(Stack Frame)用于存储局部变量表、操作栈、动态链接、方法出口等信息。每一个方法被调用直至执行完成的过程,就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。 】
      • 出现栈溢出的情况
        • 如果线程请求的栈深度大于虚拟机所允许的深度,将抛出 StackOverflowError 异常;
          • 根本原因是,某个线程所需的栈内存超过了JVM的限制,而此时物理内存仍有足够的可用空间。
        • 如果虚拟机栈可以动态扩展(当前大部分的 Java 虚拟机都可动态扩展,只不过 Java 虚拟机规范中也允许固定长度的虚拟机栈),当扩展时无法申请到足够的内存时会抛出 OutOfMemoryError 异常。
          • 根本原因是,(操作系统管理的)物理内存已没有足够的可用内存分配给JVM的栈使用。
    • 本地方法栈(Native Method Stack)
      • 和虚拟机栈类似,不过区别是专⻔提供给 Native 方法用的。
    • 程序计数器(Program Counter Register)
      • 占用很小的一片区域,我们知道 JVM 执行代码是一行一行执行字节码,所以需要一个计数器来记录当前执行的行数。
  • 内存泄漏
    • 当某些对象不再被应用程序所使用,但是由于仍然被引用而导致垃圾收集器不能释放他们。
    • 内存泄漏场景
      • 静态集合类
      • 各种连接,如数据库连接、网络连接和 IO 连接等。
      • 变量不合理的作用域。
      • 内部类持有外部类
        • 如果一个外部类的实例对象的方法返回了一个内部类的实例对象,这个内部类对象被长期引用了,即使那个外部类实例对象不再被使用,但由于内部类持有外部类的实例对象,这个外部类对象将不会被垃圾回收,这也会造成内存泄露。
      • 改变哈希值
        • 当一个对象被存储进 HashSet 集合中以后,就不能修改这个对象中的那些参与计算哈希值的字段了,否则,对象修改后的哈希值与最初存储进 HashSet 集合中时的哈希值就不同了,在这种情况下,即使在 contains 方法使用该对象的当前引用作为的参数去 HashSet 集合中检索对象,也将返回找不到对象的结果,这也会导致无法从 HashSet 集合中单独删除当前对象,造成内存泄露
      • 监听器的使用,在释放对象的同时没有相应删除监听器的时候也可能导致内存泄露。
    • 内存泄露解决的原则:
      • 尽量减少使用静态变量,类的静态变量的生命周期和类同步的。
      • 声明对象引用之前,明确内存对象的有效作用域,尽量减小对象的作用域,将类的成员变量改写为方法内的局部变量;
      • 减少长生命周期的对象持有短生命周期的引用;
      • 使用 StringBuilder 和 StringBuffer 进行字符串连接,String 和 StringBuilder 以及 StringBuffer 等都可以代表字符串,其中 String 字符串代表的是不可变的字符串,后两者表示可变的字符串。如果使用多个 String 对象进行字符串连接运算,在运行时可能产生大量临时字符串,这些字符串会保存在内存中从而导致程序性能下降。
      • 对于不需要使用的对象手动设置 null 值,不管 GC 何时会开始清理,我们都应及时的将无用的对象标记为可被清理的对象;
      • 各种连接(数据库连接,网络连接,IO 连接)操作,务必显示调用 close 关闭。

引用类型

  • 强引用
    • 被强引用关联的对象不会被回收。
    • 使用 new 一个新对象的方式来创建强引用。
  • 软引用
    • 被软引用关联的对象只有在内存不够的情况下才会被回收。
    • 使用 SoftReference 类来创建软引用。
  • 弱引用
    • 被弱引用关联的对象一定会被回收,也就是说它只能存活到下一次垃圾回收发生之前。
    • 使用 WeakReference 类来创建弱引用。
  • 虚引用
    • 又称为幽灵引用或者幻影引用,一个对象是否有虚引用的存在,不会对其生存时间造成影响,也无法通过虚引用得到一个对象。
    • 为一个对象设置虚引用的唯一目的是能在这个对象被回收时收到一个系统通知。
    • 使用 PhantomReference 来创建虚引用。

垃圾回收

  • 垃圾回收算法
    • 标记清除
      • 标记-清除算法将垃圾回收分为两个阶段:标记阶段和清除阶段。
      • 流程
        • 在标记阶段首先通过根节点(GC Roots),标记所有从根节点开始的对象,未被标记的对象就是未被引用的垃圾对象。然后,在清除阶段,清除所有未被标记的对象。
    • 复制算法
      • 流程
        • 从根集合节点进行扫描,标记出所有的存活对象,并将这些存活的对象复制到一块儿新的内存(图中下边的那一块儿内存)上去,之后将原来的那一块儿内存(图中上边的那一块儿内存)全部回收掉
    • 标记整理
      • 复制算法的高效性是建立在存活对象少、垃圾对象多的前提下的。
      • 这种情况在新生代经常发生,但是在老年代更常⻅的情况是大部分对象都是存活对象。如果依然使用复制算法,由于存活的对象较多,复制的成本也将很高
    • 分代收集算法
      • 分代收集算法就是目前虚拟机使用的回收算法。在不同年代使用不同的算法,从而使用最合适的算法,新生代存活率低,可以使用复制算法。而老年代对象存活率搞,没有额外空间对它进行分配担保,所以只能使用标记清除或者标记整理算法。
  • 判断一个对象是否可被回收
    • 引用计数算法
      • 为对象添加一个引用计数器,当对象增加一个引用时计数器加 1,引用失效时计数器减 1。引用计数为 0 的对象可被回收。
      • 在两个对象出现循环引用的情况下,此时引用计数器永远不为 0,导致无法对它们进行回收。正是因为循环引用的存在,因此 Java 虚拟机不使用引用计数算法。
    • 可达性分析算法
      • 通过 Roots 对象作为起点进行搜索,搜索走过的路径称为“引用链”,当一个对象到 Roots 没有任何的引用链相连时时,证明此对象不可用,当然被判定为不可达的对象不一定就会成为可回收对象。
        • GC ROOTS 可以的对象有
          • 虚拟机栈中的引用对象
          • 方法区的类变量的引用
          • 方法区中的常量引用
          • 本地方法栈中的对象引用
      • 被判定为不可达的对象要成为可回收对象必须至少经历两次标记过程,如果在这两次标记过程中仍然没 有逃脱成为可回收对象的可能性,则基本上就真的成为可回收对象了,能否被回收其实主要还是要看 finalize() 方法有没有与引用链上的对象关联,如果在 finalize() 方法中有关联则自救成功,改 对象不可被回收,反之如果没有关联则成功被二次标记成功,就可以称为要被回收的垃圾了。
    • 方法区的回收
      • 因为方法区主要存放永久代对象,而永久代对象的回收率比新生代低很多,所以在方法区上进行回收性价比不高。
      • 主要是对常量池的回收和对类的卸载。
      • 为了避免内存溢出,在大量使用反射和动态代理的场景都需要虚拟机具备类卸载功能。
      • 类的卸载条件很多,需要满足以下三个条件,并且满足了条件也不一定会被卸载:
        • 该类所有的实例都已经被回收,此时堆中不存在该类的任何实例。
        • 加载该类的 ClassLoader 已经被回收。
        • 该类对应的 Class 对象没有在任何地方被引用,也就无法在任何地方通过反射访问该类方法。
  • 垃圾回收器
    • JVM_垃圾回收器搭配
    • Serial
      • 复制算法,单线程,新生代
      • JVM_Serial
    • ParNew
      • 复制算法,多线程,新生代
      • JVM_ParNew
    • Parallel Scavenge
      • 多线程,复制算法,新生代,高吞吐量
    • Serial Old
      • 标记-整理算法,老年代
      • JVM_Serial_Old
    • Parallel Old
      • 标记-整理算法,老年代,注重吞吐量的场景下
      • JDK8 默认采用 Parallel Scavenge + Parallel Old 的组合
      • JVM_Parallel_Old
    • CMS
      • 是一种以获取最短回收停顿时间为目标的收集器
      • 基于“标记-清除”算法实现
      • JVM_CMS
      • 运作过程:
        • 初始标记
          • 需要“stop the world”
            • stop the world
              • Stop-The-World 机制简称 STW,是在执行垃圾收集算法时,Java 应用程序的其他所有线程都被挂起(除了垃圾收集帮助器之外)。
              • Java 中一种全局暂停现象,全局停顿,所有 Java 代码停止,native 代码可以执行,但不能与 JVM 交互;这些现象多半是由于 gc 引起。
          • 仅仅只是标记一下 GC Roots 能直接关联到的对象,速度很快
        • 并发标记
          • 进行 GC Roots Tracing
        • 重新标记
          • 需要“stop the world”
          • 是为了修正并发标记期间因用户程序继续运作而导致标记产生表动的那一部分对象的标记记录,这个阶段的停顿时间一般会比初始标记阶段稍⻓点,但远比并发标记的时间短
        • 并发清除
      • 优点
        • 并发收集、低停顿。
      • 缺点
        • CMS 收集器对 CPU 资源非常敏感。在并发阶段,它虽然不会导致用户线程停顿,但是会因为占用了一部分线程而导致应用程序变慢,总吞吐量会降低。
        • CMS 收集器无法处理浮动垃圾,可能会出现“Concurrent Mode Failure(并发模式故障)”失败而导致 Full GC 产生。
          • 浮动垃圾
            • 由于 CMS 并发清理阶段用户线程还在运行着,伴随着程序运行自然就会有新的垃圾不断产生,这部分垃圾出现的标记过程之后,CMS 无法在当次收集中处理掉它们,只好留待下一次 GC 中再清理。
        • 容易出现大量空间碎片。当空间碎片过多,将会给大对象分配带来很大的麻烦,往往会出现老年代还有很大空间剩余,但是无法找到足够大的连续空间来分配当前对象,不得不提前触发一次 Full GC。
    • G1
      • 从整体来看是基于“标记整理”算法实现的收集器; 从局部上来看是基于“复制”算法实现的。
      • JVM_G1收集器
      • JDK9 默认垃圾收集器 G1
      • G1 把堆划分成多个大小相等的独立区域(Region),新生代和老年代不再物理隔离。
        • 通过引入 Region 的概念,从而将原来的一整块内存空间划分成多个的小空间,使得每个小空间可以单独进行垃圾回收。这种划分方法带来了很大的灵活性,使得可预测的停顿时间模型成为可能。通过记录每个 Region 垃圾回收时间以及回收所获得的空间(这两个值是通过过去回收的经验获得),并维护一个优先列表,每次根据允许的收集时间,优先回收价值最大的 Region。
        • 每个 Region 都有一个 Remembered Set,用来记录该 Region 对象的引用对象所在的 Region。通过使用 Remembered Set,在做可达性分析的时候就可以避免全堆扫描。
        • 虽然 G1 可以不需要其他收集器配合就能独立管理整个 GC 堆,但是还是保留了分代的概念。它能够采用不同的方式去处理新创建的对象和已经存活了一段时间,熬过多次 GC 的旧对象以获取更好的收集效果。
      • 对象分配策略
        • TLAB(Thread Local Allocation Buffer)线程本地分配缓冲区
        • Eden 区中分配
        • Humongous 区分配
          • Humongous:如果一个对象占用的空间超过了分区容量 75% 以上,G1 收集器就认为这是一个巨型对象。
          • 这些巨型对象,默认直接会被分配在年老代,但是如果它是一个短期存在的巨型对象,就会对垃圾收集器造成负面影响。
          • 为了解决这个问题,G1 划分了一个 Humongous 区,它用来专门存放巨型对象。
          • 如果一个 H 区装不下一个巨型对象,那么 G1 会寻找连续的 H 分区来存储。为了能找到连续的H区,有时候不得不启动 Full GC。
      • 运作步骤:
        • 初始标记
        • 并发标记
        • 最终标记
        • 筛选回收
          • 用来统计每个 region 中的中被标记为存活的对象的数量,这个阶段如果发现完全没有活对象的 region 就会将其整体回收到可分配 region 列表中。
          • 把一部分 region 里活的对象拷贝到空的 region 里面,然后回收原本的 region 空间,此阶段可以选择任意多个 region 来构成收集集合(Collection Set),选定好收集集合之后,便可以将 Collection Set 中的对象并行拷贝到新的 region 中。
      • JVM_G1
      • 特点
        • G1 能充分利用 CPU、多核环境下的硬件优势,使用多个CPU(CPU 或者 CPU 核心)来缩短 stop-The-World 停顿时间。部分其他收集器原本需要停顿 Java 线程执行的 GC 动作,G1 收集器仍然可以通过并发的方式让 Java 程序继续执行。
      • 相关问题
        • G1 的个显著特点他能够让用户设置应用的暂停时间,为什么 G1 能做到这一点呢?
          • G1 回收的第 4 步,它是“选择一些内存块”,而不是整代内存来回收,这是 G1 跟其它 GC 非常不同的一点,其它 GC 每次回收都会回收整个 Generation 的内存(Eden, Old),而回收内存所需的时间就取决于内存的大小,以及实际垃圾的多少,所以垃圾回收时间是不可控的;而 G1 每次并不会回收整代内存,到底回收多少内存就看用户配置的暂停时间,配置的时间短就少回收点,配置的时间长就多回收点,伸缩自如。
  • 垃圾标记
    • 三色标记法
      • 颜色说明
        • 白色:尚未访问过。
        • 黑色:本对象已访问过,而且本对象 引用到 的其他对象 也全部访问过了。
        • 灰色:本对象已访问过,但是本对象 引用到 的其他对象 尚未全部访问完。全部访问后,会转换为黑色。
      • 流程
        • 停止线程标记
          • JVM_三色标记流程_1
          1. 初始时,所有对象都在【白色集合】中;
          2. 将GC Roots 直接引用到的对象挪到【灰色集合】中;
          3. 从灰色集合中获取对象:
            1. 将本对象引用到的其他对象全部挪到【灰色集合】中;
            2. 将本对象挪到【黑色集合】里面。
          4. 重复步骤3,直至【灰色集合】为空时结束。
          5. 结束后,仍在【白色集合】的对象即为GC Roots 不可达,可以进行回收。
        • 并发标记
          • 问题
            • 多标-浮动垃圾
              • JVM_三色标记_浮动垃圾
              • 此刻之后,对象E/F/G是“应该”被回收的。然而因为E已经变为灰色了,其仍会被当作存活对象继续遍历下去。最终的结果是:这部分对象仍会被标记为存活,即本轮GC不会回收这部分内存
              • 这部分本应该回收 但是 没有回收到的内存,被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性,只是需要等到下一轮垃圾回收中才被清除。
              • 另外,针对并发标记开始后的新对象,通常的做法是直接全部当成黑色,本轮不会进行清除。这部分对象期间可能会变为垃圾,这也算是浮动垃圾的一部分。
            • 漏标-读写屏障
              • JVM_三色标记_漏标
                1. 读取对象 E 的成员变量 fieldG 的引用值,即对象 G;
                2. 对象 E 往其成员变量 fieldG,写入 null 值。
                3. 对象 D 往其成员变量 fieldG,写入对象 G;
                • 我们只要在上面这三步中的任意一步中做一些“手脚”,将对象 G 记录起来,然后作为灰色对象再进行遍历即可。比如放到一个特定的集合,等初始的 GC Roots 遍历完(并发标记),该集合的对象遍历即可(重新标记)。
              • 此时切回GC线程继续跑,因为E已经没有对G的引用了,所以不会将G放到灰色集合;尽管因为D重新引用了G,但因为D已经是黑色了,不会再重新做遍历处理。
              • 最终导致的结果是:G会一直停留在白色集合中,最后被当作垃圾进行清除。这直接影响到了应用程序的正确性,是不可接受的。
              • 不难分析,漏标只有同时满足以下两个条件时才会发生:
                1. 灰色对象断开了白色对象的引用(直接或间接的引用);即灰色对象原来成员变量的引用发生了变化。
                2. 黑色对象重新引用了该白色对象;即黑色对象成员变量增加了新的引用。
              • 解决方法
                • 写屏障(Store Barrier)
                  • 写屏障 + SATB
                    • 这种做法的思路是:尝试保留开始时的对象图,即原始快照(Snapshot At The Beginning,SATB),当某个时刻的 GC Roots 确定后,当时的对象图就已经确定了。
                    • 比如当时 D 是引用着 G 的,那后续的标记也应该是按照这个时刻的对象图走(D 引用着 G)。如果期间发生变化,则可以记录起来,保证标记依然按照原本的视图来。
                    • SATB 破坏了条件一:【灰色对象 断开了 白色对象的引用】,从而保证了不会漏标。

                  • 写屏障 + 增量更新
                    • 这种做法的思路是:不要求保留原始快照,而是针对新增的引用,将其记录下来等待遍历,即增量更新(Incremental Update)。
                    • 增量更新破坏了条件二:【黑色对象 重新引用了 该白色对象】,从而保证了不会漏标。

                • 读屏障(Load Barrier)
                  • 当读取成员变量时,一律记录下来
            • Java HotSpot VM 中,其并发标记时对漏标的处理方案如下:
              • CMS:写屏障 + 增量更新
              • G1:写屏障 + SATB
              • ZGC:读屏障
  • GC 流程
    • JVM_GC流程
    • 内存分配策略
      • 对象优先在 Eden 分配
        • 大多数情况下,对象在新生代 Eden 上分配,当 Eden 空间不够时,发起 Minor GC。
      • 大对象直接进入老年代
        • 大对象是指需要连续内存空间的对象,最典型的大对象是那种很长的字符串以及数组。
        • 经常出现大对象会提前触发垃圾收集以获取足够的连续空间分配给大对象。
        • -XX:PretenureSizeThreshold,大于此值的对象直接在老年代分配,避免在 Eden 和 Survivor 之间的大量内存复制。
      • 长期存活的对象进入老年代
        • 为对象定义年龄计数器,对象在 Eden 出生并经过 Minor GC 依然存活,将移动到 Survivor 中,年龄就增加 1 岁,增加到一定年龄则移动到老年代中。
        • -XX:MaxTenuringThreshold 用来定义年龄的阈值。
      • 动态对象年龄判定
        • 虚拟机并不是永远要求对象的年龄必须达到 MaxTenuringThreshold 才能晋升老年代,如果在 Survivor 中相同年龄所有对象大小的总和大于 Survivor 空间的一半,则年龄大于或等于该年龄的对象可以直接进入老年代,无需等到 MaxTenuringThreshold 中要求的年龄。
      • 空间分配担保
        • 在发生 Minor GC 之前,虚拟机先检查老年代最大可用的连续空间是否大于新生代所有对象总空间,如果条件成立的话,那么 Minor GC 可以确认是安全的。
        • 如果不成立的话虚拟机会查看 HandlePromotionFailure 的值是否允许担保失败,如果允许那么就会继续检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小,如果大于,将尝试着进行一次 Minor GC;如果小于,或者 HandlePromotionFailure 的值不允许冒险,那么就要进行一次 Full GC。
    • 垃圾回收分类
      • Minor GC
        • 回收新生代,因为新生代对象存活时间很短,因此 Minor GC 会频繁执行,执行的速度一般也会比较快。
        • Minor GC 的触发条件
          • 当 Eden 空间满时,就将触发一次 Minor GC。
        • 正式 Minor GC 前的检查
          • 在正式 Minor GC 前,JVM 会先检查新生代中对象,是比老年代中剩余空间大还是小。
            • 为什么要做这样的检查呢?
              • 原因很简单,假如 Minor GC 之后 Survivor 区放不下剩余对象,这些对象就要进入到老年代,所以要提前检查老年代是不是够用。这样就有两种情况:
                1. 老年代剩余空间大于新生代中的对象大小,那就直接 Minor GC,GC 完 survivor 不够放,老年代也绝对够放
                2. 老年代剩余空间小于新生代中的对象大小,这个时候就要查看是否启用了「老年代空间分配担保规则」,具体来说就是看 -XX:-HandlePromotionFailure 参数是否设置了(一般都会设置)
                  • 老年代空间分配担保规则是这样的。如果老年代中剩余空间大小,大于历次 Minor GC 之后剩余对象的大小,那就允许进行 Minor GC。因为从概率上来说,以前的放的下,这次的也应该放的下。那就有两种情况:
                    1. 老年代中剩余空间大小,大于历次 Minor GC 之后剩余对象的大小,进行 Minor GC
                    2. 老年代中剩余空间大小,小于历次 Minor GC 之后剩余对象的大小,进行 Full GC,把老年代空出来再检查
        • Minor GC 后的处境
          • 前面说了,开启老年代空间分配担保规则只能说是大概率上来说,Minor GC 剩余后的对象够放到老年代,所以当然也会有万一,Minor GC 后会有这样三种情况:
            1. Minor GC 之后的对象足够放到 Survivor 区,皆大欢喜,GC 结束
            2. Minor GC 之后的对象不够放到 Survivor 区,接着进入到老年代,老年代能放下,那也可以,GC 结束
            3. Minor GC 之后的对象不够放到 Survivor 区,老年代也放不下,那就只能 Full GC
        • 实在不行只能 OOM
          • 前面都是成功 GC 的例子,还有 3 种情况,会导致 GC 失败,报 OOM:
          1. 紧接上一节 Full GC 之后,老年代任然放不下剩余对象,就只能 OOM
          2. 未开启老年代分配担保机制,且一次 Full GC 后,老年代任然放不下剩余对象,也只能 OOM
          3. 开启老年代分配担保机制,但是担保不通过,一次 Full GC 后,老年代任然放不下剩余对象,也是能 OOM
      • Full GC
        • 回收老年代和新生代,老年代对象其存活时间长,因此 Full GC 很少执行,执行速度会比 Minor GC 慢很多。
        • Full GC 的触发条件
          • 调用 System.gc()
            • 只是建议虚拟机执行 Full GC,但是虚拟机不一定真正去执行。不建议使用这种方式,而是让虚拟机管理内存。
          • 老年代空间不足
            • 老年代空间不足的常见场景为大对象直接进入老年代、长期存活的对象进入老年代等。
            • 为了避免以上原因引起的 Full GC,应当尽量不要创建过大的对象以及数组。除此之外,可以通过 -Xmn 虚拟机参数调大新生代的大小,让对象尽量在新生代被回收掉,不进入老年代。还可以通过 -XX:MaxTenuringThreshold 调大对象进入老年代的年龄,让对象在新生代多存活一段时间。
          • 空间分配担保失败
            • 使用复制算法的 Minor GC 需要老年代的内存空间作担保,如果担保失败会执行一次 Full GC。
          • JDK 1.7 及以前的永久代空间不足
            • 在 JDK 1.7 及以前,HotSpot 虚拟机中的方法区是用永久代实现的,永久代中存放的为一些 Class 的信息、常量、静态变量等数据。
            • 当系统中要加载的类、反射的类和调用的方法较多时,永久代可能会被占满,在未配置为采用 CMS GC 的情况下也会执行 Full GC。如果经过 Full GC 仍然回收不了,那么虚拟机会抛出 java.lang.OutOfMemoryError。
            • 为避免以上原因引起的 Full GC,可采用的方法为增大永久代空间或转为使用 CMS GC。
          • Concurrent Mode Failure
            • 执行 CMS GC 的过程中同时有对象要放入老年代,而此时老年代空间不足(可能是 GC 过程中浮动垃圾过多导致暂时性的空间不足),便会报 Concurrent Mode Failure 错误,并触发 Full GC。

相关问题

  • 为何 Java 代码越执行越快?
    • JIT 编译优化
    • TLAB 预热

Java

Basic Java

面向对象

  • 三大特性
    • 封装
      • 指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法。
    • 继承
      • 子类继承父类的特征和行为,使得子类对象(实例)具有父类的实例域和方法,或子类从父类继承方法,使得子类具有父类相同的行为。
      • 访问权限
        • public
        • protected
          • protected 用于修饰成员,表示在继承体系中成员对于子类可见,但是这个访问修饰符对于类没有意义。
        • default
          • 包级可见
        • private
      • 重写与重载
        • 重写(Override)
          • 存在于继承体系中,指子类实现了一个与父类在方法声明上完全相同的一个方法。
          • 三个限制(使用 @Override 注解,可以让编译器帮忙检查是否满足上面的三个限制条件。)
            • 子类方法的访问权限必须大于等于父类方法;
            • 子类方法的返回类型必须是父类方法返回类型或为其子类型。
            • 子类方法抛出的异常类型必须是父类抛出异常类型或为其子类型。
          • 在调用一个方法时,先从本类中查找看是否有对应的方法,如果没有再到父类中查看,看是否从父类继承来。否则就要对参数进行转型,转成父类之后看是否有对应的方法。总的来说,方法调用的优先级为:
            • this.func(this)
            • super.func(this)
            • this.func(super)
            • super.func(super)
        • 重载(Overload)
          • 存在于同一个类中,指一个方法与已经存在的方法名称上相同,但是参数类型、个数、顺序至少有一个不同。
          • 应该注意的是,返回值不同,其它都相同不算是重载。
    • 多态
      • 多态是同一个行为具有多个不同表现形式或形态的能力。
  • 抽象类、接口
    • 接口
      • 接口的属性默认都是 static 和 final 的。
      • 版本区别
        • 接口是抽象类的延伸,在 Java 8 之前,它可以看成是一个完全抽象的类,也就是说它不能有任何的方法实现。
        • 从 Java 8 开始,接口也可以拥有默认的方法实现,这是因为不支持默认方法的接口的维护成本太高了。在 Java 8 之前,如果一个接口想要添加新的方法,那么要修改所有实现了该接口的类,让它们都实现新增的方法。
        • 接口的成员(字段 + 方法)默认都是 public 的,并且不允许定义为 private 或者 protected。从 Java 9 开始,允许将方法定义为 private,这样就能定义某些复用的代码又不会把方法暴露出去。
    • 抽象类(abstract class)和接口(interface)区别
      • 语法上的区别
        • 抽象类只能单继承,接口可以多实现。
        • 抽象类可以有构造方法,接口中不能有构造方法。
        • 抽象类中可以有成员变量,接口中没有成员变量,只能有常量(默认就是 public static final)
        • 抽象类中可以包含非抽象的方法,在 Java 7 之前接口中的所有方法都是抽象的,在 Java 8 之后,接口支持非抽象方法:default 方法、静态方法等。Java 9 支持私有方法、私有静态方法。
        • 抽象类中的抽象方法类型可以是任意修饰符,Java 8 之前接口中的方法只能是 public 类型,Java 9 支持 private 类型。
      • 设计思想的区别
        • 接口是自上而下的抽象过程,接口规范了某些行为,是对某一行为的抽象。我需要这个行为,我就去实现某个接口,但是具体这个行为怎么实现,完全由自己决定。
        • 抽象类是自下而上的抽象过程,抽象类提供了通用实现,是对某一类事物的抽象。我们在写实现类的时候,发现某些实现类具有几乎相同的实现,因此我们将这些相同的实现抽取出来成为抽象类,然后如果有一些差异点,则可以提供抽象方法来支持自定义实现。
  • 枚举
    • 枚举是一个被命名的整型常数的集合,用于声明一组带标识符的常数。
    • 在 JDK 1.5 之前没有枚举类型,那时候一般用接口常量来替代。而使用 Java 枚举类型 enum 可以更贴近地表示这种常量。
    • 常见用法
      • 常量
      • switch
      • 向枚举中添加新方法
      • 覆盖枚举的方法
      • 实现接口
      • 使用接口组织枚举
      • 枚举集合
        • java.util.EnumSet 和 java.util.EnumMap 是两个枚举集合。EnumSet 保证集合中的元素不重复;EnumMap 中的 key 是 enum 类型,而 value 则可以是任意类型。
  • 注解
    • Java 注解是附加在代码中的一些元信息,用于一些工具在编译、运行时进行解析和使用,起到说明、配置的功能。注解不会也不能影响代码的实际逻辑,仅仅起到辅助性的作用。
    • 格式
      • public @interface 注解名称{
            属性列表;
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75
        76
        77
        78
        79
        80
        81
        82
        83
        84
        85
        86
        87
        88
        89
        90
        91
        92
        93
        94
        95
        96
        97
        98
        99
        100
        101
        102
        103
        104
        105
        106
        107
        108
        109
        110
        111
        112
        113
        114
        115
        116
        117
        118
        119
        120
        121
        122
        123
        124
        125
        126
        127
        128
        129
        130
        131
        132
        133
        134
        135
        136
        137
        138
        139
        140
        141
        142
        143
        144
        145
        146
        147
        148
        149
        150
        151
        152
        153
        154
        155
        156
        157
        158
        159
        160
        161
        162
        163
        164
        165
        166
        167
        168
        169
        170
        171
        172
        173
        174
        175
        176
        177
        178
        179
        180
        181
        182
        183
        184
        185
        186
        187
        188
        189
        190
        191
        192
        193
        194
        195
        196
        197
        198
        199
        200
        201
        202
        203
        204
        205
        206
        207
        208
        209
        210
        211
        212
        213
        214
        215
        216
        217
        218
        219
        220
        221
        222
        223
        224
        225
        226
        227
        228
        229
        230
        231
        232
        233
        234
        235
        236
        237
        238
        239
        240
        241
        242
        243
        244
        245
        246
        247
        248
        249
        250
        251
        252
        253
        254
        255
        256
        257
        258
        259
        260
        261
        262
        263
        264
        265
        266
        267
        268
        269
        270
        271
        272
        273
        274
        275
        276
        277
        278
        279
        280
        281
        282
        283
        284
        285
        286
        287
        288
        289
        290
        291
        292
        293
        294
        295
        296
        297
        298
        299
        300
        301
        302
        303
        304
        305
        306
        307
        308
        309
        310
        311
        312
        313
        314
        315
        316
        317
        318
        319
        320
        321
        322
        323
        324
        325
        326
        327
        328
        329
        330
        331
        332
        333
        334
        335
        336
        337
        338
        339
        340
        341
        342
        343
        344
        345
        346
        347
        348
        349
        350
        351
        352
        353
        354
        355
        356
        357
        358
        359
        360
        361
        362
        363
        364
        365
        366
        367
        368
        369
        370
        371
        372
        373
        374
        375
        376
        377
        378
        379
        380
        381
        382
        383
        384
        385
        386
        387
        388
        389
        390
        391
        392
        393
        394
        395
          - 分类
        - 自定义注解
        - JDK 内置注解
        - 比如 @Override 检验方法重写,@Deprecated 标识方法过期等
        - 第三方框架提供的注解
        - 比如 SpringMVC 的 @Controller 等
        - 使用位置
        - 实际开发中,注解常常出现在类、方法、成员变量、形参位置。
        - 作用
        - 目的是为当前读取该注解的程序提供判断依据。比如程序只要读到加了 @Test 的方法,就知道该方法是待测试方法,又比如 @Before 注解,程序看到这个注解,就知道该方法要放在 @Test 方法之前执行。
        - 级别
        - 注解和类、接口、枚举是同一级别的。
        - 元注解
        - 所谓元注解,就是加在注解上的注解。
        - 常用元注解
        - @Documented
        - 用于制作文档
        - @Target
        - 加在注解上,限定该注解的使用位置。不写的话,好像默认各个位置都是可以的。如果需要限定注解的使用位置,可以在自定义的注解上使用该注解。
        - @Retention(注解的保留策略)
        - 注解的保留策略有三种:SOURCE/CLASS/RUNTIME
        - 注解主要被反射读取
        - 反射只能读取内存中的字节码信息
        - RetentionPolicy.CLASS 指的是保留到字节码文件,它在磁盘内,而不是内存中。虚拟机将字节码文件加载进内存后注解会消失
        - 要想被反射读取,保留策略只能用RUNTIME,即运行时仍可读取
        - 注解的读取并不只有反射一种途径。比如 @Override,它由编译器读取(你写完代码 ctrl+s 时就编译了),而编译器只是检查语法错误,此时程序尚未运行。@Override 的保留策略是 SOURCE。
        - 属性的数据类型及特别的属性
        - value 属性
        - 如果注解的属性只有一个,且叫 value,那么使用该注解时,可以不用指定属性名,因为默认就是给 value 赋值。但是注解的属性如果有多个,无论是否叫value,都必须写明属性的对应关系。
        - 数组属性
        -
        - 反射
        - 每个类都有一个**Class**对象,包含了与类有关的信息。当编译一个新类时,会产生一个同名的 .class 文件,该文件内容保存着 Class 对象。
        - 类加载相当于 Class 对象的加载,类在第一次使用时才动态加载到 JVM 中。也可以使用 `Class.forName("com.mysql.jdbc.Driver")` 这种方式来控制类的加载,该方法会返回一个 Class 对象。
        - 反射可以提供运行时的类信息,并且这个类可以在运行时才加载进来,甚至在编译时期该类的 .class 不存在也可以加载进来。
        - 反射的三种方式
        - 通过 new 对象实现反射:`obj.getClass()`
        - 通过路径实现:`Class.forName()`
        - 通过类名实现:`Clazz.class`
        - Class 和 java.lang.reflect 一起对反射提供了支持,java.lang.reflect 类库主要包含了以下三个类:
        - **Field** :可以使用 `get()` 和 `set()` 方法读取和修改 Field 对象关联的字段;
        - **Method** :可以使用 `invoke()` 方法调用与 Method 对象关联的方法;
        - **Constructor** :可以用 Constructor 的 `newInstance()` 创建新的对象。
        - 整体流程
        - 准备阶段:编译期装载所有的类,将每个类的元信息保存至 Class 类对象中,每一个类对应一个 Class 对象
        - 获取 Class 对象:调用 `x.class/x.getClass()/Class.forName()` 获取 x 的 Class 对象 clz
        - 进行实际反射操作:通过 clz 对象获取 Field/Method/Constructor 对象进行进一步操作
        - 优点
        - **可扩展性**:应用程序可以利用全限定名创建可扩展对象的实例,来使用来自外部的用户自定义类。
        - **类浏览器和可视化开发环境**:一个类浏览器需要可以枚举类的成员。可视化开发环境(如 IDE)可以从利用反射中可用的类型信息中受益,以帮助程序员编写正确的代码。
        - **调试器和测试工具**:调试器需要能够检查一个类里的私有成员。测试工具可以利用反射来自动地调用类里定义的可被发现的 API 定义,以确保一组测试中有较高的代码覆盖率。
        - 缺点
        - **性能开销**:反射涉及了动态类型的解析,所以 JVM 无法对这些代码进行优化。因此,反射操作的效率要比那些非反射操作低得多。我们应该避免在经常被执行的代码或对性能要求很高的程序中使用反射。
        - **安全限制**:使用反射技术要求程序必须在一个没有安全限制的环境中运行。如果一个程序必须在有安全限制的环境中运行,如 Applet,那么这就是个问题了。
        - **内部暴露**:由于反射允许代码执行一些在正常情况下不被允许的操作(比如访问私有的属性和方法),所以使用反射可能会导致意料之外的副作用,这可能导致代码功能失调并破坏可移植性。反射代码破坏了抽象性,因此当平台发生改变的时候,代码的行为就有可能也随着变化。
        - 范型
        - 泛型的本质是为了参数化类型(在不创建新的类型的情况下,通过泛型指定的不同类型来控制形参具体限制的类型)。也就是说在泛型使用过程中,操作的数据类型被指定为一个参数,这种参数类型可以用在类、接口和方法中,分别被称为泛型类、泛型接口、泛型方法。
        - 限定通配符和非限定通配符
        - 限定通配符
        - `<? extends T>`
        - 确保类型必须是T的子类来设定类型的上界
        - `<? super T>`
        - 确保类型必须是T的父类来设定类型的下界
        - 非限定通配符
        - `<?>`
        - 用任意类型来替代
        - 实现原理
        - 泛型是通过类型擦除来实现的,编译器在编译时擦除了所有类型相关的信息,所以在运行时不存在任何类型相关的信息。例如`List<String>`在运行时仅用一个 List 来表示。这样做的目的,是确保能和 Java5 之前的版本开发二进制类库进行兼容。你无法在运行时访问到类型参数,因为编译器已经把泛型类型转换成了原始类型。

        ### 关键字
        - 保留关键字
        - const
        - 常量,常数:用于修改字段或局部变量的声明。
        - goto
        - 转到:指定跳转到标签,找到标签后,程序将处理从下一行开始的命令
        - 访问修饰符的关键字
        - public (公有的):可跨包
        - protected(受保护的):当前包内可用
        - private(私有的):当前类可用
        - 定义类、接口、抽象类和实现接口、继承类的关键字、实例化对象
        - class(类):`public class A(){}` 花括号里是已实现的方法体,类名需要与文件名相同
        - interface(接口):`public interface B(){}` 花括号里有方法体,但没有实现,方法体句子后面是英文分号 ; 结尾
        - abstract(声明抽象):`public abstract class C(){}` 介于类与接口中间,可以有,也可以没有已经实现的方法体
        - implemenst(实现):用于类或接口,实现接口 `public class A interface B(){}`
        - extends(继承):用于类继承类 `public class A extends D(){}`
        - new(创建新对象):`A a=new A();` A 表示一个类
        - 包的关键字
        - import(引入包的关键字):当使用某个包的一些类时,仅需要类名
        - package(定义包的关键字):将所有相关的类放在一个包类以便查找修改等
        - 数据类型的关键字
        - byte(字节型):8bit
        - char(字节型):16bit
        - boolean(布尔型):--
        - short(短整型):16bit
        - int(整型):32bit
        - float(浮点型):32bit
        - long(长整型):64bit
        - double(双精度):64bit
        - void(无返回):`public void A(){}` 其他需要反回的经常与 return 连用
        - null(空值)
        - true(真)
        - false(假)
        - 条件循环(流程控制)
        - if(如果):if(条件语句{执行代码}如果条件语句成立,就开始执行{}里面的内容
        - else(否则,或者):常与 if 连用,用法相同:`if(...){...}else{...}`
        - while(当什么时候):while(条件语句){执行代码}
        - for(满足三个条件时):`for(初始化循环变量;判断条件;循环变量值){}`
        - switch(选择结构):`switch(表达式){case 常量表达式1: 语句1;...case 常量表达式2; 语句2; default:语句;}` default 就是如果没有匹配的 case 就执行它,default 并不是必须的。case 后的语句可以不用大括号。
        - case(匹配switch的表达式里的结果):同上
        - default(默认):default 就是如果没有匹配的 case 就执行它,default 并不是必须的
        - do(运行):通常与 while 连用
        - break(跳出循环):直接跳出循环,执行循环体后的代码
        - continue(继续):中断本次循环,并开始下一轮循环
        - return(返回):return 一个返回值类型
        - instanceof(实例):一个二元操作符,和 ==、>、<是 同一类的。测试它左边的对象是否是它右边的类的实例,返回 boolean 类型的数据
        - 修饰方法、类、属性和变量
        - static(静态的)
        - 静态变量
        - 对应 *实例变量*
        - 静态方法
        - 方法中不能有 this 和 super 关键字,因为这两个关键字与具体对象关联。
        - 静态语句块
        - 静态内部类
        - 非静态内部类依赖于外部类的实例,也就是说需要先创建外部类实例,才能用这个实例去创建非静态内部类。而静态内部类不需要。
        - 静态内部类不能访问外部类的非静态的变量和方法。
        - 静态导包
        - 在使用静态变量和方法时不用再指明 ClassName,从而简化代码,但可读性大大降低。
        - 初始化顺序
        - 静态变量和静态语句块优先于实例变量和普通语句块,静态变量和静态语句块的初始化顺序取决于它们在代码中的顺序。
        - final(最终的不可被改变)
        - 数据
        - 对于基本类型,final 使数值不变;
        - 对于引用类型,final 使引用不变,也就不能引用其它对象,但是被引用的对象本身是可以修改的。
        - 方法
        - 不能被子类重写。
        - private 方法隐式地被指定为 final,如果在子类中定义的方法和基类中的一个 private 方法签名相同,此时子类的方法不是重写基类方法,而是在子类中定义了一个新的方法。
        - 类
        - 不允许被继承。
        - super(调用父类的方法):常见 `public void paint(Graphics g){super.paint(g);...}`
        - this(当前类的父类的对象):调用当前类中的方法(表示调用这个方法的对象)`this.addActionListener(al);` 等等
        - native(本地)
        - strictfp(严格,精准)
        - synchronized(线程,同步):一个时间内只能有一个线程得到执行。另一个线程必须等待当前线程执行完这个代码块以后才能执行该代码块
        - transient(短暂)
        - volatile(易失)
        - 可⻅性
        - volatile 可⻅性是由指令原子性保证的,在 jmm 中定义了 8 类原子性指令,比如 write、store、read、load。而 volatile 就要求 write-store、load-read 成为一个原子性操作,这样子可以确保在读取的时候都是从主内存读入,写入的时候会同步到主内存中。
        - JVM 线程工作时的原子性指令有:
        - lock
        - 将主内存中的变量锁定,为一个线程所独占。
        - unclock
        - 将 lock 加的锁定解除,此时其它的线程可以有机会访问此变量。
        - read
        - 将主内存中的变量值读到工作内存当中。
        - load
        - 将 read 读取的值保存到工作内存中的变量副本中。
        - use
        - 将值传递给线程的代码执行引擎。
        - assign
        - 将执行引擎处理返回的值重新赋值给变量副本。
        - store
        - 将变量副本的值存储到主内存中。
        - write
        - 将 store 存储的值写入到主内存的共享变量当中。
        - MESI协议:在早期的 CPU 中,是通过在总线加 LOCK #锁的方式实现的,但这种方式开销太大,所以 Intel 开发了缓存一致性协议,也就是 MESI 协议,该解决缓存一致性的思路是:当 CPU 写数据时,如果发现操作的变量是共享变量,即在其他 CPU 中也存在该变量的副本,那么他会发出信号通知其他 CPU 将该变量的缓存行设置为无效状态。当其他 CPU 使用这个变量时,首先会去嗅探是否有对该变量更改的信号,当发现这个变量的缓存行已经无效时,会从新从内存中读取这个变量。
        - volatile 内部实现机制就是 MESI 协议,应该是先判断该变量的缓存行状态是否失效,如果失效,才会重新从内存中读取该变量的值,而不是每次都从内存中读取。
        - 有序性(防止指令重排序)
        - **如何保证线程间可⻅和避免指令重排?**
        - 是由内存屏障来保证的,由两个内存屏障:
        - 一个是编译器屏障:阻止编译器重排,保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。
        - 第二个是 cpu 屏障:sfence 保证写入,lfence 保证读取,lock 类似于锁的方式。java 多执行了一个 `load addl $0x0, (%esp)` 操作,这个操作相当于一个 lock 指令,就是增加一个完全的内存屏障指令。
        - 保障变量单次读,写操作的原子性,但不能保证 i++ 这种操作的原子性,因为本质是读、写两次操作
        - 错误处理
        - catch(处理异常)
        - try(捕获异常)
        - finally(有没有异常都执行)
        - throw(抛出一个异常对象)
        - throws(声明一个异常可能被抛出)
        - 其他
        - enum(枚举)
        - assert(断言)

        ### Java 基本类型
        - boolean
        - 在 Java 虚拟机中没有任何供 boolean 值专用的字节码指令,Java 语言表达式所操作的 boolean 值,在编译之后都使用 Java 虚拟机中的 int 数据类型来代替,而 boolean 数组将会被编码成 Java 虚拟机的 byte 数组,每个元素 boolean 元素占 8 位。**具体还取决于虚拟机的实现**。
        - **那虚拟机为什么要用 int 来代替 boolean 呢?为什么不用 byte 或 short,这样不是更节省内存空间吗。**
        - 经过查阅资料发现,使用 int 的原因是,对于当下 32 位的处理器(CPU)来说,一次处理数据是 32 位(这里不是指的是 32/64 位系统,而是指 CPU 硬件层面),32 位 CPU 使用 4 个字节是最为节省的,哪怕你是 1 个 bit 他也是占用 4 个字节。因为 CPU 寻址系统只能 32 位 32 位地寻址,具有高效存取的特点。
        - byte
        - 8 位带符号二进制数的取值范围是 `[-128, 127]`
        - 计算时候将他们提升为 int 类型,再进行计算
        - short
        - 16 位
        - int
        - 32 位
        - long
        - 64 位
        - float
        - 32 位
        - double
        - 64 位
        - **自动类型转换规则**
        - 基本就是先转换为高位数据类型,再参加运算,结果也是最高位的数据类型;
        1. 如操作数之一为 double,则另一个操作数先被转化为 double,再参与算术运算。
        2. 如两操作数均不为 double,当操作数之一为 float,则另一操作数先被转换为 float,再参与运算。
        3. 如两操作数均不为 double 或 float,当操作数之一为 long,、则另一操作数先被转换为 long,再参与算术运算。
        4. 如两操作数均不为 double、float 或 long,则两操作数先被转换为 int,再参与运算。
        - byte short char 运算会转换为 int;
        - **当运算符为自动递增运算符(++)或自动递减运算符(--)时,如果操作数为 byte,short 或 char 类型不发生改变。**
        - **如采用 ++、--、+=、*= 等缩略形式的运算符,系统会自动强制将运算结果转换为目标变量的类型。**
        - 基本类型对应的缓冲池如下【在使用这些基本类型对应的包装类型时,如果该数值范围在缓冲池范围内,就可以直接使用缓冲池中的对象。】:
        - boolean values true and false
        - all byte values
        - short values between -128 and 127
        - int values between -128 and 127
        - char in the range \u0000 to \u007F

        ### 语法
        - switch
        - 从 Java 7 开始,可以在 switch 条件判断语句中使用 String 对象。
        - switch 不支持 long、float、double,是因为 switch 的设计初衷是对那些只有少数几个值的类型进行等值判断,如果值过于复杂,那么还是用 if 比较合适。

        ### 内置对象
        #### Object
        - Object 通用方法
        - `public native int hashCode()`
        - `public boolean equals(Object obj)`
        - `protected native Object clone() throws CloneNotSupportedException`
        - `clone()` 方法并不是 Cloneable 接口的方法,而是 Object 的一个 protected 方法。Cloneable 接口只是规定,如果一个类没有实现 Cloneable 接口又调用了 c`lone()` 方法,就会抛出 CloneNotSupportedException。
        - `public String toString()`
        - `public final native Class<?> getClass()`
        - `protected void finalize() throws Throwable {}`
        - 子类可以覆盖该方法以实现资源清理工作,GC 在回收对象之前调用该方法。
        - 与C++中的析构函数不是对应的。C++ 中的析构函数调用的时机是确定的(对象离开作用域或 delete 掉),但 Java 中的 finalize 的调用具有不确定性
        - 不建议用 finalize 方法完成“非内存资源”的清理工作,但建议用于:
        - 清理本地对象(通过JNI创建的对象);
        - 作为确保某些非内存资源(如 Socket、文件等)释放的一个补充:在finalize方法中显式调用其他资源释放方法。
        - finalize 的问题
        - 一些与 finalize 相关的方法,由于一些致命的缺陷,已经被废弃了,如 `System.runFinalizersOnExit()` 方法、`Runtime.runFinalizersOnExit()` 方法
        - `System.gc()` 与 `System.runFinalization()` 方法增加了 finalize 方法执行的机会,但不可盲目依赖它们
        - Java 语言规范并不保证 finalize 方法会被及时地执行、而且根本不会保证它们会被执行
        - finalize 方法可能会带来性能问题。因为 JVM 通常在单独的低优先级线程中完成 finalize 的执行
        - 对象再生问题:finalize 方法中,可将待回收对象赋值给 GC Roots 可达的对象引用,从而达到对象再生的目的
        - finalize 方法至多由 GC 执行一次(用户当然可以手动调用对象的 finalize 方法,但并不影响 GC 对 finalize 的行为)
        - finalize 的执行过程(生命周期)
        - 当对象变成(GC Roots)不可达时,GC 会判断该对象是否覆盖了 finalize 方法,若未覆盖,则直接将其回收。否则,若对象未执行过 finalize 方法,将其放入 F-Queue 队列,由一低优先级线程执行该队列中对象的 finalize 方法。执行 finalize 方法完毕后,GC 会再次判断该对象是否可达,若不可达,则进行回收,否则,对象“复活”。
        - 一般用途
        - 对象复活
        - 覆盖 finalize 方法以确保资源释放
        - 作为一个补充操作,以防用户忘记“关闭”资源,JDK 中 FileInputStream、FileOutputStream、Connection 类均用了此“技术”
        - 版本
        - 在 Java 9 中该方法已经被标记为废弃,并添加新的 java.lang.ref.Cleaner,提供了更灵活和有效的方法来释放资源
        - `public final native void notify()`
        - `public final native void notifyAll()`
        - `public final native void wait(long timeout) throws InterruptedException`
        - `public final void wait(long timeout, int nanos) throws InterruptedException`
        - `public final void wait() throws InterruptedException`

        #### String、StringBuilder、StringBuffer
        - StringBuilder
        - 线程不安全
        - StringBuffer
        - 线程安全
        - String
        - String 类是 final 类,也即意味着 String 类不能被继承,并且它的成员方法都默认为 final 方法。
        - String 类包含三个成员变量:char value[],int offset,int count,他们分别用来:存储真正的字符数组、存储数组的第一个位置索引、存储字符串中包含的字符个数。
        - 在 Java 9 之后,String 类的实现改用 byte 数组存储字符串,同时使用 `coder` 来标识使用了哪种编码。
        - 字符串拼接
        - 在字符串拼接的场景下,Java 编译器会自动进行优化,新建一个 StringBuilder 对象,然后调用 append 方法进行字符串的拼接。而在最后,调用了 StringBuilder 的 toString 方法,生成了一个新的字符串对象,而不是引用的常量池中的常量。
        - 方法:
        - `substring()`
        - JDK 6:会创建一个新的 String 对象,但是这个 String 的数组然指向堆中的同一个字符数组。这两个对象中只有 count 和 offset 的值是不同的。
        - **存在的问题**:如果有一个很长的字符串,但是你只需要使用很短的一段,于是你使用 substring 进行切割,但是由于你实际上引用了整个字符串,这个很长的字符串无法被回收。往小了说,造成了存储空间的浪费,往大了说,可能造成内存泄漏。
        - JDK 7:会在堆中创建一个新的数组
        - 相关问题
        - **为什么 String 在 Java 是不可更改的?**
        - 字符串常量池的需要
        - 当一个 string 被创建如果这个 string 已经在内存里面存在了,那个存在的 string 的引用被返回,而不是创建个新的对象和返回它的引用。
        - 缓存哈希值
        - 在 Java 中,string 的哈希值经常被用。举个例子,在 HashMap 中。保持不变,可以保证总是返回相同的哈希值。所以它可以被缓存而不用担心被改变。这意味这不需要在使用的时候每次都计算哈希值。这将更高效。
        - 使其他类的使用更加容易
        - 安全
        - String 在很多 Java 的类中,网络连接中,打开的文件中经常被作为参数使用。如果 String 是可以改变的,一个连接或者文件将有可能被改变,这将导致严肃的安全威胁。这个方法认为它正连接到一个机器,但是实际上不是。易变的 strings 将在反射或者作为参数将导致安全问题。
        - 不变对象是自然线程安全
        - 因为不可变对象是不可以改变的,它能够被多个线程自由的共享。这消除了同步。

        #### 容器
        容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。

        ##### Collection
        - Set
        - TreeSet
        - 基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 $O(1)$,TreeSet 则为 $O(logN)$。
        - HashSet
        - 基于哈希表实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
        - LinkedHashSet
        - 具有 HashSet 的查找效率,并且内部使用双向链表维护元素的插入顺序。
        - CopyOnWriteArraySet
        - List
        - ArrayList
        - 用数组实现的存储
        - 线程不安全。可以用 Collections.synchronizedList 把一个普通 ArrayList 包装成一个线程安全版本的数组容器。
        - 特点
        - 查询效率高,增删效率低
        - 扩容机制
        - 插入数据时,会调用 `ensureCapacityInternal` 方法。
        - 扩容后的大小为
        - 原来的 1.5 倍
        - 版本区别
        - JDK 1.7 以前会调用 `this(10)` 才是真正的容量为 10
        - 1.7 及本身以后是默认走了空数组,只有第一次 add 的时候容量会变成 10
        - LinkedList
        - 基于双向链表
        - 使用了尾插法的方式,内部维护了链表的⻓度,以及头节点和尾节点,所以获取⻓度不需要遍历
        - 特点
        - 适合一些插入、删除频繁的情况。
        - Vector
        - 线程安全。就是把所有的方法统统加上 synchronized 了。
        - PriorityQueue
        - 基于堆结构实现,可以用它来实现优先队列。
        - CopyOnWriteArrayList
        - CopyOnWriteArrayList,运用了一种“写时复制”的思想。通俗的理解就是当我们需要修改(增/删/改)列表中的元素时,不直接进行修改,而是先将列表 Copy,然后在新的副本上进行修改,修改完成之后,再将引用从原列表指向新列表。
        - 适用于“读多写少”
        - 核心方法
        - 查询【get 方法】
        - get 方法并没有加锁,直接返回了内部数组对应索引位置的值
        - 添加【add 方法】
        - add 方法首先会进行加锁,保证只有一个线程能进行修改;然后会创建一个新数组(大小为 n+1),并将原数组的值复制到新数组,新元素插入到新数组的最后;最后,将字段 array 指向新数组。
        - 删除【remove 方法】
        - 删除方法和插入一样,都需要先加锁(所有涉及修改元素的方法都需要先加锁,写-写不能并发),然后构建新数组,复制旧数组元素至新数组,最后将 array 指向新数组。
        - 迭代
        - CopyOnWriteArrayList 对元素进行迭代时,仅仅返回一个当前内部数组的快照,也就是说,如果此时有其它线程正在修改元素,并不会在迭代中反映出来,因为修改都是在新数组中进行的。
        - 存在的一些问题
        - 内存的使用
        - 由于 CopyOnWriteArrayList 使用了“写时复制”,所以在进行写操作的时候,内存里会同时存在两个 array 数组,如果数组内存占用的太大,那么可能会造成频繁 GC,所以 CopyOnWriteArrayList 并不适合大数据量的场景。
        - 数据一致性
        - CopyOnWriteArrayList 只能保证数据的最终一致性,不能保证数据的实时一致性——读操作读到的数据只是一份快照。所以如果希望写入的数据可以立刻被读到,那 CopyOnWriteArrayList 并不适合。
        - 阻塞队列
        - 都是线程安全的
        - ArrayBlockingQueue
        - 一个由数组结构组成的有界阻塞队列
        - 内部用 ReentrantLock 实现线程安全
        - 方法
        - 入队方法
        - `add(E e)`
        - 调用 offer 方法,数组满了就抛出异常
        - `offer(E e)`
        - 如果数组满了就返回 false
        - `put(E e)`
        - 如果数组满了,用 Lock 的 Condition 实现等待,然后出队列的时候进行唤醒,无返回值
        - `offer(E e, long timeout, TimeUnit unit)`
        - 如果数组满了,用 Lock 的 Condition 实现等待(有最大等待时常)
        - 出队方法
        - `remove()`
        - 调用 poll 方法,没有返回元素则抛出异常
        - `poll()`
        - 没有返回元素则返回 null
        - `take()`
        - 没有返回元素,则用 Lock 的 Condition 实现等待,然后有元素的时候唤醒返回
        - `poll(long timeout, TimeUnit unit)`
        - 没有返回元素,用 Lock 的 Condition 实现等待(有最大等待时常)
        - LinkedBlockingQueue
        - 一个由链表结构组成的有界阻塞队列。
        - PriorityBlockingQueue
        - 一个支持优先级排序的无界阻塞队列。
        - DealyQueue
        - 一个使用优先级队列实现的无界阻塞队列。
        - SynchronousQueue
        - 一个不存储元素的阻塞队列。
        - LinkedTransferQueue
        - 一个由链表结构组成的无界阻塞队列。
        - LinkedBlockingDeque
        - 一个由链表结构组成的双向阻塞队列。

        ##### Map
        - ![Java_Map对比](Java-basic-0-知识点汇总/Java_Map对比.jpg)
        - HashMap
        - 线程不安全。可以使用 `Collections.synchronizedMap(Map)` 创建线程安全的 map 集合。
        - **Collections.synchronizedMap 是怎么实现线程安全的?**
        - 在 SynchronizedMap 内部维护了一个普通对象 Map,还有排斥锁 mutex。
        - 在调用这个方法的时候就需要传入一个 Map,有两个构造器,如果传入了 mutex 参数,则将对象排斥锁赋值为传入的对象。如果没有,则将对象排斥锁赋值为 this。
        - 创建出 SynchronizedMap 之后,再操作 map 的时候,就会对方法上锁。
        - 由数组和链表组合构成。
        - 初始容量 16。
        - 负载因子默认 0.75。
        - 根据泊松分布,在负载因子默认为 0.75 的时候,单个 hash 槽内元素个数为 8 的概率小于百万分之一,所以将 7 作为一个分水岭,**等于 7 的时候不转换,大于等于 8 的时候才进行转换为红黑树,小于等于 6 的时候就化为链表**。
        - HashMap 的键值则都可以为 null。
        - hash 方法
        - 扰动函数
        - 混合原始哈希码的高位和低位,以此来加大低位的随机性。
        - Java 7
        - ```
        static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
        }
        - Java 8 中,做一次 16 位右位移异或混合 - ``` //Java 8中的散列值优化函数 static final int hash(Object key) { int h; int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //key.hashCode()为哈希算法,返回初始哈希值 }
    • 操作
      • 扩容机制
        • 当现有容量大于总容量 * 负载因子时,HashMap 扩容规则为当前容量翻倍。
        • 扩容流程
          • Java_HashMap_resize流程
      • 迭代器
        • HashMap 中的 Iterator 迭代器是 fail-fast 的。
          • 快速失败(fail—fast)是 Java 集合中的一种机制,在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出 Concurrent Modification Exception。
            • 原理:
              • 迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。
              • 集合在被遍历期间如果内容发生变化,就会改变 modCount 的值。
              • 每当迭代器使用 hashNext()/next() 遍历下一个元素之前,都会检测 modCount 变量是否为 expectedmodCount 值,是的话就返回遍历;否则抛出异常,终止遍历。
              • 这里异常的抛出条件是检测到 modCount!=expectedmodCount 这个条件。如果集合发生变化时修改 modCount 值刚好又设置为了 expectedmodCount 值,则异常不会抛出。
            • java.util 包下的集合类都是快速失败的,不能在多线程下发生并发修改(迭代过程中被修改)算是一种安全机制吧。
      • 插入数据时:
        • Java8 之前是头插法。采用 数组+链表 的数据结构。
        • Java8 之后,都是所用尾部插入了。采用 Node 数组+链表+红黑树 的数据结构。
        • 插入流程
          • Java_HashMap_插入流程
        • 相关问题
          • 为什么要改插入方式?
            • 多线程 resize 的时候,可能会产生环形链表,则插入会死循环
            • 使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了
    • 相关问题
      • 为什么是非线程安全的?
        • 多线程 put(不考虑 resize)
          • 如果 hash 冲突,后一个线程覆盖前一个线程的 key-value,如在一系列线程中出现 hash 冲突的键值对个数为 N,则最多可能丢失 N-1 个键值对,即只有一个线程的键值对最终被加入到 table 内的链表或红黑树中
        • 多线程 resize
          • 可能会产生环形链表,则插入会死循环
        • 多线程 remove
          • 可能没删掉
      • 为什么容量要是 2 的幂?
        • 为了位运算的方便,位与运算比算数计算的效率高了很多
        • 当数组长度为 $2^n$ 时,$2^n − 1$ 的所有位都是 1,如 8-1=7 即 111,那么进行低位 & 运算时,值总与原来的 hash 值相同,降低了碰撞的概率
        • 当 table 数组的大小为 2 的幂次时,通过 key.hash & table.length-1 这种方式计算出的索引 i,当 table 扩容后(2 倍),新的索引要么在原来的位置 i,要么是 i+n。

          • Java_HashMap_rehash
      • 为什么重写 equals 方法的时候需要重写 hashCode 方法?
        • 这两个方法都是用来比较两个对象是否相等的
        • 未重写 equals 方法,我们是继承了 object 的 equals 方法,那里的 equals 是比较两个对象的内存地址
        • get 的时候,他就是根据 key 去 hash 然后计算出 index。所以如果我们对 equals 方法进行了重写,建议一定要对 hashCode 方法重写,以保证相同的对象返回相同的 hash 值,不同的对象返回不同的 hash 值。
      • JDK1.8 发生了哪些变化?
        1. 由数组+链表改为数组+链表+红黑树,当链表的长度超过8时,链表变为红黑树。
          • 为什么要这么改?
            • 我们知道链表的查找效率为 $O(n)$,而红黑树的查找效率为 $O(logn)$,查找效率变高了。
          • 为什么不直接用红黑树?
            • 因为红黑树的查找效率虽然变高了,但是插入效率变低了,如果从一开始就用红黑树并不合适。从概率学的角度选了一个合适的临界值为 8
        2. 优化了 hash 算法(变成位运算)
        3. 计算元素在新数组中位置的算法发生了变化,新算法通过新增位判断 oldTable[i] 应该放在 newTable[i] 还是 newTable[i+oldTable.length]
        4. 头插法改为尾插法,扩容时链表没有发生倒置(避免形成死循环)
      • 为什么不使用 AVL 树而使用红黑树?
        • 红黑树和 AVL 树都是最常用的平衡二叉搜索树,它们的查找、删除、修改都是 $O(lgn)$
        • AVL 树和红黑树有几点比较和区别:
          • AVL 树是更加严格的平衡,因此可以提供更快的查找速度,一般读取查找密集型任务,适用 AVL 树。
          • 红黑树更适合于插入修改密集型任务。
          • 通常,AVL 树的旋转比红黑树的旋转更加难以平衡和调试。
        • 总结:
          • AVL 以及红黑树是高度平衡的树数据结构。它们非常相似,真正的区别在于在任何添加/删除操作时完成的旋转操作次数。
          • 两种实现都缩放为a $O(lgN)$,其中 N 是叶子的数量,但实际上 AVL 树在查找密集型任务上更快:利用更好的平衡,树遍历平均更短。另一方面,插入和删除方面,AVL 树速度较慢:需要更高的旋转次数才能在修改时正确地重新平衡数据结构。
          • 在 AVL 树中,从根到任何叶子的最短路径和最长路径之间的差异最多为 1。在红黑树中,差异可以是 2 倍。
          • 两个都给 $O(logn)$ 查找,但平衡 AVL 树可能需要 $O(logn)$ 旋转,而红黑树将需要最多两次旋转使其达到平衡(尽管可能需要检查 $O(logn)$ 节点以确定旋转的位置)。旋转本身是 $O(1)$ 操作,因为你只是移动指针。
  • HashTable
    • 线程安全。直接在方法上锁,并发度很低,最多同时允许一个线程访问。
      • 读写枷锁
      • 为什么效率低?
        • 对数据操作的时候都会上锁,所以效率比较低下。
    • 扩容机制
      • 当现有容量大于总容量 * 负载因子时,Hashtable 扩容规则为当前容量翻倍 + 1。
    • Hashtable 是不允许键或值为 null 的。
      • 为什么 Hashtable 是不允许 KEY 和 VALUE 为 null, 而 HashMap 则可以呢?
        • 因为 Hashtable 在我们 put 空值的时候会直接抛空指针异常,但是 HashMap 却做了特殊处理(key 为 null 直接放在 table[0] 处)。
  • ConcurrentHashMap
    • 线程安全
      • 读不加锁,写不一定加锁
    • 基本结构
      • 结点定义
        • Node 结点
          • 是其它类型节点的父类
        • TreeNode 结点
          • TreeNode 就是红黑树的结点,TreeNode 不会直接链接到 table[i](桶)上面,而是由 TreeBin 链接,TreeBin 会指向红黑树的根结点。
        • TreeBin 结点
          • TreeBin 相当于 TreeNode 的代理结点。TreeBin 会直接链接到 table[i](桶)上面,该结点提供了一系列红黑树相关的操作,以及加锁、解锁操作。
        • ForwardingNode 结点
          • ForwardingNode 结点仅仅在扩容时才会使用。
          • 当最后一个线程完成迁移任务后,会遍历所有桶,看看是否都是 ForwardingNode,如果是,那么说明整个扩容/数据迁移的过程就完成了。
        • ReservationNode 结点
          • 保留结点
    • 操作
      • 插入数据时:
        • Java8 之前,是由 Segment 数组、HashEntry 组成,和 HashMap 一样,仍然是数组加链表。采用了分段锁技术,其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理,理论上 ConcurrentHashMap 支持 CurrencyLevel(Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时,不会影响到其他的 Segment。
        • Java8 之后,Node 数组+链表+红黑树,采用了 CAS + synchronized 来保证并发安全性。操作 hash值 相同的链表,头结点用 synchronized 上锁保证线程安全。
          • 步骤:
            1. 根据 key 计算出 hashcode。
            2. 判断是否需要进行初始化。
            3. 即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功。
              • table[i] 的结点类型为 Node(链表结点)时,就会将新结点以“尾插法”的形式插入链表的尾部。
              • table[i] 的结点类型为 TreeBin(红黑树代理结点)时,就会将新结点通过红黑树的插入方式插入。
            4. 如果当前位置的 hashcode == MOVED == -1 ,则需要进行扩容。
            5. 如果都不满足,则利用 synchronized 锁写入数据。
            6. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
      • 查询数据
        • 当槽 table[i] 被普通 Node 结点占用,说明是链表链接的形式,直接从链表头开始查找
        • 当槽 table[i] 被 TreeBin 结点占用时,说明链接的是一棵红黑树。由于红黑树的插入、删除会涉及整个结构的调整,所以通常存在读写并发操作的时候,是需要加锁的
      • 扩容
        • Hash 表的扩容,一般都包含两个步骤:
          • table 数组的扩容
            • table 数组的扩容,一般就是新建一个 2 倍大小的槽数组,这个过程通过由一个单线程完成,且不允许出现并发。
          • 数据迁移
            • 把旧 table 中的各个槽中的结点重新分配到新 table 中。
        • transfer 方法,这个方法可以被多个线程同时调用,也是“数据迁移”的核心操作方法
        • transfer 方法主要包含 4 个分支,即对 4 种不同情况进行处理
          • table[i] 为空
            • 当旧 table 的桶 table[i] == null,说明原来这个桶就没有数据,那就直接尝试放置一个 ForwardingNode,表示这个桶已经处理完成。
          • table[i] 已迁移完成
          • table[i] 未迁移完成
            • 如果旧桶的数据未迁移完成,就要进行迁移,这里根据桶中结点的类型分为:链表迁移、红黑树迁移
              • 链表迁移
                1. 链表迁移的过程如下,首先会遍历一遍原链表,找到最后一个相邻的 runBit 不同的结点。
                  • runbit 是根据 key.hash 和旧 table 长度 n 进行与运算得到的值,由于 table 的长度为 2 的幂次,所以 runbit 只可能为 0 或最高位为 1
                2. 然后,会进行第二次链表遍历,按照第一次遍历找到的结点为界,将原链表分成 2 个子链表,再链接到新 table 的槽中。可以看到,新 table 的索引要么是 i,要么是 i+n
              • 红黑树迁移
                • 红黑树的迁移按照链表遍历的方式进行,当链表结点超过/小于阈值时,涉及红黑树<->链表的相互转换
          • 当前是最后一个迁移任务或出现扩容冲突
    • 安全失败:
      • java.util.concurrent 包下的容器都是安全失败,可以在多线程下并发使用,并发修改。
      • 采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。
    • 迭代器:
      • 是弱一致性迭代器。ConcurrentHashMap 的迭代器创建后,就会按照哈希表结构遍历每个元素,但在遍历过程中,内部元素可能会发生变化,如果变化发生在已遍历过的部分,迭代器就不会反映出来,而如果变化发生在未遍历过的部分,迭代器就会发现并反映出来,这就是弱一致性。
      • ConcurrentHashMap 中每个结点指向下一个结点的 next 是不可变的(final)。concurrentHashMap 的删除操作是通过将被删除的元素重新复制一遍实现的。也就是说,如果 A 删掉了第 7 个元素,此时 B 已经遍历到了第 3 个元素,那么 B 还是可以遍历到被删除的第 7 个元素(Java1.8 之前)。
  • TreeMap
    • TreeMap 是会自动进行排序的,也就是一个有序 Map(使用了红黑树来实现)
  • LinkedHashMap
    • 有序的 HashMap,和 TreeMap 是不一样的概念,是用了 HashMap+双向链 的方式来构造的
    • 线程不安全
    • 顺序
      • 插入顺序(默认实现)
        • 插入的是什么顺序,读出来的就是什么顺序
      • 访问顺序
        • 每次 get 的时候都会把链表的节点移除掉,放到链表的最后面。这样子就是一个 LRU 的一种实现方式。

I/O

  • 基本概念
    • 同步、异步
      • 同步:同步就是发起一个调用后,被调用者未处理完请求之前,调用不返回。
      • 异步:异步就是发起一个调用后,立刻得到被调用者的回应表示已接收到请求,但是被调用者并没有返回结果,此时我们可以处理其他的请求,被调用者通常依靠事件,回调等机制来通知调用者其返回结果。
      • 同步和异步的区别最大在于异步的话调用者不需要等待处理结果,被调用者会通过回调等机制来通知调用者其返回结果。
    • 阻塞、非阻塞
      • 阻塞:阻塞就是发起一个请求,调用者一直等待请求结果返回,也就是当前线程会被挂起,无法从事其他任务,只有当条件就绪才能继续。
      • 非阻塞:非阻塞就是发起一个请求,调用者不用一直等着结果返回,可以先去干其他事情。
    • 相关问题
      • 同步阻塞、同步非阻塞和异步非阻塞又代表什么意思呢?
        • 举个生活中简单的例子,你妈妈让你烧水,小时候你比较笨啊,在哪里傻等着水开(同步阻塞)。等你稍微再长大一点,你知道每次烧水的空隙可以去干点其他事,然后只需要时不时来看看水开了没有(同步非阻塞)。后来,你们家用上了水开了会发出声音的壶,这样你就只需要听到响声后就知道水开了,在这期间你可以随便干自己的事情,你需要去倒水了(异步非阻塞)。
  • I/O 方式
    • BIO(Blocking I/O)
      • 传统 BIO
        • 同步阻塞 I/O 模式,数据的读取写入必须阻塞在一个线程内等待其完成。
        • Java_BIO通信模型图
        • 采用 BIO 通信模型 的服务端,通常由一个独立的 Acceptor 线程负责监听客户端的连接。我们一般通过在 while(true) 循环中服务端会调用 accept() 方法等待接收客户端的连接的方式监听请求,请求一旦接收到一个连接请求,就可以建立通信套接字在这个通信套接字上进行读写操作,此时不能再接收其他客户端连接请求,只能等待同当前连接的客户端的操作执行完成,不过可以通过多线程来支持多个客户端的连接。可以通过线程池机制改善,线程池还可以让线程的创建和回收成本相对较低。
      • 伪异步 IO
        • 为了解决同步阻塞 I/O 面临的一个链路需要一个线程处理的问题,后来有人对它的线程模型进行了优化。
        • 后端通过一个线程池来处理多个客户端的请求接入,形成客户端个数 M : 线程池最大线程数 N 的比例关系,其中 M 可以远远大于 N。通过线程池可以灵活地调配线程资源,设置线程的最大值,防止由于海量并发接入导致线程耗尽。
        • Java_伪异步IO模型图
      • 总结
        • 在活动连接数不是特别高(小于单机 1000)的情况下,这种模型是比较不错的,可以让每一个连接专注于自己的 I/O 并且编程模型简单,也不用过多考虑系统的过载、限流等问题。线程池本身就是一个天然的漏斗,可以缓冲一些系统处理不了的连接或请求。但是,当面对十万甚至百万级连接的时候,传统的 BIO 模型是无能为力的。因此,我们需要一种更高效的 I/O 处理模型来应对更高的并发量。
    • NIO
      • NIO 是一种同步非阻塞的 I/O 模型,在 Java 1.4 中引入了 NIO 框架,对应 java.nio 包,提供了 Channel、Selector、Buffer 等抽象。它支持面向缓冲的,基于通道的 I/O 操作方法。
      • JDK 的 NIO 底层由 epoll 实现。
      • NIO 提供了与传统 BIO 模型中的 Socket 和 ServerSocket 相对应的 SocketChannel 和 ServerSocketChannel 两种不同的套接字通道实现,两种通道都支持阻塞和非阻塞两种模式。阻塞模式使用就像传统中的支持一样,比较简单,但是性能和可靠性都不好;非阻塞模式正好与之相反。对于低负载、低并发的应用程序,可以使用同步阻塞 I/O 来提升开发速率和更好的维护性;对于高负载、高并发的(网络)应用,应使用 NIO 的非阻塞模式来开发。
      • 核心组件
        • Buffer
          • 在 NIO 厍中,所有数据都是用缓冲区处理的。在读取数据时,它是直接读到缓冲区中的;在写入数据时,写入到缓冲区中。任何时候访问NIO中的数据,都是通过缓冲区进行操作。
          • 最常用的缓冲区是 ByteBuffer,一个 ByteBuffer 提供了一组功能用于操作 byte 数组。除了 ByteBuffer,还有其他的一些缓冲区,事实上,每一种 Java 基本类型(除了 Boolean 类型)都对应有一种缓冲区。
        • Channel
          • NIO 通过 Channel(通道)进行读写。
          • 通道是双向的,可读也可写,而流的读写是单向的。无论读写,通道只能和 Buffer 交互。因为 Buffer,通道可以异步地读写。
        • Selectors
          • 选择器用于使用单个线程处理多个通道。
          • Java_NIO_Selectors
      • NIO 读数据和写数据方式
        • 从通道进行数据读取:创建一个缓冲区,然后请求通道读取数据。
        • 从通道进行数据写入:创建一个缓冲区,填充数据,并要求通道写入数据。
    • AIO(Asynchronous I/O)
      • AIO 也就是 NIO 2。在 Java 7 中引入了 NIO 的改进版 NIO 2,它是异步非阻塞的 IO 模型。异步 IO 是基于事件和回调机制实现的,也就是应用操作之后会直接返回,不会堵塞在那里,当后台处理完成,操作系统会通知相应的线程进行后续的操作。
      • AIO 是异步 IO 的缩写,虽然 NIO 在网络操作中,提供了非阻塞的方法,但是 NIO 的 IO 行为还是同步的。对于 NIO 来说,我们的业务线程是在 IO 操作准备好时,得到通知,接着就由这个线程自行进行 IO 操作,IO 操作本身是同步的。

多线程

  • 并发编程 3 大重要特征
    • 原子性
      • 一个操作或者多个操作,要么全部执行成功,要么全部执行失败。满足原子性的操作,中途不可被中断。
    • 可见性
      • 多个线程共同访问共享变量时,某个线程修改了此变量,其他线程能立即看到修改后的值。
    • 有序性
      • 程序执行的顺序按照代码的先后顺序执行。(由于 JMM 模型中允许编译器和处理器为了效率,进行指令重排序的优化。指令重排序在单线程内表现为串行语义,在多线程中会表现为无序。那么多线程并发编程中,就要考虑如何在多线程环境下可以允许部分指令重排,又要保证有序性)
    • 概念
      • 公平锁和非公平锁
        • 公平锁
          • 多个线程按照申请锁的顺序去获得锁,线程会直接进入队列去排队,永远都是队列的第一位才能得到锁。
          • 优点:所有的线程都能得到资源,不会饿死在队列中
          • 缺点:吞吐量会下降很多,队列里面除了第一个线程,其他的线程都会阻塞,cpu唤醒阻塞线程的开销会很大。
        • 非公平锁
          • 多个线程去获取锁的时候,会直接去尝试获取,获取不到,再去进入等待队列,如果能获取到,就直接获取到锁。
          • 优点:可以减少 CPU 唤醒线程的开销,整体的吞吐效率会高点,CPU 也不必取唤醒所有线程,会减少唤起线程的数量。
          • 缺点:你们可能也发现了,这样可能导致队列中间的线程一直获取不到锁或者长时间获取不到锁,导致饿死。
    • synchronized
      • synchronized 是一种独占式的重量级锁,在运行到同步方法或者同步代码块的时候,让程序的运行级别由用户态切换到内核态,把所有的线程挂起,通过操作系统的指令,去调度线程。这样会频繁出现程序运行状态的切换,线程的挂起和唤醒,会消耗系统资源,为了提高效率,引入了偏向锁、轻量级锁、尽量让多线程访问公共资源的时候,不进行程序运行状态的切换。
      • 非公平锁
      • 特性
        • 可重入性
          • synchronized 锁对象的时候有个计数器,他会记录下线程获取锁的次数,在执行完对应的代码块之后,计数器就会 -1,直到计数器清零,就释放锁了。
            • 那可重入有什么好处呢?
              • 可以避免一些死锁的情况,也可以让我们更好封装我们的代码。
        • 不可中断性
          • 不可中断就是指,一个线程获取锁之后,另外一个线程处于阻塞或者等待状态,前一个不释放,后一个也一直会阻塞或者等待,不可以被中断。
      • 对象监视器(Monitor)
        • 在 HotSpot JVM 实现中,锁有个专门的名字:对象监视器。
        • 任何一个对象都有一个 Monitor 与之关联,当且一个 Monitor 被持有后,它将处于锁定状态。
        • 监视器锁(Monitor)本质是依赖于底层的操作系统的 Mutex Lock(互斥锁)来实现的。每个对象都对应于一个可称为“互斥锁”的标记,这个标记用来保证在任一时刻,只能有一个线程访问该对象。
        • synchronized 在 JVM 里的实现都是基于进入和退出 Monitor 对象来实现方法同步和代码块同步,虽然具体实现细节不一样,但是都可以通过成对的 MonitorEnter 和 MonitorExit 指令来实现。
          • MonitorEnter 指令:插入在同步代码块的开始位置,当代码执行到该指令时,将会尝试获取该对象 Monitor 的所有权,即尝试获得该对象的锁;
          • MonitorExit 指令:插入在方法结束处和异常处,JVM 保证每个 MonitorEnter 必须有对应的 MonitorExit;
        • Monitor 对象存在于每个 Java 对象的对象头 Mark Word 中(存储的指针的指向)
        • 当多个线程同时请求某个对象监视器时,对象监视器会设置几种状态用来区分请求的线程:
          • Contention List:所有请求锁的线程将被首先放置到该竞争队列
            • ContentionList 并不是一个真正的 Queue,而只是一个虚拟队列,原因在于 ContentionList 是由 Node 及其 next 指针逻辑构成,并不存在一个 Queue 的数据结构。
            • ContentionList 是一个 后进先出(LIFO) 【注:按上下文来看应该是先进先出(FIFO)】的队列,每次新加入 Node 时都会在队头进行,通过 CAS 改变第一个节点的的指针为新增节点,同时设置新增节点的 next 指向后续节点,而取得操作则发生在队尾。显然,该结构其实是个 Lock-Free 的队列。
            • 因为只有 Owner 线程才能从队尾取元素,也即线程出列操作无争用,当然也就避免了 CAS 的 ABA 问题。
            • Java_ContentionList
          • Entry List:Contention List 中那些有资格成为候选人的线程被移到 Entry List
            • EntryList 与 ContentionList 逻辑上同属等待队列,ContentionList 会被线程并发访问,为了降低对 ContentionList 队尾的争用,而建立 EntryList。
            • Owner 线程在 unlock 时会从 ContentionList 中迁移线程到 EntryList,并会指定 EntryList 中的某个线程(一般为 Head)为 Ready(OnDeck)线程。Owner 线程并不是把锁传递给 OnDeck 线程,只是把竞争锁的权利交给 OnDeck,OnDeck 线程需要重新竞争锁。这样做虽然牺牲了一定的公平性,但极大的提高了整体吞吐量,在 Hotspot 中把 OnDeck 的选择行为称之为“竞争切换”。
            • OnDeck 线程获得锁后即变为 owner 线程,无法获得锁则会依然留在 EntryList 中,考虑到公平性,在 EntryList 中的位置不发生变化(依然在队头)。如果 Owner 线程被 wait 方法阻塞,则转移到 WaitSet 队列;如果在某个时刻被 notify/notifyAll 唤醒,则再次转移到 EntryList。
          • Wait Set:那些调用 wait 方法被阻塞的线程被放置到 Wait Set
          • OnDeck:任何时刻最多只能有一个线程正在竞争锁,该线程称为 OnDeck
          • Owner:获得锁的线程称为 Owner
          • !Owner:释放锁的线程
        • 状态转换
          • Java_对象监视器_状态转换关系
      • 原理
        • 对象头,他会关联到一个 monitor 对象。
        • 当我们进入一个人方法的时候,执行 monitorenter,就会获取当前对象的一个所有权,这个时候 monitor 进入数为 1,当前的这个线程就是这个 monitor 的 owner。
        • 如果你已经是这个 monitor 的 owner 了,你再次进入,就会把进入数 +1。
          • 如果线程调用 wait 方法,将释放锁,当前线程置为 null,计数器 -1,同时进入 waitSet 等待被唤醒,调用 notify 或者 notifyAll 之后又会进入 entryList 竞争锁。
        • 同理,当他执行完 monitorexit,对应的进入数就 -1,直到为 0,才可以被其他线程持有。
        • Java_synchronized_执行流程
      • 自旋锁
        • 出现自旋锁的原因
          • 那些处于 ContetionList、EntryList、WaitSet 中的线程均处于阻塞状态,阻塞操作由操作系统完成(在 Linxu 下通过 pthread_mutex_lock 函数)。线程被阻塞后便进入内核(Linux)调度状态,这个会导致系统在用户态与内核态之间来回切换,严重影响锁的性能。
        • 原理
          • 当发生争用时,若 Owner 线程能在很短的时间内释放锁,则那些正在争用线程可以稍微等一等(自旋),在 Owner 线程释放锁后,争用线程可能会立即得到锁,从而避免了系统阻塞。但 Owner 运行的时间可能会超出了临界值,争用线程自旋一段时间后还是无法获得锁,这时争用线程则会停止自旋进入阻塞状态(后退)。基本思路就是自旋,不成功再阻塞,尽量降低阻塞的可能性,这对那些执行时间很短的代码块来说有非常重要的性能提高。自旋锁有个更贴切的名字:自旋-指数后退锁,也即复合锁。很显然,自旋在多处理器上才有意义。
        • 相关问题
          • 线程自旋时做些啥?
            • 其实啥都不做,可以执行几次 for 循环,可以执行几条空的汇编指令,目的是占着 CPU 不放,等待获取锁的机会。所以说,自旋是把双刃剑,如果旋的时间过长会影响整体性能,时间过短又达不到延迟阻塞的目的。显然,自旋的周期选择显得非常重要,但这与操作系统、硬件体系、系统的负载等诸多场景相关,很难选择,如果选择不当,不但性能得不到提高,可能还会下降,因此大家普遍认为自旋锁不具有扩展性。
          • synchronized 实现何时使用了自旋锁?
            • 在线程进入 ContentionList 时,也即第一步操作前。线程在进入等待队列时首先进行自旋尝试获得锁,如果不成功再进入等待队列。这对那些已经在等待队列中的线程来说,稍微显得不公平。还有一个不公平的地方是自旋线程可能会抢占了 Ready 线程的锁。自旋锁由每个监视对象维护,每个监视对象一个。
        • 适应性自旋锁
          • JDK 1.6 引入了更加聪明的自旋锁,即自适应自旋锁。所谓自适应就意味着自旋的次数不再是固定的,它是由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定。
          • 如何进行适应性自旋呢?
            • 线程如果自旋成功了,那么下次自旋的次数会更加多,因为虚拟机认为既然上次成功了,那么此次自旋也很有可能会再次成功,那么它就会允许自旋等待持续的次数更多。反之,如果对于某个锁,很少有自旋能够成功,那么在以后要或者这个锁的时候自旋的次数会减少甚至省略掉自旋过程,以免浪费处理器资源。
      • 锁消除
        • 锁消除是指虚拟机即时编译器在运行时,对一些代码上要求同步,但是被检测到不可能存在共享数据竞争的锁进行消除。锁消除的主要判定依据来源于逃逸分析的数据支持,如果判断在一段代码中,堆上的所有数据都不会逃逸出去从而被其他线程访问到,那就可以把它们当做栈上数据对待,认为它们是线程私有的,同步加锁自然就无须进行。
        • 例子
          • 变量是否逃逸,对于虚拟机来说需要使用数据流分析来确定,但是程序员自己所该是很清楚的,怎么会在明知道不存在数据争用的情况下要求同步呢?答案是有许多同步措施并不是程序员自己加入的,同步的代码在 Java 程序中的普遍程度也许超过了大部分读者的想象。我们来看看下面代码中的例子,这段非常简单的代码仅仅是输出 3 个字符串相加的结果,无论是源码字面上还是程序语义上都没有同步。
          • Java_synchronized_锁消除_1
          • 我们也知道,由于 String 是一个不可变的类,对字符串的连接操作总是通过生成新的 String 对象来进行的,因此 Javac 编译器会对 String 连接做自动优化。在 JDK 1.5 之前,会转化为 StringBuffer 对象的连续 append() 操作,在 JDK 1.5及以后的版本中,会转化为 StringBuilder 对象的连续 append() 操作,上述代码可能会变成下面的样子。
          • Java_synchronized_锁消除_2
          • 每个 StringBuffer.append() 方法中都有一个同步块,锁就是 sb 对象。虚拟机观察变量 sb,很快就会发现它的动态作用域被限制在 concatString() 方法内部。也就是说,sb 的所有引用永远不会 “逃逸” 到 concatString() 方法之外,其他线程无法访问到它,因此,虽然这里有锁,但是可以被安全地消除掉,在即时编译之后,这段代码就会忽略掉所有的同步而直接执行了。
      • 锁粗化
        • 原则上,我们在编写代码的时候,总是推荐将同步块的作用范围限制得尽量小,只在共享数据的实际作用域中才进行同步,这样是为了使得需要同步的操作数量尽可能变小,如果存在锁竞争,那等待锁的线程也能尽快拿到锁。
        • 大部分情况下,上面的原则都是正确的,但是如果一系列的连续操作都对同一个对象反复加锁和解锁,甚至加锁操作是出现在循环体中的,那即使没有线程竞争,频繁地进行互斥同步操作也会导致不必要的性能损耗。
        • 例子
          • Java_synchronized_锁粗化
          • 上述代码中连续的 append() 方法就属于这类情况。如果虚拟机探测到有这样一串零碎的操作都对同一个对象加锁,将会把加锁同步的范围扩展(粗化)到整个操作序列的外部,以上述代码为例,就是扩展到 append() 操作外部,也就是把 while 循环加锁,这样只需要加锁一次就可以了。
      • 锁升级
        • 从 JDK1.6 版本之后,synchronized 本身也在不断优化锁的机制,有些情况下他并不会是一个很重量级的锁了。优化机制包括自适应锁、自旋锁、锁消除、锁粗化、轻量级锁和偏向锁。
        • 无锁——>偏向锁——>轻量级锁——>重量级锁,膨胀方向不可逆。
          • 偏向锁
            • 对象头是由 Mark Word 和 Klass pointer 组成,锁争夺也就是对象头指向的 Monitor 对象的争夺,一旦有线程持有了这个对象,标志位修改为 1,就进入偏向模式,同时会把这个线程的 ID 记录在对象的 Mark Word 中。
            • 这个过程是采用了 CAS 乐观锁操作的,每次同一线程进入,虚拟机就不进行任何同步的操作了,对标志位 +1 就好了,不同线程过来,CAS 会失败,也就意味着获取锁失败。
            • 偏向锁在 1.6 之后是默认开启的,1.5 中是关闭的,需要手动开启参数是 xx:-UseBiasedLocking=false
            • Java_synchronized原理_偏向锁
          • 轻量级锁
            • 如果这个对象是无锁的,JVM 就会在当前线程的栈帧中建立一个叫锁记录(Lock Record)的空间,用来存储锁对象的 Mark Word 拷贝,然后把 Lock Record 中的 owner 指向当前对象。
            • JVM 接下来会利用 CAS 尝试把对象原本的 Mark Word 更新为 Lock Record 的指针,成功就说明加锁成功,改变锁标志位,执行相关同步操作。
            • 如果失败了,就会判断当前对象的 Mark Word 是否指向了当前线程的栈帧,是则表示当前的线程已经持有了这个对象的锁,否则说明被其他线程持有了,继续锁升级,修改锁的状态,之后等待的线程也阻塞。
            • Java_synchronized原理_轻量级锁
            • 轻量级锁认为竞争存在,但是竞争的程度很轻,一般两个线程对于同一个锁的操作都会错开,或者说稍微等待一下(自旋),另一个线程就会释放锁。 但是当自旋超过一定的次数,或者一个线程在持有锁,一个在自旋,又有第三个来访时,轻量级锁膨胀为重量级锁,重量级锁使除了拥有锁的线程以外的线程都阻塞,防止 CPU 空转。
          • 重量级锁
            • 就是让争抢锁的线程从用户态转换成内核态。让 CPU 借助操作系统进行线程协调。
        • 流程
          1. 检查 MarkWord 里面是不是放的自己的 ThreadId,如果是,表示当前线程是处于“偏向锁”。跳过轻量级锁直接执行同步体。
          2. 如果 MarkWord 不是自己的 ThreadId,锁升级,这时候,用 CAS 来执行切换,新的线程根据 MarkWord 里面现有的 ThreadId,通知之前线程暂停,之前线程将 Markword 的内容置为空。
          3. 两个线程都把对象的 HashCode 复制到自己新建的用于存储锁的记录空间,接着开始通过 CAS 操作,把共享对象的 MarKWord 的内容修改为自己新建的记录空间的地址的方式竞争 MarkWord.
          4. 第三步中成功执行 CAS 的获得资源,失败的则进入自旋.
          5. 自旋的线程在自旋过程中,成功获得资源(即之前获的资源的线程执行完成并释放了共享资源),则整个状态依然处于轻量级锁的状态,如果自旋失败
          6. 进入重量级锁的状态,这个时候,自旋的线程进行阻塞,等待之前线程执行完成并唤醒自己.
        • Java_synchronized原理
        • Java_synchronized原理_锁升级
        • Java_synchronized原理_锁升级简略版
      • 同步代码块和同步方法
        • 同步方法就是在方法前加关键字 synchronized;同步代码块则是在方法内部使用 synchronized
        • 加锁对象相同的话,同步方法锁的范围大于等于同步方法块。一般加锁范围越大,性能越差
        • 同步方法如果是 static 方法,等同于同步方法块加锁在该 Class 对象上
      • 相关命令
        • wait
        • notify
    • ReentrantLock
      • 基于 AQS 而形成了一个“可重入锁”
        • AQS:AbstractQueuedSynchronizer 的缩写
          • Java_AQS流程图
          • AQS 是 JUC(java.util.concurrent)的核心,而 CLH 锁又是 AQS 的基础
            • CLH 锁
              • 原理
                • 首先有一个尾节点指针,通过这个尾结点指针来构建等待线程的逻辑队列,因此能确保线程线程先到先服务的公平性,因此尾指针可以说是构建逻辑队列的桥梁;此外这个尾节点指针是原子引用类型,避免了多线程并发操作的线程安全性问题;
                • 通过等待锁的每个线程在自己的某个变量上自旋等待,这个变量将由前一个线程写入。由于某个线程获取锁操作时总是通过尾节点指针获取到前一线程写入的变量,而尾节点指针又是原子引用类型,因此确保了这个变量获取出来总是线程安全的。
                • Java_CLH锁
        • 可重入:同一个线程对于已经获得到的锁,可以多次继续申请到该锁的使用权
      • ReentrantLock 实现了 Lock 接口,操作其成员变量 sync(AQS 的子类),来完成锁的相关功能。
        • sync 有 2 种形态:NonfairSync 和 FairSync。
          • FairSync
            • 在 tryAquire 方法中,当判断到锁状态字段 state == 0 时,不会立马将当前线程设置为该锁的占用线程,而是去判断是在此线程之前是否有其他线程在等待这个锁(执行 hasQueuedPredecessors() 方法),如果是的话,则该线程会加入到等待队列中,进行排队(FIFO,先进先出的排队形式)。
            • Java_ReetrantLock_FairSync
          • NoFairSync
            • 在 tryAquire 方法中,没有判断是否有在此之前的排队线程,而是直接进行获锁操作,因此多个线程之间同时争用一把锁的时候,谁先获取到就变得随机了,很有可能线程 A 比线程 B 更早等待这把锁,但是B却获取到了锁,A 继续等待。
            • Java_RettrantLock_NoFairSync
      • Node
        • Node 结点是对每一个访问同步代码的线程的封装
        • 其包含了需要同步的线程本身以及线程的状态,如是否被阻塞,是否等待唤醒,是否已经被取消等。每个 Node 结点内部关联其前继结点 prev 和后继结点 next,这样可以方便线程释放锁后快速唤醒下一个在等待的线程。
        • 结构
          • waitStatus
            • 表示当前被封装成 Node 结点的等待状态
              • CANCELLED
                • 值为 1,在同步队列中等待的线程等待超时或被中断,需要从同步队列中取消该 Node 的结点,其结点的 waitStatus 为 CANCELLED,即结束状态,进入该状态后的结点将不会再变化。
              • SIGNAL
                • 值为 -1,被标识为该等待唤醒状态的后继结点,当其前继结点的线程释放了同步锁或被取消,将会通知该后继结点的线程执行。说白了,就是处于唤醒状态,只要前继结点释放锁,就会通知标识为 SIGNAL 状态的后继结点的线程执行。
              • CONDITION
                • 值为 -2,与 Condition 相关,该标识的结点处于等待队列中,结点的线程等待在 Condition 上,当其他线程调用了 Condition 的 signal() 方法后,CONDITION 状态的结点将从等待队列转移到同步队列中,等待获取同步锁。
              • PROPAGATE
                • 值为 -3,与共享模式相关,在共享模式中,该状态标识结点的线程处于可运行状态。
              • 0 状态
                • 值为0,代表初始化状态。
      • Condition
        • Condition 的具体实现类是 AQS 的内部类 ConditionObject。
        • 每个 Condition 都对应着一个等待队列,也就是说如果一个锁上创建了多个 Condition 对象,那么也就存在多个等待队列。等待队列是一个 FIFO 的队列,在队列中每一个节点都包含了一个线程的引用,而该线程就是 Condition 对象上等待的线程。当一个线程调用了 await() 相关的方法,那么该线程将会释放锁,并构建一个 Node 节点封装当前线程的相关信息加入到等待队列中进行等待,直到被唤醒、中断、超时才从队列中移出。
        • Condition 结构
          • Java_ReentrantLock_Condition结构
          • 等待队列中结点的状态只有两种即 CANCELLED 和 CONDITION
      • 相关问题
        • 线程是什么时候排队的?
          • 在获锁的时候,无法成功获取到该锁,然后进行排队等待。
        • 线程是如何排队的?
          • Java_ReentrantLock_加锁
          • 想要知道如何排队,那也就是去理解 addWaiter(Node.EXCLUSIVE) 这个方法具体是如何实现的。
          • 流程
            1. 初始状态(也就是锁未被任何线程占用的时候)线程 A 申请锁。此时,成功获取到锁,无排队线程。
            2. 线程 B 申请该锁,且上一个线程未释放。
              • Java_ReetrantLock_排队_1
              • 这里需要关注的是 Head 节点,这个节点是一个空的 Node 节点,不存储任何线程相关的信息
            3. 线程 C 申请该锁,且占有该锁的线程未释放
              • Java_ReetrantLock_排队_2
            4. 线程 D 申请该锁,且占有该锁的线程未释放
              • Java_ReetrantLock_排队_3
        • 等待中的线程如何感知到锁空闲并获得锁?
          • acquireQueued(addWaiter(Node.EXCLUSIVE), arg) 中的 addWaiter(Node.EXCLUSIVE) 方法是对获锁失败的线程放入到队列中排队等待,而该方法的外层方法 acquireQueued() 就是对已经排队中的线程进行“获锁”操作。
          • 就是一个线程获取锁失败了,被放到了线程等待队列中,而 acquireQueued 方法就是把放入队列中的这个线程不断进行“获锁”,直到它“成功获锁”或者“不再需要锁(如被中断)”。
          • Java_ReetrantLock_获锁流程
            • 不管公平还是非公平模式下,ReentrantLock 对于排队中的线程都能保证,排在前面的一定比排在后面的线程优先获得锁。但是,非公平模式不保证队列中的第一个线程一定就比新来的(未加入到队列)的线程优先获锁。因为队列中的第一个线程尝试获得锁时,可能刚好来了一个线程也要获取锁,而这个刚来的线程都还未加入到等待队列,此时两个线程同时随机竞争,很有可能,队列中的第一个线程竞争失败(而该线程等待的时间其实比这个刚来的线程等待时间要久)。
            • 什么时候线程需要被阻塞呢?
              • Java_ReetrantLock_AQS判断线程是否应该被阻塞
              • while 循环中必须要这个 node 符合“它就是该队列中最早的 Node 并且获锁成功”才会跳出 while 循环体,如果不是,则会继续执行到“判断这个线程是否应该被阻塞”,此时。原本状态不是 SIGNAL 的线程,因为在上一次“判断这个线程是否应该被阻塞”这个方法时被设置成了 SIGNAL,那么第二次执行这个判断时,就会被成功阻塞。也就不会出现“空跑”的情况。
        • 那什么时候唤醒这些阻塞的线程呢?
          • Java_ReentrantLock_解锁
          • unparkSuccessor(h) 方法就是“唤醒操作”,主要流程如代码所示
            1. 尝试释放当前线程持有的锁
            2. 如果成功释放,那么去唤醒头结点的后继节点(因为头节点 head 是不保存线程信息的节点,仅仅是因为数据结构设计上的需要,在数据结构上,这种做法往往叫做“空头节点链表”。对应的就有“非空头结点链表”)
        • synchronized、ReentrantLock 的区别
          • Java_ReentrantLock与synchronized的区别
        • 非公平锁比公平锁高效的原因?
          • 因为线程切换的开销。如果一个线程在 running 期间直接抢占到锁资源,就不需要进行【恢复现场】操作,也就可以更快地执行业务代码。相反地,如果是一个就绪态的线程想要获得锁资源,首先需要恢复现场,之后争抢锁(可能成功也可能失败),此时就已经浪费了大量的 CPU,只有在获取锁成功后才能继续执行业务代码。
          • 非公平锁减少了线程挂起的几率,后来的线程有一定几率逃离被挂起的开销。
    • ReentrantReadWriteLock
      • 表示两个锁,一个是读操作相关的锁,称为共享锁;一个是写相关的锁,称为排他锁
      • 入锁条件:
        • 线程进入读锁的前提条件:
          • 没有其他线程的写锁
          • 没有写请求或者有写请求,但调用线程和持有锁的线程是同一个。
        • 线程进入写锁的前提条件:
          • 没有其他线程的读锁
          • 没有其他线程的写锁
      • 三个重要的特性:
        • 公平选择性:支持非公平(默认)和公平的锁获取方式,吞吐量还是非公平优于公平。
        • 重进入:读锁和写锁都支持线程重进入。
        • 锁降级:遵循获取写锁、获取读锁再释放写锁的次序,写锁能够降级成为读锁。
      • 结构
        • Java_Lock继承结构
      • 原理
        • 同步状态在重入锁的实现中是表示被同一个线程重复获取的次数,即一个整形变量来维护,但是之前的那个表示仅仅表示是否锁定,而不用区分是读锁还是写锁。而读写锁需要在同步状态(一个整形变量)上维护多个读线程和一个写线程的状态。
        • 读写锁对于同步状态的实现是在一个整形变量上通过“按位切割使用”:将变量切割成两部分,高 16 位表示读,低 16 位表示写。
          • Java_读写锁同步状态
      • 读锁
        • 加锁过程
          • Java_读锁竞争过程
          • 读锁的获取条件要满足:
            1. 当前的写锁未被占有(AQS state 变量低 16 位为 0)或者当前线程是写锁占有的线程
            2. readerShouldBlock() 方法返回 false
            3. 当前读锁占有量小于最大值(2^16 -1)
            4. 成功通过 CAS 操作将读锁占有量 +1(AQS 的 state 高 16 位同步加 1)
        • 释放过程
          • Java_读锁释放过程
      • 写锁
        • 加锁过程
          • Java_写锁竞争过程
          • 写锁获取的条件需要满足:
            1. 读锁未被占用(AQS state 高 16 位为 0) ,写锁未被占用(state 低 16 位为 0)或者占用写锁的线程是当前线程
            2. writerShouldBlock()方法返回 false,即不阻塞写线程
            3. 当前写锁占有量小于最大值(2^16 -1),否则抛出Error(“Maximum lock count exceeded”)
            4. 通过 CAS 竞争将写锁状态 +1(将 state 低 16 位同步 +1)
        • 释放过程
          • Java_写锁释放过程
    • StampedLock
      • StampedLock 类,在 JDK1.8 时引入,是对读写锁 ReentrantReadWriteLock 的增强,该类提供了一些功能,优化了读锁、写锁的访问,同时使读写锁之间可以互相转换,更细粒度控制并发。
      • StampedLock 是不可重入锁。
      • 主要特点
        • 所有获取锁的方法,都返回一个邮戳(Stamp),Stamp 为 0 表示获取失败,其余都表示成功;
        • 所有释放锁的方法,都需要一个邮戳(Stamp),这个 Stamp 必须是和成功获取锁时得到的 Stamp 一致;
        • StampedLock 是不可重入的;(如果一个线程已经持有了写锁,再去获取写锁的话就会造成死锁)
        • StampedLock 支持读锁和写锁的相互转换
          • 在 RRW 中,当线程获取到写锁后,可以降级为读锁,但是读锁是不能直接升级为写锁的。
          • StampedLock 提供了读锁和写锁相互转换的功能,使得该类支持更多的应用场景。
        • 无论写锁还是读锁,都不支持 Conditon 等待
        • StampedLock 相比 ReentrantReadWriteLock,对多核 CPU 进行了优化。当 CPU 核数超过 1 时,会有一些自旋操作
      • StampedLock 有三种访问模式:
        • Reading(读模式):功能和 ReentrantReadWriteLock 的读锁类似
        • Writing(写模式):功能和 ReentrantReadWriteLock 的写锁类似
        • Optimistic reading(乐观读模式):这是一种优化的读模式
          • 读的时候不加读锁,读出来发现数据被修改了,再升级为“悲观读”;即读错了再严格读一次,避免写线程被饿死。乐观读不能保证读取到的数据是最新的,所以将数据读取到局部变量的时候需要通过 lock.validate(stamp) 校验是否被写线程修改过,若是修改过则需要上悲观读锁,再重新读取数据到局部变量。
            • stamp 类似 version
      • 原理
        • StampedLock 虽然不像其它锁一样定义了内部类来实现 AQS 框架,但是 StampedLock 的基本实现思路还是利用 CLH 队列进行线程的管理,通过同步状态值来表示锁的状态和类型。
        • Java_StampedLock_CLH队列
      • 相关问题
        • 为什么有了 ReentrantReadWriteLock,还要引入 StampedLock?
          • ReentrantReadWriteLock 使得多个读线程同时持有读锁(只要写锁未被占用),而写锁是独占的。
          • 但是,读写锁如果使用不当,很容易产生“饥饿”问题。
            • 例如
              • 比如在读线程非常多,写线程很少的情况下,很容易导致写线程“饥饿”,虽然使用“公平”策略可以一定程度上缓解这个问题,但是“公平”策略是以牺牲系统吞吐量为代价的。
                • 线程饥饿
                  • 大量读多写少的场景,读线程连续抢占导致等待的写线程无法执行。
    • LockSupport
      • 底层实现原理
        • 在 Linux 系统下,是用的 Posix 线程库 pthread 中的 mutex(互斥量),condition(条件变量)来实现的。
        • mutex 和 condition 保护了一个 _counter 的变量,当 park 时,这个变量被设置为 0,当 unpark 时,这个变量被设置为 1。
      • LockSupport可以在任何场合使线程阻塞,同时也可以指定要唤醒的线程
        • 使用 wait、notify 来实现等待唤醒功能至少有两个缺点:
          1. 在调用这两个方法前必须先获得锁对象,这限制了其使用场合:只能在同步代码块中。
          2. 当对象的等待队列中有多个线程时,notify 只能随机选择一个线程唤醒,无法唤醒指定的线程。
      • 常用方法
        • LockSupport.park()
          • 用来阻塞当前线程
          • 当调用 park() 方法时,会将 _counter 置为 0,同时判断设置前值,等于 1 说明前面被 unpark 过,则直接退出,否则将使该线程阻塞。
        • LockSupport.park(Object blocker)
          • 指定线程阻塞的对象 blocker,该对象主要用来排查问题
        • LockSupport.unpark(Thread thread)
          • 用来唤醒线程,因为需要线程作参数,所以可以指定线程进行唤醒
          • 当调用 unpark() 方法时,会将 _counter 置为 1,同时判断设置前值,小于 1 会进行线程唤醒,否则直接退出。
      • 相关问题
        • 为什么可以先唤醒线程后阻塞线程?
          • 因为 unpark 获得了一个凭证,之后调用 park 因为有凭证消费,故不会阻塞。
        • 为什么唤醒两次后阻塞两次会阻塞线程?
          • 因为凭证的数量最多为 1,连续调用两次 unpark 和调用一次 unpark 效果一样,只会增加一个凭证;而调用两次 park 却需要消费两个凭证。
  • ThreadLocal
    • ThreadLocal 的作用
      • 作用主要是做数据隔离,填充的数据只属于当前线程,变量的数据对别的线程而言是相对隔离的,在多线程环境下,如何防止自己的变量被其它线程篡改。
        • 隔离有什么用,会用在什么场景么?
          • Spring 实现事务隔离级别
            • Spring 采用 Threadlocal 的方式,来保证单个线程中的数据库操作使用的是同一个数据库连接,同时,采用这种方式可以使业务层使用事务时不需要感知并管理 connection 对象,通过传播级别,巧妙地管理多个事务配置之间的切换,挂起和恢复。
            • Spring 框架里面就是用的 ThreadLocal 来实现这种隔离,主要是在T ransactionSynchronizationManager 这个类里面
            • Spring 的事务主要是 ThreadLocal 和 AOP 去做实现的
          • 很多场景的 cookie,session 等数据隔离都是通过 ThreadLocal 去做实现的。
    • 常用于以下这个场景
      • 多线程环境下存在对非线程安全对象的并发访问,而且该对象不需要在线程间共享,但是我们不想加锁,这时候可以使用 ThreadLocal 来使得每个线程都持有一个该对象的副本。
    • 原理
      • 每个 Thread 线程内部都有一个静态的 ThreadLocalMap。Map 里面存储线程本地对象 ThreadLocal(key)和线程的变量副本(value)。
      • Thread 内部的 Map 是由 ThreadLocal 维护,ThreadLocal 负责向 map 获取和设置线程的变量值。
      • 一个 Thread 可以有多个 ThreadLocal。
      • Java_多线程_ThreadLocal结构
      • Java_ThreadLocal_ThreadLocalMap结构
        • Entry 是继承 WeakReference(弱引用)的,只用了数组没有用链表。
          • 为什么需要数组呢?没有了链表怎么解决 Hash 冲突呢?
            • 用数组是因为,我们开发过程中可以一个线程可以有多个 ThreadLocal 来存放不同类型的对象的,但是他们都将放到你当前线程的 ThreadLocalMap 里,所以肯定要数组来存。
            • ThreadLocalMap 在存储的时候会给每一个 ThreadLocal 对象一个 threadLocalHashCode,在插入过程中,根据 ThreadLocal 对象的 hash 值,定位到 table 中的位置 i,int i = key.threadLocalHashCode & (len-1)
              • 然后会判断一下:如果当前位置是空的,就初始化一个 Entry 对象放在位置 i 上;
              • 如果位置 i 不为空,如果这个 Entry 对象的 key 正好是即将设置的 key,那么就刷新 Entry 中的 value;
              • 如果位置 i 的不为空,而且 key 不等于 entry,那就找下一个空位置,直到为空为止。
            • Java_ThreadLocal_新增数据
            • 在 get 的时候,也会根据 ThreadLocal 对象的 hash 值,定位到 table 中的位置,然后判断该位置 Entry 对象中的 key 是否和 get 的 key 一致,如果不一致,就判断下一个位置,set 和 get 如果冲突严重的话,效率还是很低的。
    • ThreadLocal 的问题
      • 内存泄露
        • ThreadLocal 在保存的时候会把自己当做 Key 存在 ThreadLocalMap 中,正常情况应该是 key 和 value 都应该被外界强引用才对,但是现在 key 被设计成 WeakReference 弱引用了。
        • 这就导致了一个问题,ThreadLocal 在没有外部强引用时,发生 GC 时会被回收,如果创建 ThreadLocal 的线程一直持续运行,那么这个 Entry 对象中的 value 就有可能一直得不到回收,发生内存泄露。
        • 就比如线程池里面的线程,线程都是复用的,那么之前的线程实例处理完之后,出于复用的目的线程依然存活,所以,ThreadLocal 设定的 value 值被持有,导致内存泄露。
        • 按照道理一个线程使用完,ThreadLocalMap 是应该要被清空的,但是现在线程被复用了。
          • 那怎么解决?
            • 在代码的最后使用 remove 就好了,我们只要记得在使用的最后用 remove 把值清空就好了。
    • 相关问题
      • 如果我想共享线程的 ThreadLocal 数据怎么办?
        • 使用 InheritableThreadLocal 可以实现多个线程访问 ThreadLocal 的值,我们在主线程中创建一个 InheritableThreadLocal 的实例,然后在子线程中得到这个 InheritableThreadLocal 实例设置的值。
        • 怎么传递的呀?
          • Java_ThreadLocal_InheritableThreadLocal
          • ```
            public class Thread implements Runnable {
            ……
            if (inheritThreadLocals && parent.inheritableThreadLocals != null)
              this.inheritableThreadLocals=ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);
            
            ……
            }
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
            43
            44
            45
            46
            47
            48
            49
            50
            51
            52
            53
            54
            55
            56
            57
            58
            59
            60
            61
            62
            63
            64
            65
            66
            67
            68
            69
            70
            71
            72
            73
            74
            75
            76
            77
            78
            79
            80
            81
            82
            83
            84
            85
            86
            87
            88
            89
            90
            91
            92
            93
            94
            95
            96
            97
            98
            99
            100
            101
            102
            103
            104
            105
            106
            107
            108
            109
            110
            111
            112
            113
            114
            115
            116
            117
            118
            119
            120
            121
            122
            123
            124
            125
            126
            127
            128
            129
            130
            131
            132
            133
            134
            135
            136
            137
            138
            139
            140
            141
            142
            143
            144
            145
            146
            147
            148
            149
            150
            151
            152
            153
            154
            155
            156
            157
            158
            159
            160
            161
            162
            163
            164
            165
            166
            167
            168
            169
            170
            171
            172
            173
            174
            175
            176
            177
            178
            179
            180
            181
            182
            183
            184
            185
            186
            187
            188
            189
            190
            191
            192
            193
            194
            195
            196
            197
            198
            199
            200
            201
            202
            203
            204
            205
            206
            207
            208
            209
            210
            211
            212
            213
            214
            215
            216
            217
            218
            219
            220
            221
            222
            223
            224
            225
            226
            227
            228
            229
            230
            231
            232
            233
            234
            235
            236
            237
            238
            239
            240
            241
            242
            243
            244
            245
            246
            247
            248
            249
            250
            251
            252
            253
            254
            255
            256
            257
            258
            259
            260
            261
            262
            263
            264
            265
            266
            267
                    - 如果线程的 inheritThreadLocals 变量不为空,比如我们上面的例子,而且父线程的 inheritThreadLocals 也存在,那么我就把父线程的 inheritThreadLocals 给当前线程的 inheritThreadLocals。
            - **那为什么 ThreadLocalMap 的 key 要设计成弱引用?**
            - key 不设置成弱引用的话就会造成和 entry 中 value 一样内存泄漏的场景。
            - 多线程相关使用类
            - 原子操作相关类
            - AtomicReference
            - AtomicReference 是作用是对”对象”进行原子操作。提供了一种读和写都是原子性的对象引用变量。
            - FieldUpdater
            - 子类有:AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater
            - AtomicXXXFieldUpdater,就是可以以一种线程安全的方式操作非线程安全对象的某些字段
            - 可以在不修改用户代码(调用方)的情况下,就能实现并发安全性
            - ![Java_AtomicIntegerFieldUpdater_例子](Java-basic-0-知识点汇总/Java_AtomicIntegerFieldUpdater_例子.png)
            - AtomicReferenceFieldUpdater 的使用必须满足以下条件
            - AtomicReferenceFieldUpdater 只能修改对于它可见的字段,也就是说对于目标类的某个字段 field,如果修饰符是 private,但是 AtomicReferenceFieldUpdater 所在的使用类不能看到 field,那就会报错;
            - 目标类的操作字段,必须用 volatile 修饰;
            - 目标类的操作字段,不能是 static 的;
            - AtomicReferenceFieldUpdater 只适用于引用类型的字段;
            - 原理
            - 利用 Unsafe 进行 CAS 更新
            - LongAdder
            - JDK1.8 时,java.util.concurrent.atomic 包中提供了一个新的原子类:LongAdder。
            - 根据 Oracle 官方文档的介绍,LongAdder 在高并发的场景下会比它的前辈(AtomicLong)具有更好的性能,代价是消耗更多的内存空间
            - 原理
            - 内部是一个 Base + 一个 Cell 数组
            - base 变量:非竞争状态条件下,直接累加到该变量上
            - Cell数组:竞争条件下(高并发下),累加各个线程自己的槽 `Cell[i]` 中
            - add 方法
            - ![Java_LongAdder_add方法原理](Java-basic-0-知识点汇总/Java_LongAdder_add方法原理.png)
            - sum 方法
            - $\text { value }=\text { base }+\sum_{i=0}^{n} \operatorname{Cell}[i]$
            - 相关类
            - LongAccumulator
            - LongAccumulator 是 LongAdder 的增强版。LongAdder 只能针对数值的进行加减运算,而 LongAccumulator 提供了自定义的函数操作。
            - DoubleAdder
            - DoubleAccumulator
            - 相关问题
            - **为什么要引入 LongAdder?**
            - AtomicLong 是利用了底层的 CAS 操作来提供并发性的,比如 addAndGet 方法:
            - ![Java_AtomicLong_addAndGet](Java-basic-0-知识点汇总/Java_AtomicLong_addAndGet.png)
            - 上述方法调用了 Unsafe 类的 getAndAddLong 方法,该方法内部是个 native 方法,它的逻辑是采用自旋的方式不断更新目标值,直到更新成功。
            - 在并发量较低的环境下,线程冲突的概率比较小,自旋的次数不会很多。但是,高并发环境下,N 个线程同时进行自旋操作,会出现大量失败并不断自旋的情况,此时 AtomicLong 的自旋会成为瓶颈。
            - 这就是 LongAdder 引入的初衷-d解决高并发环境下 AtomicLong 的自旋瓶颈问题。
            - **LongAdder 快在哪里?**
            - AtomicLong 中有个内部变量 value 保存着实际的 long 值,所有的操作都是针对该变量进行。也就是说,高并发环境下,value 变量其实是一个热点,也就是 N 个线程竞争一个热点。
            - LongAdder 的基本思路就是分散热点,将 value 值拆分到一个数组中,不同线程会命中到数组的不同槽中,各个线程只对自己槽中的那个值进行 CAS 操作,这样热点就被分散了,冲突的概率就小很多。如果要获取真正的 long 值,只要将各个槽中的变量值累加返回。
            - 其他
            - Semaphore
            - Semaphore,又名信号量,这个类的作用有点类似于“许可证”。有时,我们因为一些原因需要控制同时访问共享资源的最大线程数量,比如出于系统性能的考虑需要限流,或者共享资源是稀缺资源,我们需要有一种办法能够协调各个线程,以保证合理的使用公共资源。
            - Semaphore 维护了一个许可集,其实就是一定数量的“许可证”。
            - 当有线程想要访问共享资源时,需要先获取(acquire)的许可;如果许可不够了,线程需要一直等待,直到许可可用。当线程使用完共享资源后,可以归还(release)许可,以供其它需要的线程使用。
            - Semaphore 其实就是实现了AQS共享功能的同步器
            - 注意:Semaphore 不是锁,只能限制同时访问资源的线程数,至于对数据一致性的控制,Semaphore 是不关心的。当前,如果是只有一个许可的 Semaphore,可以当作锁使用。
            - CyclicBarrier
            - CyclicBarrier 是一个辅助同步器类,在 JDK1.5 时随着 J.U.C 一起引入。
            - CyclicBarrier 可以认为是一个栅栏。让线程到达栅栏时被阻塞(调用await方法),直到到达栅栏的线程数满足指定数量要求时,栅栏才会打开放行。
            - ![Java_CyclicBarrier](Java-basic-0-知识点汇总/Java_CyclicBarrier.png)
            - CyclicBarrier 是可以循环复用的
            - CountDownLatch
            - CountDownLatch 是一个辅助同步器类,用来作计数使用,它的作用有点类似于生活中的倒数计数器,先设定一个计数初始值,当计数降到0时,将会触发一些事件,如火箭的倒数计时。
            - 用法
            - 初始计数值在构造 CountDownLatch 对象时传入,每调用一次 `countDown()` 方法,计数值就会减 1。
            - 线程可以调用 CountDownLatch 的 await 方法进入阻塞,当计数值降到 0 时,所有之前调用 await 阻塞的线程都会释放。
            - 注意:CountDownLatch 的初始计数值一旦降到 0,无法重置。如果需要重置,可以考虑使用 CyclicBarrier。
            - Exchanger
            - Exchanger-交换器,是 JDK1.5 时引入的一个同步器,从字面上就可以看出,这个类的主要作用是交换数据。
            - Exchanger 有点类似于 CyclicBarrier。Exchanger 可以看成是一个双向栅栏。
            - ![Java_Exchanger](Java-basic-0-知识点汇总/Java_Exchanger.png)
            - Thread1 线程到达栅栏后,会首先观察有没其它线程已经到达栅栏,如果没有就会等待,如果已经有其它线程(Thread2)已经到达了,就会以成对的方式交换各自携带的信息,因此 Exchanger 非常适合用于两个线程之间的数据交换。
            - Phaser
            - Phaser 是 JDK1.7 开始引入的一个同步工具类,适用于一些需要分阶段的任务的处理。它的功能与 CyclicBarrier 和 CountDownLatch 有些类似,类似于一个多阶段的栅栏,并且功能更强大
            - Fork/Join 框架
            - Fork/Join 框架是在 java7 之后提供的一种基于分治策略的多线程框架。与分支策略思想一样,即一个大问题可以被拆分为若干个小问题,而且小问题之间互不干扰,并且解法与原问题形式相同,最终将子问题的解合并可以得到原问题的解。
            - 执行流程
            - ![Java_ForkJoin_执行流程](Java-basic-0-知识点汇总/Java_ForkJoin_执行流程.png)
            - 相关类
            - RecursiveTask
            - ForkJoinPool
            - 线程
            - 线程的五种状态
            - ![Java_线程_线程状态转换图](Java-basic-0-知识点汇总/Java_线程_线程状态转换图.jpg)
            - NEW
            - 新创建了一个线程对象。
            - RUNNABLE
            - 线程对象创建后,其他线程(比如 main 线程)调用了该对象的 `start()` 方法。该状态的线程位于可运行线程池中,等待被线程调度选中,获取 cpu 的使用权。
            - RUNNING
            - 可运行状态(runnable)的线程获得了 cpu 时间片(timeslice),执行程序代码。
            - BLOCKED
            - 阻塞状态是指线程因为某种原因放弃了 cpu 使用权,也即让出了 cpu timeslice,暂时停止运行。直到线程进入可运行(runnable)状态,才有机会再次获得 cpu timeslice 转到运行(running)状态。阻塞的情况分三种:
            - 等待阻塞:运行(running)的线程执行 `o.wait()` 方法,JVM 会把该线程放入等待队列(waitting queue)中。
            - 等待队列
            - 调用 obj 的 `wait()`,`notify()`方法前,必须获得 obj 锁,也就是必须写在 `synchronized(obj)` 代码段内。
            - ![Java_线程_锁池](Java-basic-0-知识点汇总/Java_线程_锁池.jpg)
            - 锁池状态
            - 当前线程想调用对象 A 的同步方法时,发现对象 A 的锁被别的线程占有,此时当前线程进入锁池状态。简言之,锁池里面放的都是想争夺对象锁的线程。
            - 当一个线程 1 被另外一个线程 2 唤醒时,1 线程进入锁池状态,去争夺对象锁。
            - 锁池是在同步的环境下才有的概念,一个对象对应一个锁池。
            - 同步阻塞:运行(running)的线程在获取对象的同步锁时,若该同步锁被别的线程占用,则 JVM 会把该线程放入锁池(lock pool)中。
            - 其他阻塞:运行(running)的线程执行 `Thread.sleep(long ms)` 或 `t.join()` 方法,或者发出了 I/O 请求时,JVM 会把该线程置为阻塞状态。当 `sleep()` 状态超时、`join()` 等待线程终止或者超时、或者 I/O 处理完毕时,线程重新转入可运行(runnable)状态。
            - DEAD
            - 线程 `run()`、`main()` 方法执行结束,或者因异常退出了 `run()` 方法,则该线程结束生命周期。死亡的线程不可再次复生。
            - 几种会导致线程状态改变的方法
            - api
            - `Thread.sleep(long millis)`,一定是当前线程调用此方法,当前线程进入阻塞,但不释放对象锁,millis 后线程自动苏醒进入可运行状态。
            - 作用:给其它线程执行机会的最佳方式。
            - `Thread.yield()`,一定是当前线程调用此方法,当前线程放弃获取的 cpu 时间片,由运行状态变会可运行状态,让 OS 再次选择线程。
            - 作用:让相同优先级的线程轮流执行,但并不保证一定会轮流执行。实际中无法保证 `yield()` 达到让步目的,因为让步的线程还有可能被线程调度程序再次选中。`Thread.yield()` 不会导致阻塞。
            - `t.join()/t.join(long millis)`,当前线程里调用其它线程 1 的 join 方法,当前线程阻塞,但不释放对象锁,直到线程 1 执行完毕或者 millis 时间到,当前线程进入可运行状态。
            - `obj.wait()`,当前线程调用对象的 `wait()` 方法,当前线程释放对象锁,进入等待队列。依靠 `notify()/notifyAll()` 唤醒或者 `wait(long timeout)` timeout 时间到自动唤醒。
            - `obj.notify()`,唤醒在此对象监视器上等待的单个线程,选择是任意性的。`notifyAll()` 唤醒在此对象监视器上等待的所有线程。
            - 应用
            - `Thread.yield()` 和 `Thread.sleep(0)`
            - `Thread.yield()` 和 `Thread.sleep(0)` 语义实现取决于具体的 JVM,某些 JVM 可能什么都不做,而大多数虚拟机会让线程放弃剩余的 cpu 时间片,重新变为 runnable 状态,并放到同优先级线程队列的末尾等待 cpu 资源。 但是当我们调用 `Thread.yield()` 的那一刻,并不意味着当前线程立马释放 cpu 资源,这是因为获得时间片的线程从 runable 切换到 running 仍需要一定的准备时间,这段时间当前线程仍可能运行一小段时间。
            - Thread 的常用方法
            - `interrupt()`
            - 其作用是中断此线程(此线程不一定是当前线程,而是指调用该方法的 Thread 实例所代表的线程),但实际上只是给线程设置一个中断标志,线程仍会继续运行。
            - `interrupted()`
            - 作用是测试当前线程是否被中断(检查中断标志),返回一个 boolean 并清除中断状态,第二次再调用时中断状态已经被清除,将返回一个 false。
            - `isInterrupted()`
            - 作用是只测试此线程是否被中断 ,不清除中断状态。
            - `join()`
            - 线程安全问题
            - 运行结果错误
            - 发布和初始化导致线程安全问题
            - 我们创建对象并进行发布和初始化供其他类或对象使用是常见的操作,但如果我们操作的时间或地点不对,就可能导致线程安全问题。
            - 活跃性问题
            - 活跃性问题就是程序始终得不到运行的最终结果,相比于前面两种线程安全问题带来的数据错误或报错,活跃性问题带来的后果可能更严重,比如发生死锁会导致程序完全卡死,无法向下运行。
            - 最典型的有三种
            - 死锁
            - 死锁是一种状态,当两个(或多个)线程(或进程)相互持有对方所需要的资源,却又都不主动释放自己手中所持有的资源,导致大家都获取不到自己想要的资源,所有相关的线程(或进程)都无法继续往下执行,在未改变这种状态之前都不能向前推进,我们就把这种状态称为死锁状态,认为它们发生了死锁。
            - 活锁
            - 举一个例子,假设有一个消息队列,队列里放着各种各样需要被处理的消息,而某个消息由于自身被写错了导致不能被正确处理,执行时会报错,可是队列的重试机制会重新把它放在队列头进行优先重试处理,但这个消息本身无论被执行多少次,都无法被正确处理,每次报错后又会被放到队列头进行重试,周而复始,最终导致线程一直处于忙碌状态,但程序始终得不到结果,便发生了活锁问题。
            - 饥饿
            - 饥饿是指线程需要某些资源时始终得不到,尤其是 CPU 资源,就会导致线程一直不能运行而产生的问题。
            - 线程池
            - 核心的参数概念
            - 最大线程数 maximumPoolSize
            - 该参数表示的是线程池中允许存在的最大线程数量。当任务队列满了以后,再有新的任务进入到线程池时,会判断再新建一个线程是否会超过 maximumPoolSize,如果会超过,则不创建线程,而是执行拒绝策略。如果不会超过 maximumPoolSize,则会创建新的线程来执行任务。
            - 核心线程数 corePoolSize
            - 该参数表示的是线程池的核心线程数。当任务提交到线程池时,如果线程池的线程数量还没有达到 corePoolSize,那么就会新创建的一个线程来执行任务,如果达到了,就将任务添加到任务队列中。
            - 活跃时间 keepAliveTime
            - 当线程池中的线程数量大于 corePoolSize 时,那么大于 corePoolSize 这部分的线程,如果没有任务去处理,那么就表示它们是空闲的,这个时候是不允许它们一直存在的,而是允许它们最多空闲一段时间,这段时间就是 keepAliveTime,时间的单位就是 TimeUnit。
            - unit
            - 空闲线程允许存活时间的单位,TimeUnit 是一个枚举值,它可以是纳秒、微妙、毫秒、秒、分、小时、天。
            - 阻塞队列 workQueue
            - 任务队列,用来存放任务。该队列的类型是阻塞队列,常用的阻塞队列有 ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityBlockingQueue 等。
            - ArrayBlockingQueue
            - 是一个基于数组实现的阻塞队列,元素按照先进先出(FIFO)的顺序入队、出队。因为底层实现是数组,数组在初始化时必须指定大小,因此 ArrayBlockingQueue 是有界队列。
            - LinkedBlockingQueue
            - 是一个基于链表实现的阻塞队列,元素按照先进先出(FIFO)的顺序入队、出队。因为顶层是链表,链表是基于节点之间的指针指向来维持前后关系的,如果不指链表的大小,它默认的大小是 Integer.MAX_VALUE。这个数值太大了,因此通常称 LinkedBlockingQueue 是一个无界队列。当然如果在初始化的时候,就指定链表大小,那么它就是有界队列了。
            - SynchronousQueue
            - 是一个不存储元素的阻塞队列。每个插入操作必须得等到另一个线程调用了移除操作后,该线程才会返回,否则将一直阻塞。吞吐量通常要高于 LinkedBlockingQueue。
            - PriorityBlockingQueue
            - 是一个将元素按照优先级排序的阻塞的阻塞队列,元素的优先级越高,将会越先出队列。这是一个无界队列。
            - threadFactory
            - 线程池工厂,用来创建线程。通常在实际项目中,为了便于后期排查问题,在创建线程时需要为线程赋予一定的名称,通过线程池工厂,可以方便的为每一个创建的线程设置具有业务含义的名称。
            - 拒绝策略 RejectedExecutionHandler
            - AbortPolicy:直接丢弃任务,抛出异常,这是默认策略
            - CallerRunsPolicy:只用调用者所在的线程来处理任务
            - DiscardOldestPolicy:丢弃等待队列中最旧的任务,并执行当前任务
            - DiscardPolicy:直接丢弃任务,也不抛出异常
            - 分类
            - FixedThreadPool
            - 特点:固定池子中线程的个数。使用静态方法 `newFixedThreadPool()` 创建线程池的时候指定线程池个数。
            - CachedThreadPool(弹性缓存线程池)
            - 特点:用 `newCachedThreadPool()` 方法创建该线程池对象,创建之初里面一个线程都没有,当 execute 方法或 submit 方法向线程池提交任务时,会自动新建线程;如果线程池中有空余线程,则不会新建;这种线程池一般最多情况可以容纳几万个线程,里面的线程空余 60s 会被回收。
            - SingleThreadPool(单线程线程池)
            - 池中只有一个线程,如果扔 5 个任务进来,那么有 4 个任务将排队;作用是保证任务的顺序执行。
            - ScheduledThreadpool(定时器线程池)
            - 在给定延迟后运行命令或者定期地执行。
            - WorkStealingPool
            - 在 Java 8 中,引入了一种新型的线程池,作为 `newWorkStealingPool()` 来补充现有的线程池。WorkStealingPool 线程池,来维持相应的并行级别,它会通过工作窃取的方式,使得多核的 CPU 不会闲置,总会有活着的线程让 CPU 去运行。
            - 它基于工作窃取算法,其中任务可以生成其他较小的任务,这些任务将添加到并行处理线程的队列中。如果一个线程完成了工作并且无事可做,则可以从另一线程的队列中“窃取”工作。
            - 底层用的 ForkJoinPool 来实现的。
            - ForkJoinPool
            - 在 Java7 中引入。主要用来使用分治法(Divide-and-Conquer Algorithm)来解决问题。ForkJoinPool 的优势在于,可以充分利用多 cpu,多核 cpu 的优势,把一个任务拆分成多个“小任务”分发到不同的 cpu 核心上执行,执行完后再把结果收集到一起返回。
            - 线程池的五种状态
            - ![Java_线程池_状态转换](Java-basic-0-知识点汇总/Java_线程池_状态转换.jpg)
            - RUNNING
            - 状态说明:线程池处在 RUNNING 状态时,能够接收新任务,以及对已添加的任务进行处理。
            - 状态切换:线程池的初始化状态是 RUNNING。换句话说,线程池被一旦被创建,就处于 RUNNING 状态,并且线程池中的任务数为 0!
            - SHUTDOWN
            - 状态说明:线程池处在 SHUTDOWN 状态时,不接收新任务,但能处理已添加的任务。
            - 状态切换:调用线程池的 `shutdown()` 接口时,线程池由 RUNNING -> SHUTDOWN。
            - STOP
            - 状态说明:线程池处在 STOP 状态时,不接收新任务,不处理已添加的任务,并且会中断正在处理的任务。
            - 状态切换:调用线程池的 `shutdownNow()` 接口时,线程池由(RUNNING or SHUTDOWN) -> STOP。
            - TIDYING
            - 状态说明:当所有的任务已终止,ctl 记录的”任务数量”为 0,线程池会变为 TIDYING 状态。当线程池变为 TIDYING 状态时,会执行钩子函数 `terminated()`。`terminated()` 在 ThreadPoolExecutor 类中是空的,若用户想在线程池变为 TIDYING 时,进行相应的处理;可以通过重载 `terminated()` 函数来实现。
            - 状态切换:当线程池在 SHUTDOWN 状态下,阻塞队列为空并且线程池中执行的任务也为空时,就会由 SHUTDOWN -> TIDYING。当线程池在 STOP 状态下,线程池中执行的任务为空时,就会由 STOP -> TIDYING。
            - TERMINATED
            - 状态说明:线程池彻底终止,就变成 TERMINATED 状态。
            - 状态切换:线程池处在 TIDYING 状态时,执行完 `terminated()` 之后,就会由 TIDYING -> TERMINATED。
            - 提交一个新任务到线程池时,具体的执行流程
            1. 当我们提交任务,线程池会根据 corePoolSize 大小创建若干任务数量线程执行任务
            2. 当任务的数量超过 corePoolSize 数量,后续的任务将会进入阻塞队列阻塞排队
            3. 当阻塞队列也满了之后,那么将会继续创建 `(maximumPoolSize-corePoolSize)` 个数量的线程来执行任务,如果任务处理完成,`maximumPoolSize-corePoolSize` 额外创建的线程等待 keepAliveTime 之后被自动销毁
            - **如果使用无界队列**
            - 使用了无界队列,会直接导致最大线程数的配置失效。服务端高并发下使用无界的阻塞队列会发生 OOM,把机器打爆。LinkedBlockingQueue 默认的最大任务数量是 Integer.MAX_VALUE,非常大,近乎于可以理解为无限吧。
            4. 如果达到 maximumPoolSize,阻塞队列还是满的状态,那么将根据不同的拒绝策略对应处理
            - ![Java_线程池_提交任务](Java-basic-0-知识点汇总/Java_线程池_提交任务.jpg)
            - 原理
            - 在线程池中,使用了一个原子类 AtomicInteger 的变量来表示线程池状态和线程数量,该变量在内存中会占用 4 个字节,也就是 32bit,其中高 3 位用来表示线程池的状态,低 29 位用来表示线程的数量。
            - 线程池的状态一共有 5 种状态,用 3bit 最多可以表示 8 种状态
            - ![Java_线程池_AtomicInteger](Java-basic-0-知识点汇总/Java_线程池_AtomicInteger.jpg)
            - 线程池参数设计
            - CPU 密集型任务
            - 这种任务消耗的主要是 CPU 资源,可以将线程数设置为 N(CPU 核心数)+1,比 CPU 核心数多出来的一个线程是为了防止线程偶发的缺页中断,或者其它原因导致的任务暂停而带来的影响。
            - 一旦任务暂停,CPU 就会处于空闲状态,而在这种情况下多出来的一个线程就可以充分利用 CPU 的空闲时间。
            - I/O 密集型任务
            - 这种任务应用起来,系统会用大部分的时间来处理 I/O 交互,而线程在处理 I/O 的时间段内不会占用 CPU 来处理,这时就可以将 CPU 交出给其它线程使用。因此在 I/O 密集型任务的应用中,我们可以多配置一些线程,具体的计算方法是 2N。
            - **IO 是否会一直占用CPU?**
            - IO 所需要的 CPU 资源非常少。大部分工作是分派给 DMA(Direct Memory Access)完成的。
            - 流程
            - CPU 计算文件地址 ——> 委派 DMA 读取文件 ——> DMA 接管总线 ——> CPU 的 A 进程阻塞,挂起——> CPU 切换到 B 进程 ——> DMA 读完文件后通知 CPU(一个中断异常)——> CPU 切换回 A 进程操作文件
            - 相关问题
            - **为什么是先判断任务队列有没有满,再判断线程数有没有超过最大线程数?而不是先判断最大线程数,再判断任务队列是否已满?**
            - 案和具体的源码实现有关。因为当需要创建线程的时候,都会调用 `addWorker()` 方法,在 `addWorker()` 的后半部分的逻辑中,会调用 `mainLock.lock()` 方法来获取全局锁,而获取锁就会造成一定的资源争抢。如果先判断最大线程数,再判断任务队列是否已满,这样就会造成线程池原理的 4 个步骤中,第 1 步判断核心线程数时要获取全局锁,第 2 步判断最大线程数时,又要获取全局锁,这样相比于先判断任务队列是否已满,再判断最大线程数,就可能会多出一次获取全局锁的过程。因此在设计线程池,为了尽可能的避免因为获取全局锁而造成资源的争抢,所以会先判断任务队列是否已满,再判断最大线程数。
            - **LinkedBlockingQueue 的吞吐量比 ArrayBlockingQueue 的吞吐量要高。前者是基于链表实现的,后者是基于数组实现的,正常情况下,不应该是数组的性能要高于链表吗?**
            - 因为 LinkedBlockingQueue 的读和写操作使用了两个锁,takeLock 和 putLock,读写操作不会造成资源的争抢。而 ArrayBlockingQueue 的读和写使用的是同一把锁,读写操作存在锁的竞争。因此 LinkedBlockingQueue 的吞吐量高于 ArrayBlockingQueue。
            - **为什么要使用线程池?**
            - 降低资源消耗。通过重复利用已创建的线程,降低线程创建和销毁造成的消耗。
            - 提高响应速度。当任务到达时,任务可以不需要等到线程创建就能立即执行。
            - 增加线程的可管理型。线程是稀缺资源,使用线程池可以进行统一分配,调优和监控。
            - **线程池为什么能维持线程不释放,随时运行各种任务?**
            - 线程池就是用一堆包装住 Thread 的 Wroker 类的集合,在里面有条件的进行着死循环,从而可以不断接受任务来进行。

            ### 异常
            - 基类为 Throwable
            - 子类 Error(错误)
            - 所有的编译时期的错误以及系统错误都是通过 Error 抛出的。这些错误表示故障发生于虚拟机自身、或者发生在虚拟机试图执行应用时,如 Java 虚拟机运行错误(Virtual MachineError)、类定义错误(NoClassDefFoundError)等。这些错误是不可查的,因为它们在应用程序的控制和处理能力之外,而且绝大多数是程序运行时不允许出现的状况。对于设计合理的应用程序来说,即使确实发生了错误,本质上也不应该试图去处理它所引起的异常状况。在 Java 中,错误通过 Error 的子类描述。
            - 常见的 Error
            - OutOfMemoryError
            - 如果虚拟机在扩展栈时无法申请到足够的内存空间,则抛出 OutOfMemoryError异常。
            - 具体情况
            - OutOfMemoryError: PermGen space
            - 在 JDK1.8 之前,方法区放在堆的永久带区(PermGen),方法区内存溢出则报此异常
            - OutOfMemoryError: Metaspace
            - JDK1.8 及以后的版本使用 Metaspace 来代替永久代,Metaspace 是方法区在 HotSpot 中的实现,它与持久代最大区别在于,Metaspace 并不在虚拟机内存中而是使用本地内存。
            - StackOverflowError
            - 如果线程请求的栈深度大于虚拟机所允许的最大深度,将抛出 StackOverflowError异常。
            - 子类 Exception(异常)
            - RuntimeException
            - 常见的 RuntimeException
            - NullPointerException
            - ClassNotFoundException
            - NumberFormatException
            - IndexOutOfBoundsException
            - IllegalArgumentException
            - ClassCastException
            - 非 RuntimeException
            - 是 checked exception,需要在代码中处理
            - 捕获异常
            - finally
            - try 关键字最后可以定义 finally 代码块。 finally 块中定义的代码,总是在 try 和任何 catch 块之后、方法完成之前运行。
            - 正常情况下,不管是否抛出或捕获异常 finally 块都会执行。
            - 使用场景
            - 执行关闭连接、关闭文件和释放线程的的操作。
            - 相关问题
            - **啥时候 finally 不会被执行?**
            - 调用 System.exit 函数
            - ```
            try {
            System.out.println("Inside try");
            System.exit(1);
            } finally {
            System.out.println("Inside finally");
            }
          • 调用 halt 函数
            • ```
              try {
              System.out.println("Inside try");
              Runtime.getRuntime().halt(1);
              
              } finally {
              System.out.println("Inside finally");
              
              }
              1
              2
              3
              4
              5
              6
              7
              8
              9
              10
              11
              12
              13
              14
                  - 守护线程
              - 如果守护线程刚开始执行到 finally 代码块,此时没有任何其他非守护线程,那么虚拟机将退出,此时 JVM 不会等待守护线程的 finally 代码块执行完成。
              - try 代码块中无限循环
              - 常见陷阱
              - 忽视异常
              - finally 代码块包含返回语句,没有处理未捕获的异常。
              - ```
              try {
              System.out.println("Inside try");
              throw new RuntimeException();
              } finally {
              System.out.println("Inside finally");
              return "from finally";
              }
          • 此时,try 代码块中的 RuntimeException 会被忽略,函数返回 “from finally”字符串。
        • 覆盖其他返回语句
          • 如果 finally 代码块中存在返回语句,则 try 和 catch 代码块如果存在返回语句就会被忽略。
        • 改变 throw 或 return 行为
          • 如果再 finally 代码块中扔出异常,则 try 和 catch 中的异常扔出或者返回语句都将被忽略。
          • ```
            try {
            System.out.println("Inside try");
            return "from try";
            
            } finally {
            throw new RuntimeException();
            
            }
            1
            2
            3
            4
            5
            6
            7
            8
                - 这段代码永远都不会有返回值,总是会抛出 RuntimeException。
            - 执行顺序
            - ```
            try {
            return expression;
            } finally {
            do some work;
            }
        1. 执行:expression,计算该表达式,结果保存在操作数栈顶;
        2. 执行:操作数栈顶值(expression 的结果)复制到局部变量区作为返回值;
        3. 执行:finally 语句块中的代码;
        4. 执行:将第 2 步复制到局部变量区的返回值又复制回操作数栈顶;
        5. 执行:return 指令,返回操作数栈顶的值;

JNI、JNA

  • JNI(Java Native Interface)
    • 它允许 Java 代码和其他语言(尤其 C/C++)写的代码进行交互,只要遵守调用约定即可。
    • 调用过程
      • Java_JNI调用过程
    • 缺点
      • 调用步骤非常的多,很麻烦,使用 JNI 调用 .dll/.so 共享库都能体会到这个痛苦的过程。如果已有一个编译好的 .dll/.so 文件,如果使用 JNI 技术调用,我们首先需要使用 C 语言另外写一个 .dll/.so 共享库,使用 SUN 规定的数据结构替代 C 语言的数据结构,调用已有的 dll/so 中公布的函数。然后再在 Java 中载入这个库 dll/so,最后编写 Java native 函数作为链接库中函数的代理。经过这些繁琐的步骤才能在 Java 中调用本地代码。因此,很少有 Java 程序员愿意编写调用 dll/.so 库中原生函数的 java 程序。
  • JNA(Java Native Access)
    • 是一个开源的 Java 框架,是 SUN 公司主导开发的,建立在经典的 JNI 的基础之上的一个框架。
    • JNA 大大简化了调用本地方法的过程,使用很方便,基本上不需要脱离 Java 环境就可以完成。
    • 调用过程
      • Java_JNA调用过程
  • 相关问题
    • JNA 能完全替代 JNI 吗?
      • JNA 是不能完全替代 JNI 的,因为有些需求还是必须求助于 JNI。
      • 使用 JNI 技术,不仅可以实现 Java 访问 C 函数,也可以实现 C 语言调用 Java 代码。
      • 而 JNA 只能实现 Java 访问 C 函数,作为一个 Java 框架,自然不能实现 C 语言调用 Java 代码。此时,你还是需要使用 JNI 技术。
      • JNI 是 JNA 的基础,是 Java 和 C 互操作的技术基础。

Java 与 C++ 的区别

  • Java 是纯粹的面向对象语言,所有的对象都继承自 java.lang.Object,C++ 为了兼容 C 即支持面向对象也支持面向过程。
  • Java 通过虚拟机从而实现跨平台特性,但是 C++ 依赖于特定的平台。
  • Java 没有指针,它的引用可以理解为安全指针,而 C++ 具有和 C 一样的指针。
  • Java 支持自动垃圾回收,而 C++ 需要手动回收。
  • Java 不支持多重继承,只能通过实现多个接口来达到相同目的,而 C++ 支持多重继承。
  • Java 不支持操作符重载,虽然可以对两个 String 对象执行加法运算,但是这是语言内置支持的操作,不属于操作符重载,而 C++ 可以。
  • Java 的 goto 是保留字,但是不可用,C++ 可以使用 goto。

算法

五大常用算法

分治算法

  • 基本概念:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
  • 运用:排序算法(快速排序,归并排序)、傅立叶变换(快速傅立叶变换)、二分搜索、大整数乘法、Strassen 矩阵乘法、棋盘覆盖、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔……
  • 分治法所能解决的问题一般具有以下几个特征:
  1. 该问题的规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解;
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

说明:第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;
第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;
第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

  • 分治法在每一层递归上都有三个步骤:
  1. 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
  2. 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
  3. 合并:将各个子问题的解合并为原问题的解。

动态归纳

  • 基本概念:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。
  • 与分治法之间的区别:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。
  • 能采用动态规划求解的问题的一般要具有 3 个性质:
  1. 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
  2. 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
  3. 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
  • 动态规划的设计都有着一定的模式,一般要经历以下几个步骤:
  1. 划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
  2. 确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
  3. 确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
  4. 寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

贪心算法

  • 基本概念:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
  • 运用:Prim算法、Kruskal算法(都是求最小生成树的)
  • 基本思路:将问题分解为若干个小问题,逐渐求得各个子问题的局部最优解,最后合并为原来问题的解
  • 贪婪算法可解决的问题通常大部分都有如下的特性:
  1. 随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。
  2. 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
  3. 还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。
  4. 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
  5. 最后,目标函数给出解的值。
  6. 为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行,那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合,并检查该集合是否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。
  • 贪心算法的实现框架

从问题的某一初始解出发;
while (能朝给定总目标前进一步)
{
利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;

回溯算法

  • 基本概念:回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

分支限界

  • 基本概念:类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。
  • 与回溯算法的区别:分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

加密算法

  • 加密和解密
    • 加密
      • 数据加密的基本过程,就是对原来为明文的文件或数据按某种算法进行处理,使其成为不可读的一段代码,通常称为“密文”。通过这样的途径,来达到保护数据不被 非法人窃取、阅读的目的。
    • 解密
      • 加密的逆过程为解密,即将该编码信息转化为其原来数据的过程。
  • 加密方式
    • 对称加密算法
      • 的加密与解密密钥相同,又称为共享密钥加密算法。
      • 流程
        • 数据加密过程:在对称加密算法中,数据发送方将明文(原始数据)和加密密钥一起经过特殊加密处理,生成复杂的加密密文进行发送。
        • 数据解密过程:数据接收方收到密文后,若想读取原数据,则需要使用加密使用的密钥及相同算法的 逆算法对加密的密文进行解密,才能使其恢复成可读明文。
      • 常见算法
        • DES 算法
          • DES 加密算法是一种分组密码,以 64 位为分组对数据加密,它的密钥长度是 56 位,加密解密用同一算法。
          • DES 加密算法是对密钥进行保密,而公开算法,包括加密和解密算法。这样,只有掌握了和发送方相同密钥的人才能解读由 DES 加密算法加密的密文数据。因此,破译 DES 加密算法实际上就是搜索密钥的编码。对于 56 位长度的密钥来说,如果用穷举法来进行搜索的话,其运算次数为 $2^56$ 次。
        • 3DES 算法
          • 是基于 DES 的对称算法,对一块数据用三个不同的密钥进行三次加密,强度更高。
        • AES 算法
          • AES 加密算法是密码学中的高级加密标准,该加密算法采用对称分组密码体制,密钥长度的最少支持为 128 位、 192 位、256 位,分组长度 128 位,算法应易于各种硬件和软件实现。这种加密算法是美国联邦政府采用的区块加密标准。
          • AES 本身就是为了取代 DES 的,AES 具有更好的安全性、效率和灵活性。
    • 非对称加密算法
      • 的加密密钥与解密密钥不同,又称为公开密钥加密算法。
      • 需要两个密钥,一个称为公开密钥(public key),即公钥,另一个称为私有密钥(private key),即私钥。
      • 流程
        • 如果使用公钥对数据进行加密,只有用对应的私钥才能进行解密。
        • 如果使用私钥对数据进行加密,只有用对应的公钥才能进行解密。
      • 常见算法
        • RSA 算法
          • RSA 加密算法是目前最有影响力的公钥加密算法,并且被普遍认为是目前最优秀的公钥方案之一。RSA 是第一个能同时用于加密和数字签名的算法,它能够抵抗到目前为止已知的所有密码攻击,已被 ISO 推荐为公钥数据加密标准。
          • RSA 加密算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。
          • 原理
            • 例子
              • 假如原文是 123
              • $123*13=1599$,我取后 3 位即 599 作为密文,然后取 13 作为加密密钥,关键来了,如果要对 599 进行解密,按照以往的思路,是不是要做除法?但是你的密文是 599,你并不知道 1599 这个完整的信息,所以不能直接做除法,那怎么办呢?
              • $599*77=46123$,然后我取 46123 的后 3 位,其中 77 是解密密钥
              • 那么上面的这个加密和解密用的都是乘法,加密解密不是互逆的运算,这就是非对称。
              • 那么这个 13 和 77 为什么是这两个数字呢?其实 $13*77=1001$,任何三位正整数 abc 乘以 1001 结果都是 abcabc, 所以才能保证原文的正确还原
        • ECC 算法
          • ECC 也是一种非对称加密算法,主要优势是在某些情况下,它比其他的方法使用更小的密钥,比如 RSA 加密算法,提供相当的或更高等级的安全级别。不过一个缺点是加密和解密操作的实现比其他机制时间长(相比 RSA 算法,该算法对 CPU 消耗严重)。
    • 不需要密钥的散列算法
      • 常见算法
        • MD5 算法
          • MD5 用的是哈希函数,它的典型应用是对一段信息产生信息摘要,以防止被篡改。严格来说,MD5 不是一种加密算法而是摘要算法。无论是多长的输入,MD5 都会输出长度为 128bits 的一个串(通常用 16 进制表示为 32 个字符)。
        • SHA1 算法
          • SHA1 是和 MD5 一样流行的消息摘要算法,然而 SHA1 比 MD5 的 安全性更强。对于长度小于 $2^64$ 位的消息,SHA1 会产生一个 160 位的消息摘要。基于 MD5、SHA1 的信息摘要特性以及不可逆(一般而言),可以被应用在检查文件完整性以及数字签名等场景。
        • HMAC 算法
          • HMAC 是密钥相关的哈希运算消息认证码(Hash-based Message Authentication Code),HMAC 运算利用哈希算法(MD5、SHA1 等),以一个密钥和一个消息为输入,生成一个消息摘要作为输出。
          • HMAC 发送方 和 接收方都有的 key 进行计算,而没有这把 key 的第三方,则是无法计算出正确的散列值的,这样就可以防止数据被篡改。
    • 混合加密
      • 由于以上加密算法都有各自的缺点(RSA 加密速度慢、AES 密钥存储问题、MD5 加密不可逆),因此实际应用时常将几种加密算法混合使用。
      • 常见算法
        • RSA + AES
          • 采用 RSA 加密 AES 的密钥,采用 AES 对数据进行加密,这样集成了两种加密算法的优点,既保证了数据加密的速度,又实现了安全方便的密钥管理。
    • 其他
      • Base64
        • Base64 编码之所以称为 Base64,是因为其使用 64 个字符来对任意数据进行编码,同理有 Base32、Base16 编码。
        • 标准 Base64 编码使用的 64 个字符为:
          • Base64_基础字符
          • 这 64 个字符是各种字符编码(比如 ASCII 编码)所使用字符的子集,基本,并且可打印。唯一有点特殊的是最后两个字符,因对最后两个字符的选择不同,Base64 编码又有很多变种,比如 Base64 URL 编码。
        • 原理
          • Base64 编码本质上是一种将二进制数据转成文本数据的方案。对于非二进制数据,是先将其转换成二进制形式,然后每连续 6 比特($2^6=64$)计算其十进制值,根据该值在上面的索引表中找到对应的字符,最终得到一个文本字符串。
        • Base64 编码是每 3 个原始字符编码成 4 个字符,如果原始字符串长度不能被 3 整除,那怎么办?使用 0 值来补充原始字符串。
          • Base64_编码例子
            • 最后 2 个零值只是为了 Base64 编码而补充的,在原始字符中并没有对应的字符,那么 Base64 编码结果中的最后两个字符 AA 实际不带有效信息,所以需要特殊处理,以免解码错误。
          • 标准 Base64 编码通常用 = 字符来替换最后的 A,即编码结果为 SGVsbG8hIQ==。因为 = 字符并不在 Base64 编码索引表中,其意义在于结束符号,在 Base64 解码时遇到 = 时即可知道一个 Base64 编码字符串结束。
          • 解码是对编码的逆向操作,但注意一点:对于最后的两个 = 字符,转换成两个 A 字符,再转成对应的两个 6 比特二进制0值,接着转成原始字符之前,需要将最后的两个 6 比特二进制 0 值丢弃,因为它们实际上不携带有效信息。

排序算法

  • 分类
    • 根据排序的空间来分
      • In-place sort(内部排序)
        • 在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序
        • 当需要对大量数据进行排序时,In-place sort 就显示出优点,因为只需要占用常数的内存
        • 排序方式
          • 插入排序、选择排序、冒泡排序、堆排序、快速排序
      • Out-place sort(外部排序)
        • 在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序排序方法称为外排序
        • 排序方式
          • 归并排序、计数排序、基数排序、桶排序
    • 根据排序的稳定性来分
      • stable sort(稳定排序)
        • 有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就说这种排序方法是稳定的
        • 排序方式
          • 插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序
      • unstable sort(非稳定排序)
      • 排序方式
        • 选择排序、快速排序、堆排序
  • 排序算法
    • 排序算法比较
    • 插入排序
      • 基本思路:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
        • 插入排序
      • 时间复杂度:
        • 最优复杂度:当输入数组就是排好序的时候,复杂度为 $O(n)$,而快速排序在这种情况下会产生 $O(n^2)$ 的复杂度。
        • 最差复杂度:当输入数组为倒序时,复杂度为 $O(n^2)$。
      • 插入排序包括:
        • 直接插入排序
          • 基本思路:把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的纪录插入完为止,得到一个新的有序序列
          • 稳定性:稳定排序
        • 二分插入排序(又称折半插入排序)
          • 将直接插入排序中寻找 A[i] 的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。
          • 稳定性:稳定排序
          • 算法过程
            1. 计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的元素大,说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置到中间值的位置,这样很简单的完成了折半;
            2. 在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i 个元素要插在什么地方;
            3. 确定位置之后,将整个序列后移,并将元素插入到相应位置。
        • 链表插入排序
    • 希尔排序(又称缩小增量排序)。
      • 希尔排序法又称缩小增量法。是插入排序的一种变种。
      • 稳定性:不稳定
      • 基本思路:把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。
        • 希尔排序
      • 时间复杂度:希尔排序的时间复杂度与增量序列的选取有关。例如希尔增量时间复杂度为 $O(n^2)$,而 Hibbard 增量的希尔排序的时间复杂度为 $O(n^{\frac{3}{2}})$,希尔排序时间复杂度的下界是 $O(n*log2n)$。
      • 希尔排序没有快速排序算法快 $O(n(logn))$,因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。
      • 本质上讲,希尔排序算法是直接插入排序算法的一种改进,减少了其复制的次数,速度要快很多。原因是,当n值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。当n值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。
    • 冒泡排序
      • 基于交换排序的一种算法。
      • 稳定性:稳定
      • 时间复杂度:
        • 最坏运行时间:$O(n^2)$;
        • 最佳运行时间:$O(n^2)$(当然,也可以进行改进使得最佳运行时间为 $O(n)$)
      • 基本思路:通过两两交换,像水中的泡泡一样,小的先冒出来,大的后冒出来。
        • 冒泡排序
    • 选择排序
      • 稳定性:不稳定
      • 时间复杂度:
        • 最好情况时间:$O(n^2)$。
        • 最坏情况时间:$O(n^2)$。
      • 基本思路:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
        • 选择排序
    • 归并排序
      • 时间复杂度:
        • 最坏情况运行时间:$O(nlogn)$。
        • 最佳运行时间:$O(nlogn)$。
      • 速度仅次于快速排序
      • 稳定性:稳定
      • 基本思路:运用分治法思想解决排序问题
        • 归并排序
      • 算法过程
        1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
        2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
        3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
        4. 重复步骤 3 直到某一指针超出序列尾
        5. 将另一序列剩下的所有元素直接复制到合并序列尾
    • 快速排序
      • 被誉为“20世纪十大经典算法之一”。
      • 时间复杂度:
        • 最坏运行时间:当输入数组已排序时,时间为 $O(n^2)$,当然可以通过随机化来改进(shuffle array 或者 randomized select pivot),使得期望运行时间为 $O(nlogn)$。
        • 最佳运行时间:$O(nlogn)$。
      • 稳定性:不稳定
      • 基本思路:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
        • 快速排序
    • 堆排序
      • 时间复杂度:
        • 最优时间:$O(nlogn)$。
        • 最差时间:$O(nlogn)$。
      • 稳定性:不稳定
      • 基本思路:堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
        • 堆排序
      • 堆实质上是满足如下性质的完全二叉树:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
      • 大根堆和小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆。
    • 计数排序
      • 是一个非基于比较的排序算法
      • 时间复杂度:
        • 最坏情况运行时间:$O(n+k)$。
        • 最好情况运行时间:$O(n+k)$。当 $k=O(n)$ 时,计数排序时间为 $O(n)$
      • 稳定性:稳定
      • 基本思路:对于给定的输入序列中的每一个元素 x,确定该序列中值小于 x 的元素的个数。一旦有了这个信息,就可以将x直接存放到最终的输出序列的正确位置上。
        • 计数排序
      • 它的优势在于在对一定范围内的整数排序时,它的复杂度为 $Ο(n+k)$(其中k是整数的范围),快于任何比较排序算法。
    • 基数排序
      • 时间复杂度:
        • 最坏情况运行时间:$O((n+k)d)$。
        • 最好情况运行时间:$O((n+k)d)$。
      • 稳定性:稳定
      • 基本思路:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
        • 基数排序
    • 桶排序
      • 时间复杂度:
        • 最坏情况运行时间:当分布不均匀时,全部元素都分到一个桶中,则 $O(n^2)$,当然也可以将插入排序换成堆排序、快速排序等,这样最坏情况就是 $O(nlgn)$。
        • 最好情况运行时间:$O(n)$
      • 稳定性:稳定
      • 基本思路:工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。
        • 桶排序
      • 桶排序是鸽巢排序的一种归纳结果。
      • 桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法
    • 鸽巢排序
      • 时间复杂度:
        • 最坏时间复杂度:$O(N+n)$。
        • 最好时间复杂度:$O(N+n)$。
      • 基本思路:假设我们要排序的数组为 init_array,设其中最大元素为 Max。额外分配一个长度为 Max 的 int 类型数组 temp[Max],数组中元素初始都为 0,算法开始循环地将 temp 中下标为 init_array[i] 处的元素置一个常数 a(假设为 1);然后从 0 开始扫描数组 init_array,遇到 temp 中值为这个常数 a 的元素时,将其依次存入数组 init_array 中,此时 init_array 中存储的就是已排序的元素。
      • 算法过程:
        1. 对于给定的一组要排序的数组,需要初始化一个空的辅助数组(“鸟巢”),把初始数组中的每个值作为一个 key(“阁子”)。
        2. 遍历初始数组,根据每个值放入辅助数组对应的“阁子”。
        3. 顺序遍历辅助数组,把辅助数组“阁子”中不为空的数放回初始数组中。

动态规划

  • 动态规划
    • 维特比算法
      • 维特比算法是一种动态规划算法用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。
      • 维特比算法
      • 维特比算法2
      • 步骤
        • 找到每一层每一个点的最短路径再算下一层

遍历

  • 深度优先(DFS)
  • 广度优先(BFS)
    • BFS(广度优先搜索)