学习总结

数据结构

数组

哈希表

**哈希表**可以弥补**数组*的一些缺点，所以我们就可以在数组的基础上做一些改动，来实现哈希表。

树

树的种类

无序树

树的任意节点的子节点没有顺序关系。

有序树

树的任意节点的子节点有顺序关系。

字典树

又称单词查找树， Trie树，是一种 树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的 字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符；
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
每个节点的所有子节点包含的字符都不相同。

线索二叉树

在 二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

二叉树

树的任意节点至多包含两棵子树。
二叉树遍历:
二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的访问次序可以分为四种：
前序遍历 中序遍历 后序遍历 层次遍历

霍夫曼树

带权路径最短的二叉树称为哈夫曼树或最优二叉树。

二叉查找树（二叉搜索树、二叉排序树、BST）[这几个都是别名]

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是BST。

AVL树

在计算机科学中， AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为 高度平衡树。增加和删除可能需要通过一次或多次 树旋转来重新平衡这个树。
AVL树本质上还是一棵二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
使用场景：
AVL树适合用于插入删除次数比较少，但查找多的情况。
也在Windows进程地址空间管理中得到了使用
旋转的目的是为了降低树的高度，使其平衡

红黑树

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
使用场景：
红黑树多用于搜索,插入,删除操作多的情况下
红黑树应用比较广泛：
1. 广泛用在C++的STL中。map和set都是用红黑树实现的。
2. 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。
3.epoll在内核中的实现，用红黑树管理事件块
4.nginx中，用红黑树管理timer等

伸展树

伸展树（Splay Tree），也叫分裂树，是一种 二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由 丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。
在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。

替罪羊树

替罪羊树是 计算机科学中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平摊最坏 时间复杂度是 O(log n)，搜索节点的最坏时间复杂度是O(log n)。
在非平衡的 二叉搜索树中，每次操作以后检查操作路径，找到最高的满足max(size(son_L),size(son_R))>alpha*size(this)的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。替罪羊树替罪羊树是一棵自平衡二叉搜索树，由ArneAndersson提出。替罪羊树的主要思想就是将不平衡的树压成一个序列,然后暴力重构成一颗平衡的树。

B-tree（B树）

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故 内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。

B树(B-Tree)是一种自平衡的树,它是一种多路搜索树（并不是二叉的），能够保证数据有序。同时它还保证了在查找、插入、删除等操作时性能都能保持在O(logn)，为大块数据的读写操作做了优化,同时它也可以用来描述外部存储(支持对保存在磁盘或者网络上的符号表进行外部查找)

