-[Spring](https://github.com/msJavaCoder/msJava/blob/master/docs/框架/Spring.md)

-[SpringMVC](https://github.com/msJavaCoder/msJava/blob/master/docs/框架/SpringMVC.md)

*[理解TCP和UDP](./docs/network/理解TCP和UDP.md)

*[理解HTTP和HTTPS](./docs/network/理解HTTP与HTTPS.md)

* 数据结构与算法

*[常用数据结构](./docs/数据结构/常用数据结构.md)

*[常用算法](./docs/数据结构/常用算法.md)

* Java核心基础

*[理解基本数据类型与包装类](./docs/java/理解基本数据类型与包装类.md)

*[理解类与Object](./docs/java/理解类与Object.md)

首先看数据结构的知识点都有哪些，如下图所示。


1. 队列和栈是经常使用的数据结构，需要了解它们的特点。队列是先进先出，栈是后进先出。

2. 表，包括很多种，有占用连续空间的数组、用指针链接的单向和双向链表，首尾相接的循环链表、以及散列表，也叫哈希表。

3. 图，在特定领域使用的比较多，例如路由算法中会经常使用到，图分为有向图、无向图及带权图，这部分需要掌握图的深度遍历和广度遍历算法，了解最短路径算法。

4. 树的内容，树一般用作查找与排序的辅助结构，剩下两个部分都和树有关，一个是二叉树，一个是多叉树。

5. 多叉树包括 B 树族，有 B 树、B+ 树、B* 树，比较适合用来做文件检索；另外一个是字典树，适合进行字符串的多模匹配。

6. 二叉树包括平衡二叉树、红黑树、哈夫曼树，以及堆，适合用于进行数据查找和排序。这部分需要了解二叉树的构建、插入、删除操作的实现，需要掌握二叉树的前序、中序、后序遍历。

如下图所示，二叉搜索树满足这样的条件，每个节点包含一个值，每个节点至多有两个子树。每个节点左子树节点的值都小于自身的值，每个节点右子树节点的值都大于自身的值。


二叉树的查询时间复杂度是 log(N)，但是随着不断的插入、删除节点，二叉树的树高可能会不断变大，当一个二叉搜索树所有节点都只有左子树或者都只有右子树时，其查找性能就退化成线性的了。

平衡二叉树可以解决上面这个问题，平衡二叉树保证每个节点左右子树的高度差的绝对值不超过 1，例如 AVL 树。AVL 树是严格的平衡二叉树，插入或删除数据时可能经常需要旋转来保持平衡，比较适合插入、删除比较少的场景。

红黑树是一种更加实用的非严格的平衡二叉树。红黑树更关注局部平衡而非整体平衡，确保没有一条路径会比其他路径长出 2 倍，所以是接近平衡的，但减少了许多不必要的旋转操作，更加实用。前面提到过，Java 8 的 HashMap 中就应用了红黑树来解决散列冲突时的查找问题。TreeMap 也是通过红黑树来保证有序性的。

红黑树除了拥有二叉搜索树的特点外，还有以下规则，如下图所示。


红黑树特点如下：

1. 每个节点不是红色就是黑色。

2. 根节点是黑色。

3. 每个叶子节点都是黑色的空节点，如图中的黑色三角。

4. 红色节点的两个子节点都是黑色的。

5. 任意节点到其叶节点的每条路径上，包含相同数量的黑色节点。

B 树是一种多叉树，也叫多路搜索树。B 树中每个节点可以存储多个元素，非常适合用在文件索引上，可以有效减少磁盘 IO 次数。B 树中所有结点的最大子节点数称为 B 树的阶，如下图所示是一棵 3 阶 B 树，也叫 2-3 树。


一个 m 阶 B 树有如下特点：

1. 非叶节点最多有 m 棵子树；

2. 根节点最少有两个子树，非根、非叶节点最少有 m/2 棵子树；

3. 非叶子结点中保存的关键字个数，等于该节点子树个数−1，就是说一个节点如果有 3棵子树，那么其中必定包含 2 个关键字；

4. 非叶子节点中的关键字大小有序，如上图中左边的节点中 37、51 两个元素就是有序的；

5. 节点中每个关键字的左子树中的关键字都小于该关键字，右子树中的关键字都大于该关键字。如上图中关键字 51 的左子树有 42、49，都小于 51，右子树的节点有 59，大于51；

6. 所有叶节点都在同一层。

B 树在查找时，从根结点开始，对结点内的有序的关键字序列进行二分查找，如果找到就结束，没有找到就进入查询关键字所属范围的子树进行查找，直到叶节点。

**总结一下：**

- B 树的关键字分布在整颗树中，一个关键字只出现在一个节点中；

- 搜索可能在非叶节点停止；

- B 树一般应用在文件系统。

下图是 B 树的一个变种，叫作 B+ 树。


B+ 树的定义与 B 树基本相同，除了下面这几个特点。

1. 节点中的关键字与子树数目相同，比如节点中有 3 个关键字，那么就有 3 棵子树；

2. 关键字对应的子树中的节点都大于或等于关键字，子树中包括关键字自身；

3. 所有关键字都出现在叶子节点中；

4. 所有叶子节点都有指向下一个叶子节点的指针。

**与 B 树不同，B+ 树在搜索时不会在非叶子节点命中，一定会查询到叶子节点；另外一个，叶子节点相当于数据存储层，保存关键字对应的数据，而非叶子节点只保存关键字和指向叶节点的指针，不保存关键字对应的数据，所以同样数量关键字的非叶节点，B+ 树比 B 树要小很多。**

**（重点）**B+ 树更适合索引系统，MySQL 数据库的索引就提供了 B+ 树实现。原因有三个：

1. 由于叶节点之间有指针相连，B+ 树更适合范围检索；

2. 由于非页节点只保存关键字和指针，同样大小非叶节点，B+ 树可以容纳更多的关键字，可以降低树高，查询时磁盘读写代价更低；

3. B+ 树的查询效率比较稳定。任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，效率相当。

4. 最后可以简单了解，还有一种 B* 树的变种，在 B+ 树的非叶节点上，也增加了指向同一层下一个非叶节点的指针。

来看算法部分的知识点汇总，如下图所示。

<imgsrc="http://s0.lgstatic.com/i/image2/M01/8A/C1/CgoB5l14oT6ARislAAIosv-_rkU883.png"alt="img"style="zoom:80%;" />

算法题的常用解题方法。

1. 复杂度是衡量算法好坏的标准之一，我们需要掌握计算算法时间复杂度和空间复杂度的方法。计算时间复杂度的方法一般是找到执行次数最多的语句，然后计算语句执行次数的数量级，最后用大写 O 来表示结果。

2. 常用的字符串匹配算法，了解不同算法的匹配思路。

3. 排序也是经常考察的知识点，排序算法分为插入、交换、选择、归并、基数五类，其中快速排序和堆排序考察的频率最高，要重点掌握，需要能够手写算法实现。

4. 常用的查找算法，包括二分查找、二叉排序树、B 树、Hash、BloomFilter 等，需要了解它们的适用场景，例如二分查找适合小数量集内存查找，B 树适合文件索引，Hash 常数级的时间复杂度更适合对查找效率要求较高的场合，BloomFilter 适合对大数据集进行数据存在性过滤。

算法的知识点比较多，提高算法解题能力需要适当刷题，但不能单纯依靠刷题来解决问题。需要掌握几种常用解题思路与方法，才能以不变应万变。这里讲一下：分治、动态规划、贪心、回溯和分支界定这五种常用的算法题解题方法，来看看它们分别适用于什么场景，如何应用。

分治法的思想是将一个难以直接解决的复杂问题或者大问题，分割成一些规模较小的相同问题，分而治之。比如快速排序、归并排序等都是应用了分治法。

适合使用分治法的场景需要满足三点要求：

1. 可以分解为子问题；

2. 子问题的解可以合并为原问题的解；

3. 子问题之间没有关联。

使用分治法解决问题的一般步骤如下图表格所示。


1. 第一步，要找到最小子问题的求解方法；

2. 第二步，要找到合并子问题解的方法；

3. 第三步，要找到递归终止条件。

动态规划法，与分治法类似，也是将问题分解为多个子问题。与分治法不同的是，子问题的解之间是有关联的。前一子问题的解，为后一子问题的求解提供了有用的信息。动态规划法依次解决各子问题，在求解每一个子问题时，列出所有局部解，通过决策保留那些有可能达到全局最优的局部解。最后一个子问题的解就是初始问题的解。

使用动态规划的场景需要也满足三点条件：

1. 子问题的求解必须是按顺序进行的；

2. 相邻的子问题之间有关联关系；

3. 最后一个子问题的解就是初始问题的解。

使用动态规划解决问题时，如上图表格第二行。

1. 第一步，先要分析最优解的性质；

2. 第二步，递归的定义最优解；

3. 第三步，记录不同阶段的最优值；

4. 第四步，根据阶段最优解选择全局最优解

第三个贪心算法，因为它考虑的是局部的最优解，所以贪心算法不是对所有问题都能得到整体最优解。贪心算法的关键是贪心策略的选择。贪心策略必须具备无后效性，就是说某个状态以后的过程不会影响以前的状态，只与当前状态有关。

贪心算法使用的场景必须满足两点：

1. 局部最优解能产生全局最优解；

2. 就是刚才说的必须具备无后效性。

如下图所示，使用贪心算法解题的一般步骤为：


1. 第一步，先分解为子问题；

2. 第二步、按贪心策略计算每个子问题的局部最优解；

3. 第三步，合并局部最优解。

回溯算法实际上是一种深度优先的搜索算法，按选优的条件向前搜索，当探索到某一步时，发现原先选择并不优或达不到目标，就退回上一步重新选择，这种走不通就退回再走的方法就是回溯法。

回溯法适用于能够深度优先搜索，并且需要获取解空间的所有解的场合，例如迷宫问题等。

如上图所示，回溯法一般的解题步骤为：

1. 第一步先针对所给问题，确定问题的解空间；

2. 第二步、确定结点的扩展搜索规则；

3. 第三步，以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

最后是分支界定法，与回溯法的求解目标不同。回溯法的求解目标是找出满足约束条件的所有解，而分支界定法的求解目标则是找出满足约束条件的一个解。

分支界定法适用于广度优先搜索，并且获取解空间的任意解就可以的场合，例如求解整数规划问题。

如上图所示，分支界定法一般的解题步骤：

1. 第一步先确定解的特征；

2. 第二步在确定子节点搜索策略，例如是先入先出，还是先入后出；

3. 第三步通过广度优先遍历寻找解。