```

数据结构

树

树的种类

无序树

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

有序树

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

字典树

又称单词查找树，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+树要低，空间使用率更高；

算法

复杂度分析

时间复杂度：

空间复杂度：

递归

​

计算机网络

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

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

• 应用层：协议有：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 的三次握手和四次挥手

TCP 是一种面向连接的单播协议，在发送数据前，通信双方必须在彼此间建立一条连接。所谓的“连接”，其实是客户端和服务器的内存里保存的一份关于对方的信息，如 IP 地址、端口号等。​TCP 可以看成是一种字节流，它会处理 IP 层或以下的层的丢包、重复以及错误问题。在连接的建立过程中，双方需要交换一些连接的参数。这些参数可以放在 TCP 头部。​TCP 提供了一种可靠、面向连接、字节流、传输层的服务，采用三次握手建立一个连接；采用四次挥手来关闭一个连接。

HTTP & HTTPS

HTTP 是什么

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

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

HTTPS 是什么

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

操作系统

CPU

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 查找到对应的数据。

事务

事务

Java

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<E>，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,直接实现了它的有 LinkedList, ArayDeque, ConcurrentLinkedDeque 等。

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

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

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.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。表示一个持久的属性集.属性列表中每个键及其对应值都是一个字符串。

BitSet

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

集合算法

集合算法

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

迭代器（lterator）

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

锁

Redis

​

Spring