B+树

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
(1)每个结点至多有m个子女；
(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。
更适合文件索引系统
原因： 增删文件（节点）时，效率更高，因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率
使用场景：
文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：
Windows：HPFS 文件系统
Mac：HFS，HFS+ 文件系统
Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
数据库：ORACLE，MYSQL，SQLSERVER 等中
B树：有序数组+平衡多叉树
B+树：有序数组链表+平衡多叉树

B*树

B 树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

树的遍历

先序遍历：FCADBEHGM
后序遍历：ABDCHMGEF
中序遍历：ACBDFHEMG
层序遍历：FCEADHGBM，层序遍历一般很少用。

先序遍历：先访问根节点，再访问左子树，最后访问右子树。

后序遍历：先左子树，再右子树，最后根节点。

中序遍历：先左子树，再根节点，最后右子树。

层序遍历：每一层从左到右访问每一个

算法

复杂度分析

时间复杂度：

空间复杂度：

算法题

数组

链表

两两翻转链表

树

二叉树的序列化和反序列化

排序

递归

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

广度优先算法的核心思想是：
从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。
这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。

计算机网络

网络模型（七层|五层|四层）

七层模型从上到下依次是：

• 应用层：协议有：HTTP FTP TFTP SMTP SNMP DNS TELNET HTTPS POP3 DHCP
• 表示层：数据的表示、安全、压缩。格式有，JPEG、ASCll、DECOIC、加密格式等
• 会话层：建立、管理、终止会话。对应主机进程，指本地主机与远程主机正在进行的会话
• 传输层：定义传输数据的协议端口号，以及流控和差错校验。协议有：TCP UDP，数据包一旦离开网卡即进入网络传输层
• 网络层：进行逻辑地址寻址，实现不同网络之间的路径选择。协议有：ICMP IGMP IP（IPV4 IPV6） ARP RARP
• 数据链路层：建立逻辑连接、进行硬件地址寻址、差错校验等功能。将比特组合成字节进而组合成帧，用MAC地址访问介质，错误发现但不能纠正。
• 物理层：建立、维护、断开物理连接。

除了标准的OSI七层模型以外，常见的网络层次划分还有TCP/IP四层协议以及TCP/IP五层协议

TUP & UDP

用户数据报协议 UDP（User Datagram Protocol）

是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信。
特性
- 无连接：不需要先建立连接（如三次握手）
- 尽最大努力交付（不可靠交付）
- 面向报文。对于应用层交付下来的报文，不作另外的处理，只添加了头部就向下交付到网络层。因此，UDP报文数据不能太长也不能太短，会造成IP分片过多或资源浪费。
- 没有拥塞控制。 不会因网络的堵塞导致发送的速率降低。因此会用在很多的实时应用中。
- 首部开销小，只有8字节。

传输控制协议 TCP（Transmission Control Protocol）

是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块），每一条 TCP 连接只能是点对点的（一对一）。
特性
- 面向连接，要经过三次握手确定端对端都能接收和发送消息
- 可靠交付。保证无差错、不丢失、不重复、不乱序
- 双全工通信。也就是每一端都有发送和接收缓冲区，应用层在自己合适的时候对缓冲区进行读写
- 面向字节流。流 其实就是一个数据序列，在这里连续的消息是连在一起的，需要接收方知道怎么去辨别。
首部固定部分各字段意义如下：

1） 源端口和目的端口       各占2个字节，分别写入源端口和目的端口。

2） 序号              占4字节。序号范围是【0，2^32 - 1】，共2^32（即4294967296）个序号。序号增加到2^32-1后，下一个序号就又回到0。也就是说，序号使用mod 2^32运算。TCP是面向字节流的。在一个TCP连接中传送的字节流中的每一个字节都按顺序编号。整个要传送的字节流的起始序号必须在连接建立时设置。首部中的序号字段值则是指的是本报文段所发送的数据的第一个字节的序号。例如，一报文段的序号是301，而接待的数据共有100字节。这就表明：本报文段的数据的第一个字节的序号是301，最后一个字节的序号是400。显然，下一个报文段（如果还有的话）的数据序号应当从401开始，即下一个报文段的序号字段值应为401。这个字段的序号也叫“报文段序号”。

3） 确认号      占4字节，是期望收到对方下一个报文段的第一个数据字节的序号。例如，B正确收到了A发送过来的一个报文段，其序号字段值是501，而数据长度是200字节（序号501~700），这表明B正确收到了A发送的到序号700为止的数据。因此，B期望收到A的下一个数据序号是701，于是B在发送给A的确认报文段中把确认号置为701。注意，现在确认号不是501，也不是700，而是701。

       总之：若确认号为= N，则表明：到序号N-1为止的所有数据都已正确收到。

4） 数据偏移         占4位，它指出TCP报文段的数据起始处距离TCP报文段的起始处有多远。这个字段实际上是指出TCP报文段的首部长度。由于首部中还有长度不确定的选项字段，因此数据偏移字段是必要的，但应注意，“数据偏移”的单位是32位字（即以4字节的字为计算单位）。由于4位二进制数能表示的最大十进制数字是15，因此数据偏移的最大值是60字节，这也是TCP首部的最大字节（即选项长度不能超过40字节）。

5） 保留          占6位，保留为今后使用，但目前应置为0 。

下面有6个控制位，用来说明本报文段的性质。
6） 紧急URG（URGent）        当URG=1时，表明紧急指针字段有效。它告诉系统此报文段中有紧急数据，应尽快发送（相当于高优先级的数据），而不要按原来的排队顺序来传送。例如，已经发送了很长的一个程序要在远地的主机上运行。但后来发现了一些问题，需要取消该程序的运行，因此用户从键盘发出中断命令。如果不使用紧急数据，那么这两个字符将存储在接收TCP的缓存末尾。只有在所有的数据被处理完毕后这两个字符才被交付接收方的应用进程。这样做就浪费了很多时间。

       当URG置为1时，发送应用进程就告诉发送方的TCP有紧急数据要传送。于是发送方TCP就把紧急数据插入到本报文段数据的最前面，而在紧急数据后面的数据仍然是普通数据。这时要与首部中紧急指针（Urgent Pointer）字段配合使用。

7） 确认ACK（ACKnowledgment）      仅当ACK = 1时确认号字段才有效，当ACK = 0时确认号无效。TCP规定，在连接建立后所有的传送的报文段都必须把ACK置为1。

8） 推送 PSH（PuSH）    当两个应用进程进行交互式的通信时，有时在一端的应用进程希望在键入一个命令后立即就能收到对方的响应。在这种情况下，TCP就可以使用推送（push）操作。这时，发送方TCP把PSH置为1，并立即创建一个报文段发送出去。接收方TCP收到PSH=1的报文段，就尽快地（即“推送”向前）交付接收应用进程。而不用再等到整个缓存都填满了后再向上交付。

9） 复位RST（ReSeT）       当RST=1时，表名TCP连接中出现了严重错误（如由于主机崩溃或其他原因），必须释放连接，然后再重新建立传输连接。RST置为1还用来拒绝一个非法的报文段或拒绝打开一个连接。

10） 同步SYN（SYNchronization）       在连接建立时用来同步序号。当SYN=1而ACK=0时，表明这是一个连接请求报文段。对方若同意建立连接，则应在响应的报文段中使SYN=1和ACK=1，因此SYN置为1就表示这是一个连接请求或连接接受报文。

11） 终止FIN（FINis，意思是“完”“终”）          用来释放一个连接。当FIN=1时，表明此报文段的发送发的数据已发送完毕，并要求释放运输连接。

12） 窗口             占2字节。窗口值是【0，2^16-1】之间的整数。窗口指的是发送本报文段的一方的接受窗口（而不是自己的发送窗口）。窗口值告诉对方：从本报文段首部中的确认号算起，接收方目前允许对方发送的数据量（以字节为单位）。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。总之，窗口值作为接收方让发送方设置其发送窗口的依据。

      例如，发送了一个报文段，其确认号是701，窗口字段是1000.这就是告诉对方：“从701算起，我（即发送方报文段的一方）的接收缓存空间还可接受1000个字节数据（字节序号是701~1700），你在给我发数据时，必须考虑到这一点。”

      总之：窗口字段明确指出了现在允许对方发送的数据量。窗口值经常在动态变化。

13） 检验和       占2字节。检验和字段检验的范围包括首部和数据这两部分。和UDP用户数据报一样，在计算检验和时，要在TCP报文段的前面加上12字节的伪首部。伪首部的格式和UDP用户数据报的伪首部一样。但应把伪首部第4个字段中的17改为6（TCP的协议号是6）；把第5字段中的UDP中的长度改为TCP长度。接收方收到此报文段后，仍要加上这个伪首部来计算检验和。若使用TPv6,则相应的伪首部也要改变。

14） 紧急指针            占2字节。紧急指针仅在URG=1时才有意义，它指出本报文段中的紧急数据的字节数（紧急数据结束后就是普通数据） 。因此，在紧急指针指出了紧急数据的末尾在报文段中的位置。当所有紧急数据都处理完时，TCP就告诉应用程序恢复到正常操作。值得注意的是，即使窗口为0时也可以发送紧急数据。

15） 选项       长度可变，最长可达4字节。当没有使用“选项”时，TCP的首部长度是20字节。

TCP和UDP的区别

TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接。

TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付。

Tcp通过校验和，重传控制，序号标识，滑动窗口、确认应答实现可靠传输。如丢包时的重发控制，还可以对次序乱掉的分包进行顺序控制。

UDP具有较好的实时性，工作效率比TCP高，适用于对高速传输和实时性有较高的通信或广播通信。

每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信。

TCP对系统资源要求较多，UDP对系统资源要求较少。

TCP 的三次握手和四次挥手

TCP 是一种面向连接的单播协议，在发送数据前，通信双方必须在彼此间建立一条连接。所谓的“连接”，其实是客户端和服务器的内存里保存的一份关于对方的信息，如 IP 地址、端口号等。

TCP 可以看成是一种字节流，它会处理 IP 层或以下的层的丢包、重复以及错误问题。在连接的建立过程中，双方需要交换一些连接的参数。这些参数可以放在 TCP 头部。

TCP 提供了一种可靠、面向连接、字节流、传输层的服务，采用三次握手建立一个连接；采用四次挥手来关闭一个连接。

说一下 TCP 粘包是怎么产生的？

①. 发送方产生粘包
采用TCP协议传输数据的客户端与服务器经常是保持一个长连接的状态（一次连接发一次数据不存在粘包），双方在连接不断开的情况下，可以一直传输数据；但当发送的数据包过于的小时，那么TCP协议默认的会启用Nagle算法，将这些较小的数据包进行合并发送（缓冲区数据发送是一个堆压的过程）；这个合并过程就是在发送缓冲区中进行的，也就是说数据发送出来它已经是粘包的状态了。
②. 接收方产生粘包
接收方采用TCP协议接收数据时的过程是这样的：数据到底接收方，从网络模型的下方传递至传输层，传输层的TCP协议处理是将其放置接收缓冲区，然后由应用层来主动获取（C语言用recv、read等函数）；这时会出现一个问题，就是我们在程序中调用的读取数据函数不能及时的把缓冲区中的数据拿出来，而下一个数据又到来并有一部分放入的缓冲区末尾，等我们读取数据时就是一个粘包。（放数据的速度 > 应用层拿数据速度） 

TCP如何保证可靠性

1. 校验和
TCP检验和的计算与UDP一样，在计算时要加上12byte的伪首部，检验范围包括TCP首部及数据部分，但是UDP的检验和字段为可选的，而TCP中是必须有的。计算方法为：在发送方将整个报文段分为多个16位的段，然后将所有段进行反码相加，将结果存放在检验和字段中，接收方用相同的方法进行计算，如最终结果为检验字段所有位是全1则正确（UDP中也是全为1则正确），否则存在错误。

2. 确认应答与序列号
TCP将每个数据包都进行了编号，这就是序列号。
序列号的作用：
a、保证可靠性（当接收到的数据总少了某个序号的数据时，能马上知道）
b、保证数据的按序到达
c、提高效率，可实现多次发送，一次确认
d、去除重复数据
数据传输过程中的确认应答处理、重发控制以及重复控制等功能都可以通过序列号来实现

TCP通过确认应答机制实现可靠的数据传输。在TCP的首部中有一个标志位——ACK，此标志位表示确认号是否有效。接收方对于按序到达的数据会进行确认，当标志位ACK=1时确认首部的确认字段有效。进行确认时，确认字段值表示这个值之前的数据都已经按序到达了。而发送方如果收到了已发送的数据的确认报文，则继续传输下一部分数据；而如果等待了一定时间还没有收到确认报文就会启动重传机制。

序列号错误示意图
3. 超时重传
当报文发出后在一定的时间内未收到接收方的确认，发送方就会进行重传（通常是在发出报文段后设定一个闹钟，到点了还没有收到应答则进行重传）。
一种情况是发送包丢失了，其基本过程如下：

发送包丢失导致的超时
另一种情况是ACK 丢失，过程如下：


ACK 丢失导致的超时
当接收方接收到重复的数据时就将其丢掉，重新发送ACK。而要识别出重复的数据，前面提到的序列号就起作用了。

重传时间的确定：
重传时间的确定：报文段发出到收到应答中间有一个报文段的往返时间RTT，显然超时重传时间RTO会略大于这个RTT，TCP会根据网络情况动态的计算RTT，即RTO是不断变化的。在Linux中，超时以500ms为单位进行控制，每次判定超时重发的超时时间都是500ms的整数倍。其规律为：如果重发一次仍得不到应答，就等待2500ms后再进行重传，如果仍然得不到应答就等待4500ms后重传，依次类推，以指数形式递增，重传次数累计到一定次数后，TCP认为网络或对端主机出现异常，就会强行关闭连接。

4. 连接管理
连接管理机制即TCP建立连接时的三次握手和断开连接时的四次挥手。

5. 流量控制
接收端处理数据的速度是有限的，如果发送方发送数据的速度过快，导致接收端的缓冲区满，而发送方继续发送，就会造成丢包，继而引起丢包重传等一系列连锁反应。
因此TCP支持根据接收端的处理能力，来决定发送端的发送速度，这个机制叫做流量控制。
在TCP报文段首部中有一个16位窗口长度，当接收端接收到发送方的数据后，在应答报文ACK中就将自身缓冲区的剩余大小，放入16窗口大小中。这个大小随数据传输情况而变，窗口越大，网络吞吐量越高，而一旦接收方发现自身的缓冲区快满了，就将窗口设置为更小的值通知发送方。如果缓冲区满，就将窗口置为0，发送方收到后就不再发送数据，但是需要定期发送一个窗口探测数据段，使接收端把窗口大小告诉发送端。


流量控制示意图
注意：窗口大小不受16位窗口大小限制，在TCP首部40字节选项中还包含一个窗口扩大因子M，实际窗口大小是窗口字段的值左移M位。

6. 拥塞控制
流量控制解决了两台主机之间因传送速率而可能引起的丢包问题，在一方面保证了TCP数据传送的可靠性。然而如果网络非常拥堵，此时再发送数据就会加重网络负担，那么发送的数据段很可能超过了最大生存时间也没有到达接收方，就会产生丢包问题。
为此TCP引入慢启动机制，先发出少量数据，就像探路一样，先摸清当前的网络拥堵状态后，再决定按照多大的速度传送数据。
此处引入一个拥塞窗口：
发送开始时定义拥塞窗口大小为1；每次收到一个ACK应答，拥塞窗口加1；而在每次发送数据时，发送窗口取拥塞窗口与接送段接收窗口最小者。
慢启动：在启动初期以指数增长方式增长；设置一个慢启动的阈值，当以指数增长达到阈值时就停止指数增长，按照线性增长方式增加；线性增长达到网络拥塞时立即“乘法减小”，拥塞窗口置回1，进行新一轮的“慢启动”，同时新一轮的阈值变为原来的一半。
“慢启动”机制可用图表示：
拥塞窗口调整

关于拥塞控制的算法细节，可以参考4. TCP 的那些事儿（下）
6.1. 慢启动
1）连接建好的开始先初始化cwnd = 1，表明可以传一个MSS大小的数据。

2）每当收到一个ACK，cwnd++; 呈线性上升

3）每当过了一个RTT，cwnd = cwnd*2; 呈指数让升

4）还有一个ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”（后面会说这个算法）

6.2. 拥塞避免
1）收到一个ACK时，cwnd = cwnd + 1/cwnd

2）当每过一个RTT时，cwnd = cwnd + 1

这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。很明显，是一个线性上升的算法。

6.3. 快重传
当出现ack超时的时候，需要重传数据包。

sshthresh = cwnd /2
cwnd 重置为 1
进入慢启动过程
TCP认为这种情况太糟糕，反应也很强烈。
快速重传在收到3个duplicate ACK时就开启重传(三次 ack 就认为丢包的原理见关于TCP乱序和重传的问题、TCP 快速重传为什么是三次冗余 ACK)，而不用等到RTO超时。

TCP Reno的实现是：

cwnd = cwnd /2
sshthresh = cwnd
进入快速恢复算法——Fast Recovery
6.4. 快恢复
快速恢复
快速重传和快速恢复算法一般同时使用。快速恢复算法是认为，你还有3个Duplicated Acks说明网络也不那么糟糕，所以没有必要像RTO超时那么强烈。 注意，正如前面所说，进入Fast Recovery之前，cwnd 和 sshthresh已被更新：

cwnd = cwnd /2
sshthresh = cwnd
然后，真正的Fast Recovery算法如下：
cwnd = sshthresh + 3 * MSS （3的意思是确认有3个数据包被收到了）
重传Duplicated ACKs指定的数据包
如果再收到 duplicated Acks，那么cwnd = cwnd +1
如果收到了新的Ack，那么，cwnd = sshthresh ，然后就进入了拥塞避免的算法了。
如果你仔细思考一下上面的这个算法，你就会知道，上面这个算法也有问题，那就是——它依赖于3个重复的Acks。注意，3个重复的Acks并不代表只丢了一个数据包，很有可能是丢了好多包。但这个算法只会重传一个，而剩下的那些包只能等到RTO超时，于是，进入了恶梦模式——超时一个窗口就减半一下，多个超时会超成TCP的传输速度呈级数下降，而且也不会触发Fast Recovery算法了。

通常来说，正如我们前面所说的，SACK或D-SACK的方法可以让Fast Recovery或Sender在做决定时更聪明一些，但是并不是所有的TCP的实现都支持SACK（SACK需要两端都支持），所以，需要一个没有SACK的解决方案。而通过SACK进行拥塞控制的算法是FACK（可参见关于TCP乱序和重传的问题）

HTTP & HTTPS

HTTP是什么

HTTP（超文本传输协议）是一个基于请求与响应模式的、无状态的、应用层的协议，常基于TCP的连接方式

HTTP 常见的状态码，有哪些？

HTTPS是什么

基于HTTP的缺点
- 通信使用明文不加密，内容可能被窃听
- 不验证通信方身份，可能遭到伪装
- 无法验证报文完整性，可能被篡改
HTTPS就是HTTP加上SSL加密处理（一般是SSL安全通信线路）+认证+完整性保护

操作系统

CPU

进程、线程、协程的概念

进程：

是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竞争计算机系统资源的基本单位。

线程：

是进程的一个执行单元，是进程内科调度实体。比进程更小的独立运行的基本单位。线程也被称为轻量级进程。

协程：

是一种比线程更加轻量级的存在。一个线程也可以拥有多个协程。其执行过程更类似于子例程，或者说不带返回值的函数调用。

进程和线程的区别

地址空间：线程共享本进程的地址空间，而进程之间是独立的地址空间。
资源：线程共享本进程的资源如内存、I/O、cpu等，不利于资源的管理和保护，而进程之间的资源是独立的，能很好的进行资源管理和保护。
健壮性：多进程要比多线程健壮，一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。
执行过程：每个进程有一个程序运行的入口、顺序执行序列和程序入口，执行开销大。线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，执行开销小
切换时：进程切换时，消耗的资源大，效率高。所以涉及到频繁的切换时，使用线程要好于进程。同样如果要求同时进行并且又要共享某些变量的并发操作，只能用线程不能用进程

协程和线程的区别

协程避免了无意义的调度，由此可以提高性能，但程序员必须自己承担调度的责任。同时，协程也失去了标准线程使用多CPU的能力。
线程
    相对独立

    有自己的上下文

    切换受系统控制；

协程
    相对独立

    有自己的上下文

    切换由自己控制，由当前协程切换到其他协程由当前协程来控制。

何时使用多进程，何时使用多线程？

对资源的管理和保护要求高，不限制开销和效率时，使用多进程。

要求效率高，频繁切换时，资源的保护管理要求不是很高时，使用多线程。

为什么会有线程？

每个进程都有自己的地址空间，即进程空间，在网络或多用户换机下，一个服务器通常需要接收大量不确定数量用户的并发请求，为每一个请求都创建一个进程显然行不通（系统开销大响应用户请求效率低），因此操作系统中线程概念被引进。

Liunx

Linux什么命令可以改变文件的属性？

Linux chattr命令用于改变文件属性。

这项指令可改变存放在ext2文件系统上的文件或目录属性，这些属性共有以下8种模式：

a：让文件或目录仅供附加用途。
b：不更新文件或目录的最后存取时间。
c：将文件或目录压缩后存放。
d：将文件或目录排除在倾倒操作之外。
i：不得任意更动文件或目录。
s：保密性删除文件或目录。
S：即时更新文件或目录。
u：预防意外删除。

Linux哪个命令可以查看线程？

方法一：PS

在ps命令中，“-T”选项可以开启线程查看。下面的命令列出了由进程号为<pid>的进程创建的所有线程。

1.$ ps -T -p <pid>

方法二： Top

top命令可以实时显示各个线程情况。要在top输出中开启线程查看，请调用top命令的“-H”选项，该选项会列出所有Linux线程。在top运行时，你也可以通过按“H”键将线程查看模式切换为开或关。

1.$ top -H

要让top输出某个特定进程<pid>并检查该进程内运行的线程状况：

2.$ top -H -p <pid>

方法三： Htop

一个对用户更加友好的方式是，通过htop查看单个进程的线程，它是一个基于ncurses的交互进程查看器。该程序允许你在树状视图中监控单个独立线程。

要在htop中启用线程查看，请开启htop，然后按<F2>来进入htop的设置菜单。选择“设置”栏下面的“显示选项”，然后开启“树状视图”和“显示自定义线程名”选项。按<F10>退出设置。

Java

面向对象

面向对象的三大特征

封装：封装就是隐藏对象的属性和实现细节，仅对外公开接口，控制在程序中属性的读和修改的访问级别，将数据与操作数据的源代码进行结合，形成“类”。
继承：子类从父类继承方法，使得子类具有父类相同的行为。
多态：是指一个类（实例对象）的相同方法在不同情形有不同表现形式。多态机制使具有不同内部结构的对象可以共享相同的外部接口。

五大基本原则

1、接口隔离原则（ISP）
2、依赖倒置原则（DIP）
3、里氏替换原则（LSP）
4、开放封闭原则（OCP）
5、单一职责原则（SRP）

重写和重载的区别

重写:重写（Override）是父类与子类之间多态性的一种表现。如果在子类中定义某方法与其父类有相同的名称和参数，我们说该方法被重写 (Override)。子类的对象使用这个方法时，将调用子类中的定义，对它而言，父类中的定义如同被“屏蔽”了。
重载：重载（Overload）是一个类中多态性的一种表现。如果在一个类中定义了多个同名的方法，它们参数列表不同，则称为方法的重载(Overload)
区别：重载实现于一个类中;重写实现于子类中。
重载(Overload)：是一个类中多态性的一种表现，指同一个类中不同的函数使用相同的函数名，但是函数的参数个数或类型不同。可以有不同的返回类型;可以有不同的访问修饰符;可以抛出不同的异常。调用的时候根据函数的参数来区别不同的函数。
重写（Override): 是父类与子类之间的多态性，是子类对父类函数的重新实现。函数名和参数与父类一样，子类与父类函数体内容不一样。子类返回的类型必须与父类保持一致；子类方法访问修饰符的限制一定要大于父类方法的访问修饰（public>protected>default>private）；子类重写方法一定不能抛出新的检查异常或者比被父类方法申明更加宽泛的检查型异常。

关键字

String、StringBuffer和StringBuilder类的区别

String 和 StringBuffer、StringBuilder 的区别在于 String 声明的是不可变的对象，每次操作都会生成新的 String 对象，然后将指针指向新的 String 对象，而 StringBuffer、StringBuilder 可以在原有对象的基础上进行操作，所以在经常改变字符串内容的情况下最好不要使用 String。
StringBuffer 和 StringBuilder 最大的区别在于，StringBuffer 是线程安全的，而 StringBuilder 是非线程安全的，但 StringBuilder 的性能却高于 StringBuffer，所以在单线程环境下推荐使用 StringBuilder，多线程环境下推荐使用 StringBuffer。
一、可变与不可变
String类是一个不可变类，即创建String对象后，该对象中的字符串是不可改变的，直到这个对象被销毁。StringBuffer与StringBuilder都继承自AbstractStringBuilder类，在AbstractStringBuilder中也是使用字符数组保存字符串，是可变类。

由于String是可变类，适合在需要被共享的场合中使用，当一个字符串经常被修改时，最好使用StringBuffer实现。如果用String保存一个经常被修改的字符串，该字符串每次修改时都会创建新的无用的对象，这些无用的对象会被垃圾回收器回收，会影响程序的性能，不建议这么做。
二、初始化方式
当创建String对象时，可以利用构造方法String str = new String("Java")的方式来对其进行初始化，也可以直接用赋值的方式String s = "Java"来初始化。而StringBuffer只能使用构造方法StringBuffer sb = new StringBuffer("hello")的方式初始化。
三、字符串修改方式
String字符串修改方法是首先创建一个StringBuffer，其次调用StringBuffer的append方法，最后调用StringBuffer的toString()方法把结果返回，示例代码如下：
四、是否实现了equals和hashCode方法
String实现了equals()方法和hashCode()方法，new String("java").equals(new String("java"))的结果为true；

而StringBuffer没有实现equals()方法和hashCode()方法，因此，new StringBuffer("java").equals(new StringBuffer("java"))的结果为false，将StringBuffer对象存储进Java集合类中会出现问题。
五、是否线程安全
StringBuffer与StringBuilder都提供了一系列插入、追加、改变字符串里的字符序列的方法，它们的用法基本相同，只是StringBuilder是线程不安全的，StringBuffer是线程安全的，。如果只是在单线程中使用字符串缓冲区，则StringBuilder的效率会高些，但是当多线程访问时，最好使用StringBuffer。

综上，在执行效率方面，StringBuilder最高，StringBuffer次之，String最低，对于这种情况，一般而言，如果要操作的数量比较小，应优先使用String类；如果是在单线程下操作大量数据，应优先使用StringBuilder类；如果是在多线程下操作大量数据，应优先使用StringBuilder类。

final关键字特性

final关键字可以申明成员变量、方法、类、本地变量。一旦将引用声明为final，将无法再改变这个引用，final关键字还能保证内存同步。
final变量：
    final变量有成员变量或者是本地变量(方法内的局部变量)，在类成员中final经常和static一起使用，作为类常量使用。其中类常量必须在声明时初始化，final成员常量可以在构造函数初始化。
final方法：
    final方法表示该方法不能被子类的方法重写，将方法声明为final，在编译的时候就已经静态绑定了，不需要在运行时动态绑定。final方法调用时使用的是invokespecial指令。
final类：
    final类不能被继承，final类中的方法默认也会是final类型的，java中的String类和Integer类都是final类型的。
final方法的好处:

    提高了性能，JVM在常量池中会缓存final变量
    final变量在多线程中并发安全，无需额外的同步开销
    final方法是静态编译的，提高了调用速度
    final类创建的对象是只可读的，在多线程可以安全共享
final关键字的知识点：

    final成员变量必须在声明的时候初始化或者在构造器中初始化，否则就会报编译错误。final变量一旦被初始化后不能再次赋值。
    本地变量必须在声明时赋值。 因为没有初始化的过程
    在匿名类中所有变量都必须是final变量。
    final方法不能被重写, final类不能被继承
    接口中声明的所有变量本身是final的。类似于匿名类
    final和abstract这两个关键字是反相关的，final类就不可能是abstract的。
    final方法在编译阶段绑定，称为静态绑定(static binding)。
    将类、方法、变量声明为final能够提高性能，这样JVM就有机会进行估计，然后优化。

JVM

Jvm的内存结构

（线程私有）
1、程序计数器：它可以看作是当前线程所执行的字节码的行号指示器。
2、虚拟机栈：它描述的是java方法执行的内存模型，每个方法执行的同时都会创建一个栈帧（Stack Frame）用于存储局部变量表、操作数栈、动态链接、方法出口等信息。
每当一个方法执行完成时，该栈帧就会弹出栈帧的元素作为这个方法的返回值，并且清除这个栈帧，Java栈的栈顶的栈帧就是当前正在执行的活动栈，也就是当前正在执行的方法。
3、本地方法栈：本地方法栈和虚拟机栈所发挥的作用是很相似的，它们之间的区别不过是虚拟机栈为虚拟机执行Java方法（字节码）服务，而本地方法栈则为虚拟机使用到的Native方法服务。
（线程共享）
4、堆：它存储着几乎所有的实例对象，堆由垃圾收集器自动回收，堆区由各子线程共享使用；通过参数-Xms设定初始值、-Xmx设定最大值
5、方法区：方法区是被所有线程共享的内存区域，用来存储已被虚拟机加载的类信息、常量池、静态变量、JIT（just in time,即时编译技术）编译后的代码等数据。

Java的堆内存划分

1、堆内存为了配合垃圾回收划分了不同的区域
2、Java的堆内存基于Generation算法（Generational Collector）划分为新生代、年老代和持久代。
3、新生代又被进一步划分为Eden和Survivor区，最后Survivor由FromSpace（Survivor0）和ToSpace（Survivor1）组成。

Java中的对象引用

1、强引用：如“Object obj = new Object（）”，这类引用是Java程序中最普遍的。只要强引用还存在，垃圾收集器就永远不会回收掉被引用的对象。
2、软引用：它用来描述一些可能还有用，但并非必须的对象。在系统内存不够时，这类引用关联的对象将被垃圾收集器回收。JDK1.2之后提供了SoftReference类来实现软引用
3、弱引用：它也是用来描述非须对象的，但它的强度比软引用更弱些，被弱引用关联的对象只能生存到下一次垃圾收集发生之前。
         当垃圾收集器工作时，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。在JDK1.2之后，提供了WeakReference类来实现弱引用。
4、虚引用：最弱的一种引用关系，完全不会对其生存时间构成影响，也无法通过虚引用来取得一个对象实例。
         为一个对象设置虚引用关联的唯一目的是希望能在这个对象被收集器回收时收到一个系统通知。JDK1.2之后提供了PhantomReference类来实现虚引用。

垃圾回收算法

1、引用计数算法：堆中的每个对象都有一个引用计数器。当一个对象被创建并初始化赋值后，该变量计数设置为1。每当有一个地方引用它时，计数器值就加1。
              当引用失效时（一个对象的某个引用超过了生命周期（出作用域后）或者被设置为一个新值时），计数器值就减1。
              任何引用计数为0的对象可以被当作垃圾收集。当一个对象被垃圾收集时，它引用的任何对象计数减1。
              优点：引用计数收集器执行简单，判定效率高，交织在程序运行中。对程序不被长时间打断的实时环境比较有利（OC的内存管理使用该算法）。
            缺点： 难以检测出对象之间的循环引用。同时，引用计数器增加了程序执行的开销。所以Java语言并没有选择这种算法进行垃圾回收。
2、根搜索算法： 通过一系列名为“GC Roots”的对象作为起始点，寻找对应的引用节点。
             找到这些引用节点后，从这些节点开始向下继续寻找它们的引用节点。
             搜索所走过的路径称为引用链，当一个对象到GC Roots没有任何引用链相连时，就证明此对象是不可用的。
        Java和C#中都是采用根搜索算法来判定对象是否存活的。

GC Roots有哪些

（1）虚拟机栈中引用的对象（栈帧中的本地变量表）；

（2）方法区中的常量引用的对象；

（3）方法区中的类静态属性引用的对象；

（4）本地方法栈中JNI（Native方法）的引用对象。

（5）活跃线程。

回收垃圾对象内存的算法

1、标记—清除法：
2、标记—整理法：
3、复制算法：该算法的提出是为了克服句柄的开销和解决堆碎片的垃圾回收。它将内存按容量分为大小相等的两块，每次只使用其中的一块（对象面），当这一块的内存用完了，就将还存活着的对象复制到另外一块内存上面（空闲面），然后再把已使用过的内存空间一次清理掉。
4、Adaptive算法：在特定的情况下，一些垃圾收集算法会优于其它算法。基于Adaptive算法的垃圾收集器就是监控当前堆的使用情况，并将选择适当算法的垃圾收集器。

垃圾回收机制（GC）

垃圾回收(Garbage Collection)是Java虚拟机(JVM)提供的一种用于在空闲时间不定时回收无任何对象引用的对象占据的内存空间的一种机制。
1、新生代GC（Minor GC/Scavenge GC）：发生在新生代的垃圾收集动作。因为Java对象大多都具有朝生夕灭的特性，因此Minor GC非常频繁(不一定等Eden区满了才触发)，一般回收速度也比较快。在新生代中，每次垃圾收集时都会发现有大量对象死去，只有少量存活，因此可选用复制算法来完成收集。
2、老年代GC（Major GC/Full GC）：发生在老年代的垃圾回收动作。Major GC，经常会伴随至少一次Minor GC。由于老年代中的对象生命周期比较长，因此Major GC并不频繁，一般都是等待老年代满了后才进行Full GC，而且其速度一般会比Minor GC慢10倍以上。另外，如果分配了Direct Memory，在老年代中进行Full GC时，会顺便清理掉Direct Memory中的废弃对象。而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用标记—清除算法或标记—整理算法来进行回收。

（1）串行垃圾回收器（Serial Garbage Collector）：串行垃圾回收器通过持有应用程序所有的线程进行工作。它为单线程环境设计，只使用一个单独的线程进行垃圾回收，通过冻结所有应用程序线程进行工作，所以可能不适合服务器环境。它最适合的是简单的命令行程序。通过JVM参数-XX:+UseSerialGC可以使用串行垃圾回收器。

（2）并行垃圾回收器（Parallel Garbage Collector）：它是JVM的默认垃圾回收器。与串行垃圾回收器不同，它使用多线程进行垃圾回收。相似的是，当执行垃圾回收的时候它也会冻结所有的应用程序线程。适用于多CPU、对暂停时间要求较短的应用上。可用-XX:+UseParallelGC来强制指定，用-XX:ParallelGCThreads=4来指定线程数。

（3）并发标记扫描垃圾回收器（CMS Garbage Collector）：使用多线程扫描堆内存，标记需要清理的实例并且清理被标记过的实例。相比并行垃圾回收器，并发标记扫描垃圾回收器使用更多的CPU来确保程序的吞吐量。如果我们可以为了更好的程序性能分配更多的CPU，那么并发标记上扫描垃圾回收器是更好的选择相比并发垃圾回收器。通过JVM参数 XX:+USeParNewGC 打开并发标记扫描垃圾回收器。
                                                并发标记垃圾回收器只会在下面两种情况持有应用程序所有线程。
                                                （1）当标记的引用对象在Tenured区域；
                                                （2）在进行垃圾回收的时候，堆内存的数据被并发的改变。
                                                
（4）G1垃圾回收器（G1 Garbage Collector）：  G1收集器是当今收集器技术发展最前沿的成果，它是一款面向服务端应用的收集器，它能充分利用多CPU、多核环境。因此它是一款并行与并发收集器，并且它能建立可预测的停顿时间模型。 G1垃圾回收器适用于堆内存很大的情况，他将堆内存分割成不同的区域，并且并发的对其进行垃圾回收。G1也可以在回收内存之后对剩余的堆内存空间进行压缩。并发扫描标记垃圾回收器在STW情况下压缩内存。G1垃圾回收会优先选择第一块垃圾最多的区域。
通过JVM参数 –XX:+UseG1GC 使用G1垃圾回收器。

GC性能调优

集合

Collection 集合

一、Collection 集合接口
Collection 是最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 的元素, Java不提供直接继承自Collection的类，只提供继承于的子接口(如List和set)。 Collection 接口存储一组不唯一，无序的对象。

1、AbstractCollection

AbstractCollection 是 Java 集合框架中 Collection 接口 的一个直接实现类， Collection 下的大多数子类都继承 AbstractCollection ，比如 List 的实现类, Set的实现类。它实现了一些方法，也定义了几个抽象方法留给子类实现，因此它是一个抽象类。

1.1、AbstractList

AbstractList 继承自 AbstractCollection 抽象类，实现了 List 接口 ，是 ArrayList 和 AbstractSequentiaList 的父类

1.1.1、 AbstractSequentialList

什么是 AbstractSequentialList（ Sequential 相继的，按次序的）AbstractSequentialList 没有什么特别的，这里是为了理解 LinkedList 更容易。AbstractSequentialList 继承自 AbstractList，是 LinkedList 的父类，是 List 接口 的简化版实现。简化在哪儿呢？简化在 AbstractSequentialList 只支持按次序访问，而不像 AbstractList 那样支持随机访问。想要实现一个支持按次序访问的 List的话，只需要继承这个抽象类，然后把指定的抽象方法实现就好了。需要实现的方法：

1.2、AbstractSet

AbstractSet没有提供具有AbstractCollection中的所有方法，并且只重写了equals，hashCode，removeAll三个方法。

1、List 接口

List接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。 List 接口存储一组不唯一，有序（插入顺序）的对象。

1.1、LinkedList

LinkedList 继承自 AbstractSequentialList 接口，同时了还实现了 Deque 接口。

我们知道 ArrayList 是以数组实现的，遍历时很快，但是插入、删除时都需要移动后面的元素，效率略差些。

而LinkedList 是以链表实现的，插入、删除时只需要改变前后两个节点指针指向即可，省事不少。

1.2、ArrayList

ArrayList 是 Java 集合框架中 List接口 的一个实现类。可以说 ArrayList 是我们使用最多的 List 集合，它有以下特点：

• 容量不固定，想放多少放多少（当然有最大阈值，但一般达不到）
• 有序的（元素输出顺序与输入顺序一致）
• 元素可以为 null
• 效率高 size(), isEmpty(), get(), set() iterator(), ListIterator() 方法的时间复杂度都是 O(1)
• add() 添加操作的时间复杂度平均为 O(n) 其他所有操作的时间复杂度几乎都是 O(n)
• 占用空间更小 对比 LinkedList，不用占用额外空间维护链表结构

2、Set 接口

Set 具有与 Collection 完全一样的接口，只是行为上不同，Set 不保存重复的元素。 Set 接口存储一组无序的、不可重复的对象

2.1、SortedSet

继承于Set保存有序的集合。

2.2、HashSet

• HashSet 允许有 null 值。
• HashSet 是无序的，即不会记录插入的顺序。
• HashSet 不是线程安全的， 如果多个线程尝试同时修改 HashSet，则最终结果是不确定的。 须在多线程访问时显式同步对 HashSet 的并发访问。
• HashSet 实现了 Set 接口。

2.3、LinkedHashSet

是HashSet的子类，底层使用了LinkedHashMap，在HashSet的哈希表数据结构基础之上，增加了一个双向链表用来记录元素添加的顺序，能按照添加顺序遍历输出。需要频繁遍历的话效率可能高于HashSet

2.4、 TreeSet

TreeSet是一个有序的集合，它的作用是提供有序的Set集合。它继承了AbstractSet抽象类，实现了NavigableSet，Cloneable，Serializable接口。TreeSet是基于TreeMap实现的，TreeSet的元素支持2种排序方式：自然排序或者根据提供的Comparator进行排序。

3、Queue 队列接口

Queue 继承自 Collection 接口，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。

除了继承 Collection 接口的一些方法，Queue 还添加了额外的 添加、删除、查询操作。

Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问。

3.1、Deque

Deque 是 Double ended queue (双端队列) 的缩写,读音和 deck 一样，蛋壳。

Deque 继承自 Queue，直接实现了它的有 ArrayDeque、ConcurrentLinkedDeque、LinkedBlockingDeque、LinkedList 等。

Deque 支持容量受限的双端队列，也支持大小不固定的。一般双端队列大小不确定。

Deque 接口定义了一些从头部和尾部访问元素的方法。比如分别在头部、尾部进行插入、删除、获取元素。

3.1.1、ArrayDeque

ArrayDeque是Deque接口的一个实现，使用了可变数组，所以没有容量上的限制。

同时，ArrayDeque是线程不安全的，在没有外部同步的情况下，不能再多线程环境下使用。

ArrayDeque是Deque的实现类，可以作为栈来使用，效率高于Stack；

也可以作为队列来使用，效率高于LinkedList。

需要注意的是，ArrayDeque不支持null值。

BitSet

Java平台的BitSet用于存放一个位序列，如果要高效的存放一个位序列，就可以使用位集(BitSet)。由于位集将位包装在字节里，所以使用位集比使用Boolean对象的List更加高效和更加节省存储空间。

集合算法

集合算法

集合框架定义了几种可应用于集合和映射的算法。
这些算法在Collections类中定义为静态方法。 有些方法可能会抛出ClassCastException ，当尝试比较不兼容的类型时会发生这种情况，或者在尝试修改不可修改的集合时发生UnsupportedOperationException 。

迭代器（lterator）

迭代器，使你能够通过循环来得到或删除集合的元素。ListIterator 继承了 Iterator，以允许双向遍历列表和修改元素。

Map集合

二、 Map

Map 接口存储一组键值对象，提供key（键）到value（值）的映射。

1、AbstractMap

AbstractMap 是 Map 接口的的实现类之一，也是 HashMap, TreeMap, ConcurrentHashMap 等类的父类。 AbstractMap 提供了 Map 的基本实现，使得我们以后要实现一个 Map 不用从头开始，只需要继承 AbstractMap, 然后按需求实现/重写对应方法即可。

1.1、HashMap

HashMap 是一个采用哈希表实现的键值对集合，继承自 AbstractMap，实现了 Map 接口 。

HashMap 的特殊存储结构使得在获取指定元素前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率贼高。

当发生 哈希冲突（碰撞）的时候，HashMap 采用 拉链法 进行解决，因此 HashMap 的底层实现是 数组+链表

JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

针对这种情况，JDK 1.8 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题。

HashMap 的特点

• 底层实现是 链表数组，JDK 8 后又加了 红黑树
• 实现了 Map 全部的方法
• key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法
• 允许空键和空值（但空键只有一个，且放在第一位，下面会介绍）
• 元素是无序的，而且顺序会不定时改变
• 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）
• 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）
• 两个关键因子：初始容量、加载因子

1.1.1、LinkedHashMap

LinkedHashMap继承于HashMap，迭代HashMap的顺序并不是HashMap放置的顺序，也就是无序。HashMap的这一缺点往往会带来困扰，因为有些场景，我们期待一个有序的Map。

这个时候，LinkedHashMap就闪亮登场了，它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序。该迭代顺序可以是插入顺序或者是访问顺序。

1.2、ConcurrentHashMap

1.2.1、ConcurrentHashMap 1.7

其实大体的哈希表实现跟 HashMap 没有本质的区别，都是经过 key 的 hash 定位到一个下标，然后获取元素，如果冲突了就用链表相连。

差别就在于引入了一个 Segments 数组。

原理就是先通过 key 的 hash 判断得到 Segment 数组的下标，然后将这个 Segment 上锁，然后再次通过 key 的 hash 得到 Segment 里 HashEntry 数组的下标，下面这步其实就是 HashMap 一致了，所以我说差别就是引入了一个 Segments 数组。

因此可以简化的这样理解：每个 Segment 数组存放的就是一个单独的 HashMap。

如果我们有 6 个 Segment ，那么等于有六把锁，因此共可以有六个线程同时操作这个 ConcurrentHashMap，并发度就是 6，相比于直接将 put 方法上锁，并发度就提高了，这就是分段锁。

具体上锁的方式来源于 Segment ，这个类实际继承了 ReentrantLock，因此它自身具备加锁的功能。

可以看出，1.7 的分段锁已经有了细化锁粒度的概念，它的一个缺陷是 Segment 数组一旦初始化了之后不会扩容，只有 HashEntry 数组会扩容，这就导致并发度过于死板，不能随着数据的增加而提高并发度。

1.2.2、ConcurrentHashMap 1.8

1.8 ConcurrentHashMap 做了更细粒度的锁控制，可以理解为 1.8 HashMap 的数组的每个位置都是一把锁，这样扩容了锁也会变多，并发度也会增加

思想的转变就是把粒度更加细化，我不分段了，我直接把 Node 数组的每个节点分别上一把锁，这样并发度不就更高了吗？

并且 1.8 也不借助于 ReentrantLock 了，直接用 synchronized，这也侧面证明，都 1.8 了 synchronized 优化后的速度已经不下于 ReentrantLock 了

具体实现思路也简单，当塞入一个值的时候，先计算 key 的 hash 后的下标，如果计算到的下标还未有 Node ，那么就通过 cas 塞入新的 Node。如果已经有 node 则通过 synchronized 将这个 node 上锁，这样别的线程就无法访问这个 node 及其之后的所有节点。

然后判断 key 是否相等，相等则是替换 value ，反之则是新增一个 node，这个操作和 HashMap 是一样的。

1.8 的扩容也是有点意思的，它允许协助扩容，也就是多线程扩容。

还有 1.8 的 size 方法和 1.7 也不一样

1.3、HashTable

与HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可为null。Hashtable中的映射不是有序的。

1.4、TreeMap

TreeMap提供了一种以排序顺序存储键/值对的有效方法。它是基于红黑树的NavigableMap实现。继承自 AbstractMap，实现了NavigableMap接口。

1.5、IdentityHashMap

IdentityHashMap与HashMap 都是，继承自 AbstractMap，实现了 Map 接口 。不同的是，其比较键（或值）时，使用引用相等性代替对象相等性。

1.6、WeakHashMap

WeakHashMap与正常的HashMap类似，不同点在WeakHashMap的key是「弱引用」的key。WeakHashMap具有弱引用的特点：随时被回收对象。 继承自 AbstractMap，实现了Map接口。

2.1、Map.Entry的作用

Map.Entry是为了更方便的输出map键值对。一般情况下，要输出Map中的key 和 value 是先得到key的集合keySet()，然后再迭代（循环）由每个key得到每个value。values()方法是获取集合中的所有值，不包含键，没有对应关系。而Entry可以一次性获得这两个值。

2.2、SortedMap
继承于 Map，使 Key 保持在升序排列。

2.2.1、NavigableMap

NavigableMap（java.util.NavigableMap）接口是SortedMap的子接口，但是 NavigableMap接口中新加了几个SortedSet接口中没有的方法，使导航存储在映射中的键和值成为可能。

三、Vector

Vector 类实现了一个动态数组和 ArrayList 很相似，但是该类是同步的，可以用在多线程的情况，该类允许设置默认增长长度，默认扩容方式为原来的2倍。

1、Stack

Stack 继承自 Vector

• Stack 栈是一个 "先进后出"的原理

• Stack 本质是一个List，其具备 List 所有方法

四、Dictionary

Dictionary 类是一个抽象类，用来存储键/值对，作用和Map类相似。

1、HashTable

与HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可为null。Hashtable中的映射不是有序的。

1.1、Properties

Properties 继承于 Hashtable。表示一个持久的属性集.属性列表中每个键及其对应值都是一个字符串。

说说Java的集合类

Java集合从分类上看，有 collection 和 map 两种，前者是存储对象的集合类，后者存储的是键值对（key-value）
Collection

Set
主要功能是保证存储的集合不会重复，至于集体是有序还是无序的，需要看具体的实现类，比如 TreeSet 就是有序的，HashSet 是无序的（所以网上有些说 set 是无序集合是在扯淡）

List
这个很熟悉，具体的实现类有 ArrayList 和 LinkedList，两者的区别在于底层实现不同，前者是数组，后者是双向链表，所以引申出来就是将数组和链表的区别。

数组 VS 链表

数组
数组的内存是连续的，且存储的元素大小是固定的，实现上是基于一个内存地址，然后由于元素固定大小，支持利用下标的直接访问。

具体是通过下标 * 元素大小+内存基地址算出一个访问地址，然后直接访问，所以随机访问的效率很高，O(1)。

而由于要保持内存连续这个特性，不能在内存中间空一块，所以删除中间元素时就需要搬迁元素，需进行内存拷贝，所以说删除的效率不高。

链表
链表的内存不需要连续，它们是通过指针相连，这样对内存的要求没那么高（数组的申请需要一块连续的内存），链表就可以散装内存，不过链表需要额外存储指针，所以总体来说，链表的占用内存会大一些。

且由于是指针相连，所以直接无法随机访问一个元素，必须从头（如双向链表，可尾部）开始遍历，所以随机查找的效率不高，O(n)。

也由于指针相连这个特性，单方面删除的效率高，因为只需要改变指针即可，没有额外的内存拷贝动作(但是要找到这个元素，费劲儿呀，除非你顺序遍历删)。

两者大致的特点就如上所说，再扯地深一点，就要说到 CPU 亲和性问题
空间局部性（spatial locality）：如果一个存储器的位置被引用，那么将来它附近的位置也会被引用。
根据这个原理，就会有预读功能，像 CPU 缓存就会读连续的内存，这样一来如果你本就要遍历数组的，那么你后面的数据就已经被上一次读取前面数据的时候，一块被加载了，这样就是 CPU 亲和性高。
反观链表，由于内存不连续，所以预读不到，所以 CPU 亲和性低。
对了，链表（数组）加了点约束的话，还可以用作栈、队列和双向队列。
像 LinkedList 就可以用来作为栈或者队列使用。

Queue
队列，有序，严格遵守先进先出，就像往常的排队，没啥别的好说的。

常用的实现类就是 LinkedList，没错这玩意还实现了 Queue 接口。

还有一个值得一提的是优先队列，即 PriorityQueue，内部是基于数组构建的，用法就是你自定义一个 comparator ，自己定义对比规则，这个队列就是按这个规则来排列出队的优先级。

HashMap 的实现原理吗

其实就是有个 Entry 数组，Entry 保存了 key 和 value。当你要塞入一个键值对的时候，会根据一个 hash 算法计算 key 的 hash 值，然后通过数组大小 n-1 & hash 值之后，得到一个数组的下标，然后往那个位置塞入这个 Entry。

然后我们知道，hash 算法是可能产生冲突的，且数组的大小是有限的，所以很可能通过不同的 key 计算得到一样的下标，因此为了解决 Entry 冲突的问题，采用了链表法。

在 JDK1.7 及之前链表的插入采用的是头插法，即在链表的头部插入新的 Entry。在 JDK1.8 的时候，改成了尾插法，并且引入了红黑树。

那 JDK 1.8 对 HashMap 有哪些改动？

1、hash 函数的优化
2、扩容 rehash 的优化
3、头插法和尾插法
4、插入与扩容时机的变更
5、引入了红黑树

1、hash 函数的优化

1.7是这样实现的：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
而 1.8 是这样实现的：

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
具体而言就是 1.7 的操作太多了，经历了四次异或，所以 1.8 优化了下，它将 key 的哈希码的高16位和低16位进行了异或，得到的 hash 值同时拥有了高位和低位的特性，这样做得出的码比较均匀，不容易冲突。

这也是 JDK 开发者根据速度、实用性、哈希质量所做的权衡来做的实现：

2、扩容 rehash 的优化

按照我们的思维，正常扩容肯定是先申请一个更大的数组，然后将原数组里面的每一个元素重新 hash 判断在新数组的位置，然后一个一个搬迁过去。
在 1.7 的时候就是这样实现的，然而 1.8 在这里做了优化，关键点就在于数组的长度是 2 的次方，且扩容为 2 倍。

总结一下，1.8 的扩容不需要每个节点重写 hash 算下标，而是通过和老数组长度的**&**计算是否为 0 ，来判断新下标的位置。

3、头插法和尾插法

1.7是头插法，头插法的好处就是插入的时候不需要遍历链表，直接替换成头结点，但是缺点是扩容的时候会逆序，而逆序在多线程操作下可能会出现环，然后就死循环了。
然后 1.8 是尾插法，每次都从尾部插入的话，扩容后链表的顺序还是和之前一致，所以不可能出现多线程扩容成环的情况。

4、插入与扩容时机的变更

1.7 是先判断 put 的键值对是新增还是替换，如果是替换则直接替换，如果是新增会判断当前元素数量是否大于等于阈值，如果超过阈值且命中数组索引的位置已经有元素了，那么就进行扩容。所以 1.7 是先扩容，然后再插入。
而 1.8 则是先插入，然后再判断 size 是否大于阈值，若大于则扩容。

5、引入了红黑树

当链表的长度大于 8 且数组大小大于等于 64 的时候，就把链表转化成红黑树，当红黑树节点小于 6 的时候，又会退化成链表。
为什么 JDK 1.8 要对 HashMap 做红黑树这个改动？
主要是避免 hash 冲突导致链表的长度过长，这样 get 的时候时间复杂度严格来说就不是 O(1) 了，因为可能需要遍历链表来查找命中的 Entry。

hashMap put get过程

hashMap是如何实现扩容

为什么 HashMap 的长度一定要是 2 的 n 次幂？

原因就在于数组下标的计算，由于下标的计算公式用的是 i = (n - 1) & hash，即位运算，一般我们能想到的是 %（取余）计算，但相比于位运算而言，效率比较低，所以推荐用位运算，而要满足上面这个公式，n 的大小就必须是 2 的 n 次幂。

HashMap初始化容量设置问题

要考虑数组长度是2的幂次方、负载因子：只存60个键值对时，2^6 = 64  考虑负载因子 0.75   达到后就会扩容    所以设置  2^7=128 

ConcurrentHashMap Get() 需要加锁吗？

不需要加锁。

保证 put 的时候线程安全之后，get 的时候只需要保证可见性即可，而可见性不需要加锁。

具体是通过Unsafe#getXXXVolatile 和用  volatile 来修饰节点的 val 和 next 指针来实现的。

为什么 ConcurrentHashMap 不支持 key 或者 value 为 null ？

首先， key 为什么也不能为 null ？我不知道，没想明白，可能是作者 lea 佬不喜欢 null 值。

那 value 为什么不能为 null ？

因为在多线程情况下， null 值会产生二义性，因为你不清楚 map 里到底是不存在在这个 key ，还是说被put(key，null)。

多线程

创建线程有哪几种方式？

①. 继承Thread类创建线程类

定义Thread类的子类，并重写该类的run方法，该run方法的方法体就代表了线程要完成的任务。因此把run()方法称为执行体。

创建Thread子类的实例，即创建了线程对象。

调用线程对象的start()方法来启动该线程。

②. 通过Runnable接口创建线程类

定义runnable接口的实现类，并重写该接口的run()方法，该run()方法的方法体同样是该线程的线程执行体。

创建 Runnable实现类的实例，并依此实例作为Thread的target来创建Thread对象，该Thread对象才是真正的线程对象。

调用线程对象的start()方法来启动该线程。

③. 通过Callable和Future创建线程

创建Callable接口的实现类，并实现call()方法，该call()方法将作为线程执行体，并且有返回值。

创建Callable实现类的实例，使用FutureTask类来包装Callable对象，该FutureTask对象封装了该Callable对象的call()方法的返回值。

使用FutureTask对象作为Thread对象的target创建并启动新线程。

调用FutureTask对象的get()方法来获得子线程执行结束后的返回值。

线程池

java里面的线程池的顶级接口是Executor，Executors是一个线程池工厂，提供了很多的工厂方法。而真正的线程池是ExecutorService。

// 创建单一线程的线程池
public static ExecutorService newSingleThreadExecutor();
// 创建固定数量的线程池
public static ExecutorService newFixedThreadPool(int nThreads);
// 创建带缓存的线程池
public static ExecutorService newCachedThreadPool();
// 创建定时调度的线程池
public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize);
// 创建流式（fork-join）线程池
public static ExecutorService newWorkStealingPool();

不使用线程池有哪些坏处

1. 频繁的线程创建和销毁会占用更多的CPU和内存
2. 频繁的线程创建和销毁会对GC产生比较大的压力
3. 线程太多，线程切换带来的开销将不可忽视
4. 线程太少，多核CPU得不到充分利用，是一种浪费

线程池带来的好处

1. 降低资源的消耗。线程本身是一种资源，创建和销毁线程会有CPU开销；创建的线程也会占用一定的内存。
2. 提高任务执行的响应速度。任务执行时，可以不必等到线程创建完之后再执行。
3. 提高线程的可管理性。线程不能无限制地创建，需要进行统一的分配、调优和监控。

线程池构造方法有7个参数。

1. corePoolSize，线程池中的核心线程数
2. maximumPoolSize，线程池中的最大线程数
3. keepAliveTime，空闲时间，当线程池数量超过核心线程数时，多余的空闲线程存活的时间，即：这些线程多久被销毁。
4. unit，空闲时间的单位，可以是毫秒、秒、分钟、小时和天，等等
5. workQueue，等待队列，线程池中的线程数超过核心线程数时，任务将放在等待队列，它是一个BlockingQueue类型的对象
6. threadFactory，线程工厂，我们可以使用它来创建一个线程
7. handler，拒绝策略，当线程池和等待队列都满了之后，需要通过该对象的回调函数进行回调处理

锁

Java对象头与Monitor对象

在JVM中，对象在内存中存储的布局可以分为三个区域，分别是对象头、实例数据以及填充数据。

实例数据： 存放类的属性数据信息，包括父类的属性信息，这部分内存按4字节对齐。
填充数据： 由于虚拟机要求对象起始地址必须是8字节的整数倍。填充数据不是必须存在的，仅仅是为了字节对齐。
对象头 :  在HotSpot虚拟机中，对象头又被分为两部分，分别为：Mark Word(标记字段)、Class Pointer(类型指针)。如果是数组，那么还会有数组长度。

1.对象头

在对象头的Mark Word中主要存储了对象自身的运行时数据，例如哈希码、GC分代年龄、锁状态、线程持有的锁、偏向线程ID以及偏向时间戳等。同时，Mark Word也记录了对象和锁有关的信息。

当对象被synchronized关键字当成同步锁时，和锁相关的一系列操作都与Mark Word有关。由于在JDK1.6版本中对synchronized进行了锁优化，引入了偏向锁和轻量级锁（关于锁优化后边详情讨论）。Mark Word在不同锁状态下存储的内容有所不同。我们以32位JVM中对象头的存储内容如下图所示。

从图中可以清楚的看到，Mark Word中有2bit的数据用来标记锁的状态。无锁状态和偏向锁标记位为01，轻量级锁的状态为00，重量级锁的状态为10。

• 当对象为偏向锁时，Mark Word存储了偏向线程的ID；
• 当状态为轻量级锁时，Mark Word存储了指向线程栈中Lock Record的指针；
• 当状态为重量级锁时，Mark Word存储了指向堆中的Monitor对象的指针。

当前我们只讨论重量级锁，因为重量级锁相当于对synchronized优化之前的状态。关于偏向锁和轻量级锁在后边锁优化章节中详细讲解。

可以看到，当为重量级锁时，对象头的MarkWord中存储了指向Monitor对象的指针。那么Monitor又是什么呢？

2.Monitor对象

Monitor对象被称为管程或者监视器锁。在Java中，每一个对象实例都会关联一个Monitor对象。这个Monitor对象既可以与对象一起创建销毁，也可以在线程试图获取对象锁时自动生成。当这个Monitor对象被线程持有后，它便处于锁定状态。

在HotSpot虚拟机中，Monitor是由ObjectMonitor实现的,它是一个使用C++实现的类，主要数据结构如下：

ObjectMonitor() {
   _header       = NULL;
   _count        = 0; //记录个数
   _waiters      = 0,
   _recursions   = 0;  // 线程重入次数
   _object       = NULL;
   _owner        = NULL;
   _WaitSet      = NULL; // 调用wait方法后的线程会被加入到_WaitSet
   _WaitSetLock  = 0 ;
   _Responsible  = NULL ;
   _succ         = NULL ;
   _cxq          = NULL ; // 阻塞队列，线程被唤醒后根据决策判读是放入cxq还是EntryList
   FreeNext      = NULL ;
   _EntryList    = NULL ; // 没有抢到锁的线程会被放到这个队列
   _SpinFreq     = 0 ;
   _SpinClock    = 0 ;
   OwnerIsThread = 0 ;
 }
复制代码

ObjectMonitor中有五个重要部分，分别为_ower,_WaitSet,_cxq,_EntryList和count。

• _ower 用来指向持有monitor的线程，它的初始值为NULL,表示当前没有任何线程持有monitor。当一个线程成功持有该锁之后会保存线程的ID标识，等到线程释放锁后_ower又会被重置为NULL;
• _WaitSet 调用了锁对象的wait方法后的线程会被加入到这个队列中；
• _cxq 是一个阻塞队列，线程被唤醒后根据决策判读是放入cxq还是EntryList;
• _EntryList 没有抢到锁的线程会被放到这个队列；
• count 用于记录线程获取锁的次数，成功获取到锁后count会加1，释放锁时count减1。

如果线程获取到对象的monitor后，就会将monitor中的ower设置为该线程的ID，同时monitor中的count进行加1. 如果调用锁对象的wait()方法，线程会释放当前持有的monitor，并将owner变量重置为NULL，且count减1,同时该线程会进入到_WaitSet集合中等待被唤醒。

另外_WaitSet，_cxq与_EntryList都是链表结构的队列，存放的是封装了线程的ObjectWaiter对象。如果不深入虚拟机查看相关源码很难理解这几个队列的作用，关于源码会在后边系列文章中分析。这里我简单说下它们之间的关系，如下：

在多条线程竞争monitor锁的时候，所有没有竞争到锁的线程会被封装成ObjectWaiter并加入_EntryList队列。 当一个已经获取到锁的线程，调用锁对象的wait方法后，线程也会被封装成一个ObjectWaiter并加入到_WaitSet队列中。 当调用锁对象的notify方法后，会根据不同的情况来决定是将_WaitSet集合中的元素转移到_cxq队列还是_EntryList队列。 等到获得锁的线程释放锁后，又会根据条件来执行_EntryList中的线程或者将_cxq转移到_EntryList中再执行_EntryList中的线程。

所以，可以看得出来，_WaitSet存放的是处于WAITING状态等待被唤醒的线程。而_EntryList队列中存放的是等待锁的BLOCKED状态。_cxq队列仅仅是临时存放，最终还是会被转移到_EntryList中等待获取锁。

了解了对象头和Monitor，那么synchronized关键字到底是如何做到与monitor关联的呢？

synchronized关键字

synchronized的特性：
1.1 原子性
所谓原子性就是指一个操作或者多个操作，要么全部执行并且执行的过程不会被任何因素打断，要么就都不执行。
1.2 可见性
可见性是指多个线程访问一个资源时，该资源的状态、值信息等对于其他线程都是可见的。
1.3 有序性
有序性值程序执行的顺序按照代码先后执行。
synchronized和volatile都具有有序性，Java允许编译器和处理器对指令进行重排，但是指令重排并不会影响单线程的顺序，它影响的是多线程并发执行的顺序性。synchronized保证了每个时刻都只有一个线程访问同步代码块，也就确定了线程执行同步代码块是分先后顺序的，保证了有序性。
1.4 可重入性
synchronized和ReentrantLock都是可重入锁。当一个线程试图操作一个由其他线程持有的对象锁的临界资源时，将会处于阻塞状态，但当一个线程再次请求自己持有对象锁的临界资源时，这种情况属于重入锁。通俗一点讲就是说一个线程拥有了锁仍然还可以重复申请锁。

synchronized底层实现原理

1.同步代码块
在字节码中会在同步代码块的入口和出口加上monitorenter和moniterexit指令。当执行到monitorenter指令时，线程就会去尝试获取该对象对应的Monitor的所有权，即尝试获得该对象的锁。
当该对象的 monitor 的计数器count为0时，那线程可以成功取得 monitor，并将计数器值设置为 1，取锁成功。如果当前线程已经拥有该对象monitor的持有权，那它可以重入这个 monitor ，计数器的值也会加 1。而当执行monitorexit指令时，锁的计数器会减1。
倘若其他线程已经拥有monitor 的所有权，那么当前线程获取锁失败将被阻塞并进入到_EntryList中，直到等待的锁被释放为止。也就是说，当所有相应的monitorexit指令都被执行，计数器的值减为0，执行线程将释放 monitor(锁)，其他线程才有机会持有 monitor 。
2.同步方法的实现
同步方法的字节码文件并没有monitorenter和moniterexit两条指令，而是在方法的flag上加入了ACC_SYNCHRONIZED的标记位。这其实也容易理解，因为整个方法都是同步代码，因此就不需要标记同步代码的入口和出口了。当线程线程执行到这个方法时会判断是否有这个ACC_SYNCHRONIZED标志，如果有的话则会尝试获取monitor对象锁。

synchronized锁优化

JDK1.6中引入偏向锁和轻量级锁对synchronized进行优化。此时的synchronized一共存在四个状态：无锁状态、偏向锁状态、轻量级锁状态和重量级锁状态。锁着锁竞争激烈程度，锁的状态会出现一个升级的过程。即可以从偏向锁升级到轻量级锁，再升级到重量级锁。锁升级的过程是单向不可逆的，即一旦升级为重量级锁就不会再出现降级的情况。

Lock

ReentrantLock

乐观锁和悲观锁？

乐观锁：乐观锁在操作数据时非常乐观，认为别人不会同时修改数据。

因此乐观锁不会上锁，只是在执行更新的时候判断一下在此期间别人是否修改了数据：如果别人修改了数据则放弃操作，否则执行操作。

悲观锁：悲观锁在操作数据时比较悲观，认为别人会同时修改数据。

因此操作数据时直接把数据锁住，直到操作完成后才会释放锁；上锁期间其他人不能修改数据。

乐观锁的实现原理

乐观锁的实现方式主要有两种：CAS机制和版本号机制

MySQL

数据库的三范式是什么

第一范式：强调的是列的原子性，即数据库表的每一列都是不可分割的原子数据项。

第二范式：要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性。

第三范式：任何非主属性不依赖于其它非主属性。

索引

B 树和 B+树有什么不同呢？

1、B 树每一个节点里存的是数据，而 B+树存储的是索引（地址），使得整个 B+树高度降低，减少了磁盘 IO。所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。
2、B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。

B+ Tree索引和Hash索引区别？

1、因为Hash索引底层是哈希表，哈希表是一种以Key-value存储数据的结构，所以在存储数据时是没有顺序关系的，Hash索引只适合等值查询，无法进行范围查询

2、Hash索引没办法利用索引完成排序

3、Hash索引也不支持多列联合索引的最左匹配规则

4、如果有大量重复键值的情况下，Hash索引的效率会很低，因为存在哈希碰撞

聚簇索引和非聚簇索引

非聚集索引方式：
    MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。
聚簇索引：
    聚簇索引查询会更快，首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，而 B+树的叶子节点存储的是主键 ID 对应的数据。
    比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，
    节点里存的是 user_name 这个 KEY，
    叶子节点存储的数据的是主键 KEY。
    拿到主键 KEY 后，InnoDB 再去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

覆盖索引

1、覆盖索引是当 select 的数据列只用从索引中就能够取得，不必读取数据行，换句话说查询列要被所建的索引覆盖。
在name字段建立了一个索引
EXPLAIN SELECT id,name FROM student
看它的执行计划，为Using index
这是因为索引叶子节点存储了主键id，而name也是索引，所以查询为覆盖索引。

索引优化

存储引擎

数据和索引怎么组织设计，设计理念的不同也导致了 Innodb 和 Myisam 的出现，各自呈现独特的性能。

Innodb 引擎和Myisam 引擎的区别

1、MyISAM 虽然数据查找性能极佳，但是不支持事务处理。
2、Innodb 最大的特色就是支持了 ACID 兼容的事务功能，而且他支持行级锁。
3、两个引擎底层数据和索引的组织方式并不一样
    Innodb 创建表后生成的文件有：
        frm:创建表的语句
        idb:表里面的数据+索引文件
    Myisam 创建表后生成的文件有：
        frm:创建表的语句
        MYD:表里面的数据文件（myisam data）
        MYI:表里面的索引文件（myisam index）
    MyISAM 引擎把数据和索引分开了，一人一个文件，这叫做非聚集索引方式；
    Innodb 引擎把数据和索引放在同一个文件里了，这叫做聚集索引方式。

MyISAM 引擎的底层实现（非聚集索引方式）

MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。
我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

Innodb 引擎的底层实现（聚集索引方式）

首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，而 B+树的叶子节点存储的是主键 ID 对应的数据，建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因。
比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY。
注意，叶子存储的是主键 KEY！拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

事务

事务

隔离级别

ACID

原子性(Atomicity)：
一个事务必须被视为一个不可分割的最小工作单元，整个事务中的所有操作要么全部提交成功，要么全部失败回滚，对于一个事务来说，不可能只执行其中的一部分操作，这就是事务的原子性

Mysql怎么保证原子性的？

OK，是利用Innodb的undo log。

undo log名为回滚日志，是实现原子性的关键，当事务回滚时能够撤销所有已经成功执行的sql语句，他需要记录你要回滚的相应日志信息。

例如

(1)当你delete一条数据的时候，就需要记录这条数据的信息，回滚的时候，insert这条旧数据

(2)当你update一条数据的时候，就需要记录之前的旧值，回滚的时候，根据旧值执行update操作

(3)当年insert一条数据的时候，就需要这条记录的主键，回滚的时候，根据主键执行delete操

一致性(Consistency)：
数据库总是从一个一致性的状态转换到另一个一致性的状态。（在前面的例子中，一致性确保了，即使在转账过程中系统崩溃，支票账户中也不会损失200美元，因为事务最终没有提交，所以事务中所做的修改也不会保存到数据库中。）

Mysql怎么保证一致性的？

OK，这个问题分为两个层面来说。

从数据库层面，数据库通过原子性、隔离性、持久性来保证一致性。也就是说ACID四大特性之中，C(一致性)是目的，A(原子性)、I(隔离性)、D(持久性)是手段，是为了保证一致性，数据库提供的手段。数据库必须要实现AID三大特性，才有可能实现一致性。例如，原子性无法保证，显然一致性也无法保证。

但是，如果你在事务里故意写出违反约束的代码，一致性还是无法保证的。例如，你在转账的例子中，你的代码里故意不给B账户加钱，那一致性还是无法保证。因此，还必须从应用层角度考虑。

从应用层面，通过代码判断数据库数据是否有效，然后决定回滚还是提交数据！

隔离性(Isolation)

通常来说，一个事务所做的修改操作在提交事务之前，对于其他事务来说是不可见的。（在前面的例子中，当执行完第三条语句、第四条语句还未开始时，此时有另外的一个账户汇总程序开始运行，则其看到支票帐户的余额并没有被减去200美元。）

持久性(Durability)

一旦事务提交，则其所做的修改会永久保存到数据库。

Mysql怎么保证持久性的？

OK，是利用Innodb的redo log。

正如之前说的，Mysql是先把磁盘上的数据加载到内存中，在内存中对数据进行修改，再刷回磁盘上。如果此时突然宕机，内存中的数据就会丢失。

怎么解决这个问题？

简单啊，事务提交前直接把数据写入磁盘就行啊。

这么做有什么问题？

只修改一个页面里的一个字节，就要将整个页面刷入磁盘，太浪费资源了。毕竟一个页面16kb大小，你只改其中一点点东西，就要将16kb的内容刷入磁盘，听着也不合理。

毕竟一个事务里的SQL可能牵涉到多个数据页的修改，而这些数据页可能不是相邻的，也就是属于随机IO。显然操作随机IO，速度会比较慢。

于是，决定采用redo log解决上面的问题。当做数据修改的时候，不仅在内存中操作，还会在redo log中记录这次操作。当事务提交的时候，会将redo log日志进行刷盘(redo log一部分在内存中，一部分在磁盘上)。当数据库宕机重启的时候，会将redo log中的内容恢复到数据库中，再根据undo log和binlog内容决定回滚数据还是提交数据。

四种隔离级别

READ-UNCOMMITTED(读取未提交)： 最低的隔离级别，允许读取尚未提交的数据变更，可能会导致脏读、幻读或不可重复读。

READ-COMMITTED(读取已提交)： 允许读取并发事务已经提交的数据，可以阻止脏读，但是幻读或不可重复读仍有可能发生。

默认REPEATABLE-READ(可重复读)： 对同一字段的多次读取结果都是一致的，除非数据是被本身事务自己所修改，可以阻止脏读和不可重复读，但幻读仍有可能发生。

SERIALIZABLE(可串行化)： 最高的隔离级别，完全服从ACID的隔离级别。所有的事务依次逐个执行，这样事务之间就完全不可能产生干扰，也就是说，该级别可以防止脏读、不可重复读以及幻读。

脏读、不可重复读、幻读

脏读

1、在事务A执行过程中，事务A对数据资源进行了修改，事务B读取了事务A修改后的数据。

2、由于某些原因，事务A并没有完成提交，发生了回滚操作，则事务B读取的数据就是脏数据。

这种读取到另一个事务未提交的数据的现象就是脏读(Dirty Read)。

不可重复读

事务B读取了两次数据资源，在这两次读取的过程中事务A修改了数据，导致事务B在这两次读取出来的数据不一致。

这种在同一个事务中，前后两次读取的数据不一致的现象就是不可重复读(Nonrepeatable Read)。

幻读

事务B前后两次读取同一个范围的数据，在事务B两次读取的过程中事务A新增了数据，导致事务B后一次读取到前一次查询没有看到的行。

幻读和不可重复读有些类似，但是幻读强调的是集合的增减，而不是单条数据的更新。

MVCC

MVCC(Multi Version Concurrency Control的简称)，代表多版本并发控制。与MVCC相对的，是基于锁的并发控制，Lock-Based Concurrency Control)。

MVCC最大的优势：读不加锁，读写不冲突。在读多写少的OLTP应用中，读写不冲突是非常重要的，极大的增加了系统的并发性能

读-读：不存在任何问题，也不需要并发控制

读-写：有线程安全问题，可能会造成事务隔离性问题，可能遇到脏读，幻读，不可重复读

写-写：有线程安全问题，可能会存在更新丢失问题，比如第一类更新丢失，第二类更新丢失

当前读和快照读

当前读

像select lock in share mode(共享锁), select for update ; update, insert ,delete(排他锁)这些操作都是一种当前读，为什么叫当前读？就是它读取的是记录的最新版本，读取时还要保证其他并发事务不能修改当前记录，会对读取的记录进行加锁

快照读

像不加锁的select操作就是快照读，即不加锁的非阻塞读；快照读的前提是隔离级别不是串行级别，串行级别下的快照读会退化成当前读；之所以出现快照读的情况，是基于提高并发性能的考虑，快照读的实现是基于多版本并发控制，

即MVCC,可以认为MVCC是行锁的一个变种，但它在很多情况下，避免了加锁操作，降低了开销；既然是基于多版本，即快照读可能读到的并不一定是数据的最新版本，而有可能是之前的历史版本

原理

MVCC的目的就是多版本并发控制，在数据库中的实现，就是为了解决读写冲突，它的实现原理主要是依赖记录中的 3个隐式字段，undo日志 ，Read View 来实现的。所以我们先来看看这个三个point的概念

MVCC是通过在每行记录后面保存两个隐藏的列来实现的。这两个列，一个保存了行的创建时间，一个保存行的过期时间（或删除时间）。当然存储的并不是实际的时间值，而是系统版本号（system version number)。

每开始一个新的事务，系统版本号都会自动递增。事务开始时刻的系统版本号会作为事务的版本号，用来和查询到的每行记录的版本号进行比较。

总结

总之，MVCC就是因为大牛们，不满意只让数据库采用悲观锁这样性能不佳的形式去解决读-写冲突问题，而提出的解决方案，所以在数据库中，因为有了MVCC，所以我们可以形成两个组合：

MVCC + 悲观锁

MVCC解决读写冲突，悲观锁解决写写冲突

MVCC + 乐观锁

MVCC解决读写冲突，乐观锁解决写写冲突

这种组合的方式就可以最大程度的提高数据库并发性能，并解决读写冲突，和写写冲突导致的问题

日志

innodb事务日志包括redo log和undo log。redo log是重做日志，提供前滚操作，undo log是回滚日志，提供回滚操作。

Bin Log:是mysql服务层产生的日志，常用来进行数据恢复、数据库复制，常见的mysql主从架构，就是采用slave同步master的binlog实现的

Redo Log:记录了数据操作在物理层面的修改，mysql中使用了大量缓存，修改操作时会直接修改内存，而不是立刻修改磁盘，事务进行中时会不断的产生redo log，在事务提交时进行一次flush操作，保存到磁盘中。当数据库或主机失效重启时，会根据redo log进行数据的恢复，如果redo log中有事务提交，则进行事务提交修改数据。

Undo Log: 除了记录redo log外，当进行数据修改时还会记录undo log，undo log用于数据的撤回操作，它记录了修改的反向操作，比如，插入对应删除，修改对应修改为原来的数据，通过undo log可以实现事务回滚，并且可以根据undo log回溯到某个特定的版本的数据，实现MVCC

Redis

缓存穿透、缓存击穿、缓存雪崩

缓存穿透

表示查询一个一定不存在的数据，由于没有获取到缓存，所以没写入缓存，导致这个不存在的数据每次都需要去数据库查询，失去了缓存的意义。

请求的数据大量的没有获取到缓存，导致走数据库，有可能搞垮数据库，使整个服务瘫痪。

解决

1、对于像ID为负数的非法请求直接过滤掉，采用布隆过滤器(Bloom Filter)。

2、针对在数据库中找不到记录的，我们仍然将该空数据存入缓存中，当然一般会设置一个较短的过期时间。

缓存击穿

表示某个key的缓存非常热门，有很高的并发一直在访问，如果该缓存失效，那同时会走数据库，压垮数据库。

缓存击穿与缓存雪崩的区别是这里针对的是某一热门key缓存，而雪崩针对的是大量缓存的集中失效。

解决

1、让该热门key的缓存永不过期。

2、使用互斥锁，通过redis的setnx实现互斥锁。

缓存雪崩

表示在某一时间段，缓存集中失效，导致请求全部走数据库，有可能搞垮数据库，使整个服务瘫痪。

解决

1、针对原因1，可以实现redis的高可用，Redis Cluster 或者 Redis Sentinel(哨兵) 等方案。

2、针对原因2，设置缓存过期时间时加上一个随机值，避免缓存在同一时间过期。

3、使用双缓存策略，设置两个缓存，原始缓存和备用缓存，原始缓存失效时，访问备用缓存，备用缓存失效时间设置长点。

问题

Redis热点数据如何处理

(1)利用二级缓存

比如利用ehcache，或者一个HashMap都可以。在你发现热key以后，把热key加载到系统的JVM中。

针对这种热key请求，会直接从jvm中取，而不会走到redis层。

假设此时有十万个针对同一个key的请求过来,如果没有本地缓存，这十万个请求就直接怼到同一台redis上了。

现在假设，你的应用层有50台机器，OK，你也有jvm缓存了。这十万个请求平均分散开来，每个机器有2000个请求，会从JVM中取到value值，然后返回数据。避免了十万个请求怼到同一台redis上的情形。

(2)备份热key

这个方案也很简单。不要让key走到同一台redis上不就行了。我们把这个key，在多个redis上都存一份不就好了。接下来，有热key请求进来的时候，我们就在有备份的redis上随机选取一台，进行访问取值，返回数据。

怎么发现热key

方法一:凭借业务经验，进行预估哪些是热key

其实这个方法还是挺有可行性的。比如某商品在做秒杀，那这个商品的key就可以判断出是热key。缺点很明显，并非所有业务都能预估出哪些key是热key。

方法二:在客户端进行收集

这个方式就是在操作redis之前，加入一行代码进行数据统计。那么这个数据统计的方式有很多种，也可以是给外部的通讯系统发送一个通知信息。缺点就是对客户端代码造成入侵。

方法三:在Proxy层做收集

有些集群架构是下面这样的，Proxy可以是Twemproxy，是统一的入口。可以在Proxy层做收集上报，但是缺点很明显，并非所有的redis集群架构都有proxy。

方法四:用redis自带命令

(1)monitor命令，该命令可以实时抓取出redis服务器接收到的命令，然后写代码统计出热key是啥。当然，也有现成的分析工具可以给你使用，比如redis-faina。但是该命令在高并发的条件下，有内存增暴增的隐患，还会降低redis的性能。

(2)hotkeys参数，redis 4.0.3提供了redis-cli的热点key发现功能，执行redis-cli时加上–hotkeys选项即可。但是该参数在执行的时候，如果key比较多，执行起来比较慢。

方法五:自己抓包评估

Redis客户端使用TCP协议与服务端进行交互，通信协议采用的是RESP。自己写程序监听端口，按照RESP协议规则解析数据，进行分析。缺点就是开发成本高，维护困难，有丢包可能性。

数据类型

String字符串类型

场景

（1）缓存结构体信息：

（2）计数功能：

List列表类型

场景

（1）list列表结构常用来做异步队列使用

（2）list可用于秒杀抢购场景

数据结构

ziplist 

当存储的数据量较少的时，hash 采用 ziplist 作为底层存储结构，此时要求符合以下两个条件：

哈希对象保存的所有键值对（键和值）的字符串长度总和小于 64 个字节。

哈希对象保存的键值对数量要小于 512 个。

 dict（字典结构）

该结构类似于 Java 的 HashMap，是一个无序的字典，并采用了数组和链表相结合的方式存储数据。在 Redis 中，dict 是基于哈希表算法实现的，因此其查找性能非常高效，其时间复杂度为 O(1)。

Hash数据类型

场景

（1）保存结构体信息

Set集合类型

场景

就是用在一些去重的场景里，例如每个用户只能参与一次活动、一个用户只能中奖一次等等去重场景。

Zset有序集合

场景

（1）各类热门排序场景

数据结构

跳表

时间复杂度

有n个结点的链表，假设每两个链表构建一个索引，那么：

第一级索引个数为：n/2；

第二级索引个数为：n/4；

···

第h级索引个数为：n/2^h；

以此类推，在每一层需要通过3个节点找目标数，那么总的时间复杂度就为O(3*logn)，因为3是常数，所以最后的时间复杂度为O(logn)。

空间复杂度

链表上的索引数目按第一层，第二层，···，倒数第二层，最后一层的顺序排列下来分别为：n/2，n/4，···，4，2

所以空间复杂度为O(n)

高并发

Redis通过主从架构，实现读写分离，主节点负责写，并将数据同步给其他从节点，从节点负责读，从而实现高并发。



Redis高并发的同时，还需要容纳大量的数据：一主多从，每个实例都容纳了完整的数据，比如redis主就10G的内存量，其实你就最对只能容纳10g的数据量。如果你的缓存要容纳的数据量很大，达到了几十g，甚至几百g，或者是几t，那你就需要redis集群，而且用redis集群之后，可以提供可能每秒几十万的读写并发。

Redis主从架构数据会丢失



有两种数据丢失的情况：

异步复制导致的数据丢失：因为master -> slave的复制是异步的，所以可能有部分数据还没复制到slave，master就宕机了，此时这些部分数据就丢失了。

脑裂导致的数据丢失：某个master所在机器突然脱离了正常的网络，跟其他slave机器不能连接，但是实际上master还运行着，此时哨兵可能就会认为master宕机了，然后开启选举，将其他slave切换成了master。

这个时候，集群里就会有两个master，也就是所谓的脑裂。此时虽然某个slave被切换成了master，但是可能client还没来得及切换到新的master，还继续写向旧master的数据可能也丢失了。因此旧master再次恢复的时候，会被作为一个slave挂到新的master上去，自己的数据会清空，重新从新的master复制数据。

Redis主从复制的工作原理？



1.一个Slave实例，无论是第一次连接还是重连到Master，它都会发出一个SYNC命令；

2.当Master收到SYNC命令之后，会做两件事：(a) Master执行BGSAVE，即在后台保存数据到磁盘（rdb快照文件）；(b) Master同时将新收到的写入和修改数据集的命令存入缓冲区（非查询类）；

3.当Master在后台把数据保存到快照文件完成之后，Master会把这个快照文件传送给Slave，而Slave则把内存清空后，加载该文件到内存中；

4.而Master也会把此前收集到缓冲区中的命令，通过Reids命令协议形式转发给Slave，Slave执行这些命令，实现和Master的同步；

5.Master/Slave此后会不断通过异步方式进行命令的同步，达到最终数据的同步一致；

数据一致性问题

合理设置缓存的过期时间。
新增、更改、删除数据库操作时同步更新 Redis，可以使用事物机制来保证数据的一致性。
1.第一种方案：采用延时双删策略

解决方法一：数据实时更新

当更新数据库的时候，同步更新缓存。

优点：数据一致性强，不会出现缓存雪崩的问题。

缺点：代码耦合度高，影响正常业务，增加一次网络开销。

适用环境：适用于数据一致性要求高的场景，比如银行业务，证券交易等

解决方法二：数据准实时更新

当更新数据库的同时，异步去更新缓存，比如更新数据库后把一条消息发送到mq中去实现。

优点：与业务解耦，不影响正常业务，不会出现缓存雪崩。

缺点：有较短的延迟，并且无法保证最终的一致性，需要补偿机制。

适用环境：写操作不频繁并且实时性要求不严格的场景。

解决方法三：缓存失效机制

基于缓存本身的失效机制，具体实现方式为设置缓存失效时间，如果有缓存就从缓存中取数据，如果没缓存就从数据库中取数据，并且重新设置缓存。

优点：实现方式简单，与业务完美解耦，不影响正常业务。

缺点：有一定延迟，并且存在缓存雪崩的情况。

适用环境：适合读多写少的互联网环境，能接受一定的数据延时。

解决方法四：定时任务更新

通过定时任务，按照一定时间间隔更新缓存。

优点：不影响正常业务，在特殊场景应用广泛。

缺点：不保证实时一致性，且需要为每个任务写一个调度代码。

适用环境：适用于需要复杂数据统计的缓存更新，比如展示高速车流量，五分钟一次的统计不会影响业务使用。

Redis的事务

相关命令

\1. MULTI

用于标记事务块的开始。Redis会将后续的命令逐个放入队列中，然后才能使用EXEC命令原子化地执行这个命令序列。

这个命令的运行格式如下所示：

MULTI

这个命令的返回值是一个简单的字符串，总是OK。

\2. EXEC

在一个事务中执行所有先前放入队列的命令，然后恢复正常的连接状态。

当使用WATCH命令时，只有当受监控的键没有被修改时，EXEC命令才会执行事务中的命令，这种方式利用了检查再设置（CAS）的机制。

这个命令的运行格式如下所示：

EXEC

这个命令的返回值是一个数组，其中的每个元素分别是原子化事务中的每个命令的返回值。 当使用WATCH命令时，如果事务执行中止，那么EXEC命令就会返回一个Null值。

\3. DISCARD

清除所有先前在一个事务中放入队列的命令，然后恢复正常的连接状态。

如果使用了WATCH命令，那么DISCARD命令就会将当前连接监控的所有键取消监控。

这个命令的运行格式如下所示：

DISCARD

这个命令的返回值是一个简单的字符串，总是OK。

\4. WATCH

当某个事务需要按条件执行时，就要使用这个命令将给定的键设置为受监控的。

这个命令的运行格式如下所示：

WATCH key [key ...]

这个命令的返回值是一个简单的字符串，总是OK。

对于每个键来说，时间复杂度总是O(1)。

\5. UNWATCH

清除所有先前为一个事务监控的键。

如果你调用了EXEC或DISCARD命令，那么就不需要手动调用UNWATCH命令。

这个命令的运行格式如下所示：

UNWATCH

这个命令的返回值是一个简单的字符串，总是OK。

时间复杂度总是O(1)。

Redis事务允许在一次单独的步骤中执行一组命令，并且可以保证如下两个重要事项：

\>Redis会将一个事务中的所有命令序列化，然后按顺序执行。Redis不可能在一个Redis事务的执行过程中插入执行另一个客户端发出的请求。这样便能保证Redis将这些命令作为一个单独的隔离操作执行。

\> 在一个Redis事务中，Redis要么执行其中的所有命令，要么什么都不执行。因此，Redis事务能够保证原子性。EXEC命令会触发执行事务中的所有命令。因此，当某个客户端正在执行一次事务时，如果它在调用MULTI命令之前就从Redis服务端断开连接，那么就不会执行事务中的任何操作；相反，如果它在调用EXEC命令之后才从Redis服务端断开连接，那么就会执行事务中的所有操作。

问题

Redis事务保证原子性吗，支持回滚吗

Redis中，单条命令是原子性执行的，但事务不保证原子性，且没有回滚。事务中任意命令执行失败，其余的命令仍会被执行。

持久化机制

redis提供两种方式进行持久化

一种是RDB持久化（原理是将Reids在内存中的数据库记录定时dump到磁盘上的RDB持久化）

另外一种是AOF持久化（append only file原理是将Reids的操作日志以追加的方式写入文件）。

区别

RDB持久化是指在指定的时间间隔内将内存中的数据集快照写入磁盘，实际操作过程是fork一个子进程，先将数据集写入临时文件，写入成功后，再替换之前的文件，用二进制压缩存储。

AOF持久化以日志的形式记录服务器所处理的每一个写、删除操作，查询操作不会记录，以文本的方式记录，可以打开文件看到详细的操作记录。

优缺点

RDB

优点

1). 一旦采用该方式，那么你的整个Redis数据库将只包含一个文件，这对于文件备份而言是非常完美的。比如，你可能打算每个小时归档一次最近24小时的数据，同时还要每天归档一次最近30天的数据。通过这样的备份策略，一旦系统出现灾难性故障，我们可以非常容易的进行恢复。

2). 对于灾难恢复而言，RDB是非常不错的选择。因为我们可以非常轻松的将一个单独的文件压缩后再转移到其它存储介质上。

3). 性能最大化。对于Redis的服务进程而言，在开始持久化时，它唯一需要做的只是fork出子进程，之后再由子进程完成这些持久化的工作，这样就可以极大的避免服务进程执行IO操作了。

4). 相比于AOF机制，如果数据集很大，RDB的启动效率会更高。

缺点

1). 如果你想保证数据的高可用性，即最大限度的避免数据丢失，那么RDB将不是一个很好的选择。因为系统一旦在定时持久化之前出现宕机现象，此前没有来得及写入磁盘的数据都将丢失。

2). 由于RDB是通过fork子进程来协助完成数据持久化工作的，因此，如果当数据集较大时，可能会导致整个服务器停止服务几百毫秒，甚至是1秒钟。

AOF

优点

1). 该机制可以带来更高的数据安全性，即数据持久性。Redis中提供了3中同步策略，即每秒同步、每修改同步和不同步。事实上，每秒同步也是异步完成的，其效率也是非常高的，所差的是一旦系统出现宕机现象，那么这一秒钟之内修改的数据将会丢失。而每修改同步，我们可以将其视为同步持久化，即每次发生的数据变化都会被立即记录到磁盘中。可以预见，这种方式在效率上是最低的。至于无同步，无需多言，我想大家都能正确的理解它。

2). 由于该机制对日志文件的写入操作采用的是append模式，因此在写入过程中即使出现宕机现象，也不会破坏日志文件中已经存在的内容。然而如果我们本次操作只是写入了一半数据就出现了系统崩溃问题，不用担心，在Redis下一次启动之前，我们可以通过redis-check-aof工具来帮助我们解决数据一致性的问题。

3). 如果日志过大，Redis可以自动启用rewrite机制。即Redis以append模式不断的将修改数据写入到老的磁盘文件中，同时Redis还会创建一个新的文件用于记录此期间有哪些修改命令被执行。因此在进行rewrite切换时可以更好的保证数据安全性。

4). AOF包含一个格式清晰、易于理解的日志文件用于记录所有的修改操作。事实上，我们也可以通过该文件完成数据的重建。

缺点

1). 对于相同数量的数据集而言，AOF文件通常要大于RDB文件。RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快。

2). 根据同步策略的不同，AOF在运行效率上往往会慢于RDB。总之，每秒同步策略的效率是比较高的，同步禁用策略的效率和RDB一样高效。

二者选择的标准，就是看系统是愿意牺牲一些性能，换取更高的缓存一致性（aof），还是愿意写操作频繁的时候，不启用备份来换取更高的性能，待手动运行save的时候，再做备份（rdb）。rdb这个就更有些 eventually consistent的意思了。

常用配置

RDB持久化配置

Redis会将数据集的快照dump到dump.rdb文件中。此外，我们也可以通过配置文件来修改Redis服务器dump快照的频率，在打开6379.conf文件之后，我们搜索save，可以看到下面的配置信息：

save 900 1 #在900秒(15分钟)之后，如果至少有1个key发生变化，则dump内存快照。

save 300 10 #在300秒(5分钟)之后，如果至少有10个key发生变化，则dump内存快照。

save 60 10000 #在60秒(1分钟)之后，如果至少有10000个key发生变化，则dump内存快照。

AOF持久化配置

在Redis的配置文件中存在三种同步方式，它们分别是：

appendfsync always #每次有数据修改发生时都会写入AOF文件。

appendfsync everysec #每秒钟同步一次，该策略为AOF的缺省策略。

appendfsync no #从不同步。高效但是数据不会被持久化。

优化

缩短键值对的存储长度；

使用 lazy free（延迟删除）特性；

设置键值的过期时间；

禁用长耗时的查询命令；

使用 slowlog 优化耗时命令；

使用 Pipeline 批量操作数据；

避免大量数据同时失效；

客户端使用优化；

限制 Redis 内存大小；

使用物理机而非虚拟机安装 Redis 服务；

检查数据持久化策略；

禁用 THP 特性；

使用分布式架构来增加读写速度。

分布式锁

分布式锁应该满足哪些特性？

互斥：在任何给定时刻，只有一个客户端可以持有锁；

无死锁：任何时刻都有可能获得锁，即使获取锁的客户端崩溃；

容错：只要大多数 Redis的节点都已经启动，客户端就可以获取和释放锁。

可以使用 SETNX key value 命令是实现「互斥」特性。

这个命令来自于SET if Not eXists的缩写，意思是：如果 key 不存在，则设置 value 给这个key，否则啥都不做。Redis 官方地址说的：

1：设置成功；

0：key 没有设置成功。

使用 DEL 删除这个 key 就行。

释放锁

客户端所在节点崩溃，无法正确释放锁；

业务逻辑异常，无法执行 DEL指令。

超时设置

Redis超卖问题

答：redis存商品id，每次都只允许一个线程访问。

Mybatis-puls

mybatis 有几种分页方式？

数组分页
sql分页
拦截器分页
RowBounds分页

mybatis 逻辑分页和物理分页的区别是什么？

说一下 mybatis 的一级缓存和二级缓存？

一级缓存: 基于 PerpetualCache 的 HashMap 本地缓存，其存储作用域为 Session，当 Session flush 或 close 之后，该 Session 中的所有 Cache 就将清空，默认打开一级缓存。

二级缓存与一级缓存其机制相同，默认也是采用 PerpetualCache，HashMap 存储，不同在于其存储作用域为 Mapper(Namespace)，并且可自定义存储源，如 Ehcache。默认不打开二级缓存，要开启二级缓存，使用二级缓存属性类需要实现Serializable序列化接口(可用来保存对象的状态),可在它的映射文件中配置<cache/> ；

对于缓存数据更新机制，当某一个作用域(一级缓存 Session/二级缓存Namespaces)的进行了C/U/D 操作后，默认该作用域下所有 select 中的缓存将被 clear。

Spring

Spring的核心特性

Spring的核心特性就是IOC和AOP
IOC（Inversion of Control）：“控制反转”，即对象创建的问题。通俗地讲就是把创建对象的代码交给了Spring的配置文件来进行的。这样做的优点是大大降低的代码的耦合度。
AOP（Aspect-OrientedProgramming），即“面向切面编程”。

Spring boot 相对 Spring有什么优势

传统Spring框架存在的弊端：

Spring事物管理，MVC，启用第三方库都需要XML或Java进行显示配置，配置过重
写配置挤占了实际写应用的逻辑的时间
项目依赖管理，要考虑用那些库，还要知道哪些版本和库不会有冲突，影响开发效率

SpringBoot的优势：

自动配置：针对很多Spring常见的应用功能，SpringBoot能自动提供相关配置
起步依赖：告诉SpringBoot需要什么功能，它就能引入需要的库
CLI命令行界面：通过SpringBootCLI,借此你只需写代码就能完成完整的应用程序，无须传统项目构建
Actuator: 提供在运行时检视应用程序内部情况的能力

如何使用Spring IOC

IOC创建实例对象有两种方法，一种是配置文件创建，另一种是注解的方法创建。
1、配置文件创建
这里我们需要三步：
第一步、创建配置文件，我们在根目录下创applicationContext.xml（PS：名称可以不唯一）的配置文件，并且主体部分如下

第二步、创建类。（我们之前创建了User类，这里就不演示了）

第三步、配置xml文件

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd">
    <!--
        id:用于SpringIOC调用，可以为任意
        class：类的全路径
        scope:作用范围，scope不是必填属性，不写的默认值单例。为创建对象的方式，有两种结果：
             1.singleton默认值，单实例。(常用)
             2.prototype 多实例。(常用)
             3.request：作用于 web 应用的请求范围
             4.session：作用于 web 应用的会话范围
             5.global-session：作用于集群环境的会话范围（全局会话范围），当不是集群环境时，就是session
        -->
    <bean id="user"  class="com.testWeb.daomain.User" scope="prototype"></bean>
</beans>

第四步、写测试代码测试

public class testSpring {
    @Test
    public void testIOC(){
        ApplicationContext context=new ClassPathXmlApplicationContext("applicationContext.xml");
        User user1= (User) context.getBean("user");
        User user2=(User) context.getBean("user");
        System.out.println(user1+user2);//如果scope为单例，两个对象的地址相同，多例效果则相反
    }
}

2、注解创建

首先来指出四种创建对象的四种注解方式：（四种注解本质上创建对象的方法是相同的，名称只是起到了清晰用途的作用）

首先是@Component注解创建，它又衍生出了三种注解：

1. @Controller ：web层
2. @Service ：service层
3. @repository：持久层

如何使用Spring AOP

Spring初始化Bean

Spring单例对象的初始化其实可以分为三步：
1、createBeanInstance， 实例化，实际上就是调用对应的构造方法构造对象，此时只是**调用了构造方法，spring xml中指定的property并没有进行populate**
2、populateBean，填充属性，这步对spring xml中指定的property进行populate
3、initializeBean，调用spring xml中指定的init方法，或者AfterPropertiesSet方法。

Bean 的生命周期

如上图所示，Bean 的生命周期还是比较复杂的，下面来对上图每一个步骤做文字描述:

Spring启动，查找并加载需要被Spring管理的bean，进行Bean的实例化

Bean实例化后对将Bean的引入和值注入到Bean的属性中

如果Bean实现了BeanNameAware接口的话，Spring将Bean的Id传递给setBeanName()方法

如果Bean实现了BeanFactoryAware接口的话，Spring将调用setBeanFactory()方法，将BeanFactory容器实例传入

如果Bean实现了ApplicationContextAware接口的话，Spring将调用Bean的setApplicationContext()方法，将bean所在应用上下文引用传入进来。

如果Bean实现了BeanPostProcessor接口，Spring就将调用他们的postProcessBeforeInitialization()方法。

如果bean有被@PostConstruct注解的方法，会执行该方法；如果Bean 实现了InitializingBean接口，Spring将调用他们的afterPropertiesSet()方法。类似的，如果bean使用init-method声明了初始化方法，该方法也会被调用

如果Bean 实现了BeanPostProcessor接口，Spring就将调用他们的postProcessAfterInitialization()方法。

此时，Bean已经准备就绪，可以被应用程序使用了。他们将一直驻留在应用上下文中，直到应用上下文被销毁。

如果bean有被@PreDestroy注解的方法，执行该方法；如果bean实现了DisposableBean接口，Spring将调用它的destory()接口方法，同样，如果bean使用了destory-method 声明销毁方法，该方法也会被调用。

Bean的作用域

spring怎么解决bean的循环依赖

spring中循环依赖有三种情况：

　　1、构造器注入形成的循环依赖。也就是beanB需要在beanA的构造函数中完成初始化，beanA也需要在beanB的构造函数中完成舒适化，这种情况的结果就是两个bean都不能完成初始化，循环依赖难以解决。

　　2、setter注入构成的循环依赖。beanA需要在beanB的setter方法中完成初始化，beanB也需要在beanA的setter方法中完成初始化，spring设计的机制主要就是解决这种循环依赖。

　　3、prototype作用域bean的循环依赖。这种循环依赖同样无法解决，因为spring不会缓存‘prototype’作用域的bean，而spring中循环依赖的解决正是通过缓存来实现的。
　　
4.解决方法
4.1 重新设计
4.2 使用注解 @Lazy
4.3 使用Setter/Field注入
4.4 使用@PostConstruct
4.5 实现ApplicationContextAware与InitializingBean

setter注入构成的循环依赖解决方案

步骤一：beanA进行初始化，并且将自己进行初始化的状态记录下来，并提前向外暴露一个单例工程方法，从而使其他bean能引用到该bean（可能读完这一句，您仍然心存疑惑，没关系，继续往下读）

　　步骤二：beanA中有beanB的依赖，于是开始初始化beanB。

　　步骤三：初始化beanB的过程中又发现beanB依赖了beanA,于是又进行beanA的初始化，这时发现beanA已经在进行初始化了，程序发现了存在的循环依赖，然后通过步骤一中暴露的单例工程方法拿到beanA的引用（注意，此时的beanA只是完成了构造函数的注入但为完成其他步骤），从而beanB拿到beanA的引用，完成注入，完成了初始化，如此beanB的引用也就可以被beanA拿到，从而beanA也就完成了初始化。

　　spring进行bean的加载的时候，首先进行bean的初始化（调用构造函数），然后进行属性填充。在这两步中间，spring对bean进行了一次状态的记录，也就是说spring会把指向只完成了构造函数初始化的bean的引用通过一个变量记录下来，明白这一点对之后的源码理解至关重要。

Spring中实现事务方式

Spring 提供了两种方式实现事务:①声明式，②编程式。
Spring 并不直接支持事务，只有当数据库支持事务时，Spring 才支持事务，Spring 只不过简化了开发人员实现事务的步骤。

编程式事务：允许用户在代码中精确定义事务的边界。

声明式事务：（基于AOP）有助于用户将操作与事务规则进行解耦。简单地说，编程式事务侵入到了业务代码里面，但是提供了更加详细的事务管理；而声明式事务由于基于AOP，所以既能起到事务管理的作用，又可以不影响业务代码的具体实现。

声明式事务

声明式事务管理只需要用到@Transactional 注解和@EnableTransactionManagement（开启事务管理功能）。它是基于 Spring AOP 实现的，并且通过注解实现，实现起来简单，对原有代码没有入侵性。

事务的7种传播级别

1） PROPAGATION_REQUIRED ，默认的spring事务传播级别，使用该级别的特点是，如果上下文中已经存在事务，那么就加入到事务中执行，如果当前上下文中不存在事务，则新建事务执行。所以这个级别通常能满足处理大多数的业务场景。

2）PROPAGATION_SUPPORTS ，从字面意思就知道，supports，支持，该传播级别的特点是，如果上下文存在事务，则支持事务加入事务，如果没有事务，则使用非事务的方式执行。所以说，并非所有的包在transactionTemplate.execute中的代码都会有事务支持。这个通常是用来处理那些并非原子性的非核心业务逻辑操作。应用场景较少。

3）PROPAGATION_MANDATORY ， 该级别的事务要求上下文中必须要存在事务，否则就会抛出异常！配置该方式的传播级别是有效的控制上下文调用代码遗漏添加事务控制的保证手段。比如一段代码不能单独被调用执行，但是一旦被调用，就必须有事务包含的情况，就可以使用这个传播级别。

4）PROPAGATION_REQUIRES_NEW ，从字面即可知道，new，每次都要一个新事务，该传播级别的特点是，每次都会新建一个事务，并且同时将上下文中的事务挂起，执行当前新建事务完成以后，上下文事务恢复再执行。

这是一个很有用的传播级别，举一个应用场景：现在有一个发送100个红包的操作，在发送之前，要做一些系统的初始化、验证、数据记录操作，然后发送100封红包，然后再记录发送日志，发送日志要求100%的准确，如果日志不准确，那么整个父事务逻辑需要回滚。
怎么处理整个业务需求呢？就是通过这个PROPAGATION_REQUIRES_NEW 级别的事务传播控制就可以完成。发送红包的子事务不会直接影响到父事务的提交和回滚。

5）PROPAGATION_NOT_SUPPORTED ，这个也可以从字面得知，not supported ，不支持，当前级别的特点就是上下文中存在事务，则挂起事务，执行当前逻辑，结束后恢复上下文的事务。

这个级别有什么好处？可以帮助你将事务极可能的缩小。我们知道一个事务越大，它存在的风险也就越多。所以在处理事务的过程中，要保证尽可能的缩小范围。比如一段代码，是每次逻辑操作都必须调用的，比如循环1000次的某个非核心业务逻辑操作。这样的代码如果包在事务中，势必造成事务太大，导致出现一些难以考虑周全的异常情况。所以这个事务这个级别的传播级别就派上用场了。用当前级别的事务模板抱起来就可以了。

6）PROPAGATION_NEVER ，该事务更严格，上面一个事务传播级别只是不支持而已，有事务就挂起，而PROPAGATION_NEVER传播级别要求上下文中不能存在事务，一旦有事务，就抛出runtime异常，强制停止执行！这个级别上辈子跟事务有仇。

7）PROPAGATION_NESTED ，字面也可知道，nested，嵌套级别事务。该传播级别特征是，如果上下文中存在事务，则嵌套事务执行，如果不存在事务，则新建事务。

Autowire是按照什么规则来获取Bean

当Spring装配Bean属性时，有时候非常明确，就是需要将某个Bean的引用装配给指定属性。
比如，如果我们的应用上下文中只有一个org.mybatis.spring.SqlSessionFactoryBean 类型的Bean
那么任意一个依赖SqlSessionFactoryBean的其他Bean就是需要这个Bean。毕竟这里只有一个SqlSessionFactoryBean的Bean。
为了应对这种明确的装配场景，Spring提供了自动装配(autowiring)。与其显式的装配Bean属性，为何不让Spring识别出可以自动装配的场景。
当涉及到自动装配Bean的依赖关系时，Spring有多种处理方式。因此，Spring提供了4种自动装配策略。
    //无需自动装配
    int AUTOWIRE_NO = 0;

    //按名称自动装配bean属性
    int AUTOWIRE_BY_NAME = 1;

    //按类型自动装配bean属性
    int AUTOWIRE_BY_TYPE = 2;

    //按构造器自动装配
    int AUTOWIRE_CONSTRUCTOR = 3;

除了Autowire其他获取Bean的方法

一：在初始化时保存ApplicationContext对象
可以在初始化的时候保存ApplicationContext对象，然后通过这个对象获取Bean，测试代码如下：

/**
 * 方式二：使用ClassPathXmlApplicationContext获取ApplicationContext
 */
@Test
public void getBeanTest2() {
    ApplicationContext applicationContext = new ClassPathXmlApplicationContext("applicationContext.xml");
    UserInfo userInfo = (UserInfo) applicationContext.getBean("userInfo");
    System.out.println(userInfo);
}

：使用BeanFactory直接获取（不推荐）
使用BeanFactory从工厂中直接获取Bean实例，但是XmlBeanFactory类已经废弃，因此不建议使用，测试代码如下：

/**
 * 方式一：XmlBeanFactory已经废弃不建议使用
 */
@Test
public void getBeanTest1() {
    BeanFactory beanFactory = new XmlBeanFactory(new ClassPathResource("applicationContext.xml"));
    UserInfo userInfo = (UserInfo) beanFactory.getBean("userInfo");
    System.out.println(userInfo);
}

三：继承自抽象类ApplicationObjectSupport
可以继承抽象类ApplicationObjectSupport并将自己继承的类注入到Spring容器中，示例代码如下：

/**
 * 方法三：继承ApplicationObjectSupport来获取ApplicationContext，
 * 注意：需要把自己继承的类注入到Spring
 */
@Test
public void getBeanTest3() {
    ApplicationContextUtil2 applicationContextUtil2 = (ApplicationContextUtil2) ApplicationContextUtil.getBean("applicationContextUtil2");
    UserInfo userInfo = (UserInfo) applicationContextUtil2.getBean("userInfo");
    System.out.println(userInfo);
}

四：继承自抽象类WebApplicationObjectSupport
可以继承抽象类WebApplicationObjectSupport并将自己继承的类注入到Spring容器中，示例代码如下：

/**
 * 方法四：继承WebApplicationObjectSupport来获取ApplicationContext，
 * 注意：需要把自己继承的类注入到Spring，同时需要添加@WebAppConfiguration注解，否则会找不到web容器
 */
@Test
public void getBeanTest4() {
    ApplicationContextUtil3 applicationContextUtil3 = (ApplicationContextUtil3) ApplicationContextUtil.getBean("applicationContextUtil3");
    UserInfo userInfo = (UserInfo) applicationContextUtil3.getBean("userInfo");
    System.out.println(userInfo);
}

微服务

微服务架构

微服务架构的优缺点

分布式配置中心

Nacos

服务注册与发现

Nacos

远程服务调用（RPC）

OpenFeign

Dubbo

 Dubbo核心概念
 Apache Dubbo 是一款高性能、轻量级的开源Java RPC框架，它提供了三大核心能力：面向接口的远程方法调用，智能容错和负载均衡，以及服务自动注册和发现。

API网关 服务路由

Geteway

服务熔断

Hystrix

Sentinel

分布式消息

RocketMQ

Kafka

分布式事务

Seata