数据结构与算法面试题（爪哇程序员）

什么是算法？

原文：https://zwmst.com/1020.html

算法简单来说就是解决问题的步骤。

在Java中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。

一、算法的五个特征

①、有穷性：对于任意一组合法输入值，在执行又穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。 ②、确定性：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

③、可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

④、有输入：作为算法加工对象的量值，通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

⑤、有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法功能。

二、算法的设计原则

①、正确性：首先，算法应当满足以特定的“规则说明”方式给出的需求。其次，对算法是否 “正确”的理解可以有以下四个层次：

一、程序语法错误。

二、程序对于几组输入数据能够得出满足需要的结果。

三、程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果。

四、程序对于一切合法的输入数据都能得到满足要求的结果。

PS：通常以第三层意义的正确性作为衡量一个算法是否合格的标准。

②、可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。

③、健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

④、高效率与低存储量需求：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。

前面三点正确性，可读性和健壮性相信都好理解。对于第四点算法的执行效率和存储量，我们知道比较算法的时候，可能会说“A算法比B算法快两倍”之类的话，但实际上这种说法没有任何意义。因为当数据项个数发生变化时，A算法和B算法的效率比例也会发生变化，比如数据项增加了50%，可能A算法比B算法快三倍，但是如果数据项减少了50%，可能A算法和B算法速度一样。所以描述算法的速度必须要和数据项的个数联系起来。也就是“大O”表示法，它是一种算法复杂度的相对表示方式，这里我简单介绍一下，后面会根据具体的算法来描述。

相对(relative)：你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是，比较2个算法所做的算术操作（一个做乘法，一个做加法）将会告诉你一些有意义的东西；

表示(representation)：大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。例如，排序算法之间的对比通常是基于比较操作(比较2个结点来决定这2个结点的相对顺序)。这里面就假设了比较操作的计算开销很大。但是，如果比较操作的计算开销不大，而交换操作的计算开销很大，又会怎么样呢？这就改变了先前的比较方式；

复杂度(complexity)：如果排序10,000个元素花费了我1秒，那么排序1百万个元素会花多少时间？在这个例子里，复杂度就是相对其他东西的度量结果。

然后我们在说说算法的存储量，包括：

程序本身所占空间；

输入数据所占空间；

辅助变量所占空间；

一个算法的效率越高越好，而存储量是越低越好。

TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

原文：https://zwmst.com/1024.html

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的 compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort 方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

如何知道二叉树的深度？

原文：https://zwmst.com/1026.html

实现二叉树的深度方式有两种，递归以及非递归。

①递归实现：

为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；

②非递归实现：

利用层次遍历的算法，设置变量level记录当前节点所在的层数，设置变量last指向当前层的最后一个节点，当处理完当前层的最后一个节点，让level指向+1操作。设置变量cur记录当前层已经访问的节点的个数，当cur等于last时，表示该层访问结束。

层次遍历在求树的宽度、输出某一层节点，某一层节点个数，每一层节点个数都可以采取类似的算法。

树的宽度：在树的深度算法基础上，加一个记录访问过的层节点个数最多的变量max,在访问每层前max与last比较，如果max比较大，max不变，如果max小于last，把last赋值给max;

介绍一下，堆排序的原理是什么？

原文：https://zwmst.com/1028.html

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

（1）最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

（2）创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆。

（3）堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

数组和链表的区别

原文：https://zwmst.com/1030.html

1、数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

2、链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

二分查找了解过吗？

原文：https://zwmst.com/1032.html

**查找思路

【a】待查找有序数组序列：1, 2, 3, 4, 5, 6, 7

起始：定义start = 0 , end = 6, mid = (start + end ) / 2 = (0 + 6) / 2 = 3,arr[mid] = arr[3] =4

【b】假设需要查找"2", 因为2 arr[mid] = arr[3] = 4,所以需要将start移动到mid右边一个位置，即start = mid + 1 = 4,此时重新计算mid = (start +end) / 2 = (4+ 6)/2 = 5, arr[mid] = arr[5] = 6, 因为7>arr[mid] = arr[5] = 6,所以还是需要将start移动到mid右边一个位置，即start = mid + 1 = 5 + 1 = 6, 此时重新计算mid = (start +end) / 2 = (6 + 6) / 2 = 6.arr[6] = 7, 此时arr[mid] = arr[6] = 7,刚好等于待查找数字7，说明成功找到数字"7"所在的位置.

【d】假设查找"0", 因为 0 < arr[mid] = arr[3] = 4, 所以需要将end移动到mid左边一个位置，即end = mid – 1 = 3 – 1 = 2,此时重新计算mid = (start +end) / 2 = (0 + 2) / 2 = 1,arr[mid] = arr[1] = 2, 因为0 < arr[mid] = arr[1] = 2,所以需要将end移动到mid左边一个位置，即end = mid – 1 = 1 – 1 = 0, 此时mid = (start +end) / 2 = (0 + 0) / 2 = 0,arr[mid] = arr[0] = 1,因为0 end，即start 已经大于end结束位置，说明没有找到相应的元素0。

**算法实现

public class BinarySearchUtils {

    /
     * 根据指定值查找在数组中的位置

     * @param arr   待查找有序数组
     * @param value 指定值
     * @return 返回值在数组中对应的下标位置
     */
    public static int binarySearch(int[] arr, int value) {
        //起始位置
        int start = 0;
        //结束位置
        int end = arr.length - 1;

        while (true) {
            //计算中间位置下标
            int mid = (start + end) / 2;
            //中间值
            int midValue = arr[mid];

            if (value == midValue) {
                return mid;
            } else {
                //待查找数值比中间值小,需要将
                if (midValue > value) {
                    end = mid - 1;
                } else {
                    //待查找数值比中间值大,需要将
                    start = mid + 1 start = mid + 1;
                }
            }
            if (start > end) { 
                //start > end,说明未找到相应的元素,返回
                -1 return -1;
            }
        }
    }
}

如何在一个1到100的整数数组中找到丢失的数字?

原文：https://zwmst.com/1034.html

如果是丢了一个数字，用个遍历把这些数字累加求和，

然后用（1 + 100）*100/2 减去这个累加的总和，就是少的那一个数.

如果是丢了一些数字，

方法一：

先 1-100 遍历创建一个字典，key为1-100，值默认都为NO。

然后把那一些数字作为一个数组，判断是否包含每一个key，包含那key，则那key的值改为 YES，

最后值为NO的数则为缺失的数字

方法二：

先排序,并创建一个用来装缺失数的空数组，排好序后遍历,最大的数用101减，其余用后一个值减去前一个值如果差值不是1而是为n，就把被减数分别加1到（n-1）得出的数保存下来就是缺少的数字

请你讲讲LRU算法的实现原理？

原文：https://zwmst.com/1036.html

①LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也很高”，反过来说“如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”，两种理解是一样的；常用于页面置换算法，为虚拟页式存储管理服务。

②达到这样一种情形的算法是最理想的：每次调换出的页面是所有内存页面中最迟将被使用的；这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU 算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。

为什么要设计后缀表达式，有什么好处？

原文：https://zwmst.com/1038.html

后缀表达式又叫逆波兰表达式，逆波兰记法不需要括号来标识操作符的优先级。

什么是B树?

原文：https://zwmst.com/1040.html

B树是一种多叉树，也叫多路搜索树，适合用于文件索引上，减少磁盘IO次数，子节点存储最大数成为B树的阶，图中为2-3树。

m阶B树特点：

非叶节点最多有m棵子树。

根节点最少有两棵子树，非根非叶节点最少有m/2棵子树。

非叶节点保存的关键字个数等于该节点子树个数-1。

非叶节点保存的关键字大小有序。

节点中每个关键字左子树的关键字都小于该该关键字，右子树的关键字都大于该该关键字。

所有叶节点都在同一层。

查找：

对节点关键字进行二分查找。

如果找不到，进入对应的子树进行二分查找，如此循环。

什么是B+树?

原文：https://zwmst.com/1042.html

B树的变种，拥有B树的特点

独有特点：

节点中的关键字与子树数目相同。

关键字对应的子树节点都大于等于该关键字，子树包含该关键字自身。

所有关键字都出现在叶节点之中。

所有叶节点都有指向下一个叶节点的指针。搜索：只在叶节点搜索。

叶子节点保存关键字和对应的数据，非叶节点只保存关键字和指向叶节点的指针，同等关键字数量的B树和B+树，B+树更小。

更适合做索引系统，原因：

由于叶节点有指针项链，B+树更适合做范围检索。由于非叶节点只保存关键字和指向叶节点的指针，B+树可以容纳更多的关键字，树层数变小，磁盘查询次数更低。

B+树的查询效率比较稳定，查询所有关键字的路径相同。（MySQL索引就提供了B+树的实现方式）

谈一谈，id全局唯一且自增，如何实现？

原文：https://zwmst.com/1044.html

SnowFlake雪花算法

雪花ID生成的是一个64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成：

snowflake id生成规则

1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。

41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。

10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。

12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

503.一致性算法-Paxos

原文：https://zwmst.com/4087.html

Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。zookeeper 使用的 zab 算法是该算法的一个实现。在 Paxos 算法中，有三种角色：Proposer，Acceptor，Learners

504.Proposer

原文：https://zwmst.com/4089.html

只要 Proposer 发的提案被半数以上 Acceptor 接受，Proposer 就认为该提案里的 value 被选定了。

505.Acceptor

原文：https://zwmst.com/4091.html

只要 Acceptor 接受了某个提案，Acceptor 就认为该提案里的 value 被选定了。

506.Learner

原文：https://zwmst.com/4093.html

Acceptor 告诉 Learner 哪个 value 被选定，Learner 就认为那个 value 被选定。

507.Paxos 算法分为两个阶段

原文：https://zwmst.com/4095.html

阶段一（准 leader 确定）：

Proposer 选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求。
如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。

阶段二（leader 确认）：

如果 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对[N,V]提案的 Accept 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定。
如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案。

508.Zab

原文：https://zwmst.com/4097.html

ZAB( ZooKeeper Atomic Broadcast , ZooKeeper 原子消息广播协议）协议包括两种基本的模式：崩溃恢复和消息广播

当整个服务框架在启动过程中，或是当 Leader 服务器出现网络中断崩溃退出与重启等异常情况时，ZAB 就会进入恢复模式并选举产生新的 Leader 服务器。
当选举产生了新的 Leader 服务器，同时集群中已经有过半的机器与该 Leader 服务器完成了状态同步之后，ZAB 协议就会退出崩溃恢复模式，进入消息广播模式。
当有新的服务器加入到集群中去，如果此时集群中已经存在一个 Leader 服务器在负责进行消息广播，那么新加入的服务器会自动进入数据恢复模式，找到 Leader 服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。

以上其实大致经历了三个步骤：

崩溃恢复：主要就是 Leader 选举过程
数据同步：Leader 服务器与其他服务器进行数据同步
消息广播：Leader 服务器将数据发送给其他服务器

509.Raft

原文：https://zwmst.com/4099.html

与 Paxos 不同 Raft 强调的是易懂（Understandability），Raft 和 Paxos 一样只要保证 n/2+1 节点正常就能够提供服务；raft 把算法流程分为三个子问题：选举（Leader election）、日志复制（Log replication）、安全性（Safety）三个子问题。

510.角色

原文：https://zwmst.com/4101.html

Raft 把集群中的节点分为三种状态：Leader、 Follower 、Candidate，理所当然每种状态负责的任务也是不一样的，Raft 运行时提供服务的时候只存在 Leader 与 Follower 两种状态；

Leader（领导者-日志管理）

负责日志的同步管理，处理来自客户端的请求，与 Follower 保持这 heartBeat 的联系；

Follower（追随者-日志同步）

刚启动时所有节点为Follower状态，响应Leader的日志同步请求，响应Candidate的请求，把请求到 Follower 的事务转发给 Leader；

Candidate（候选者-负责选票）

负责选举投票，Raft 刚启动时由一个节点从 Follower 转为 Candidate 发起选举，选举出Leader 后从 Candidate 转为 Leader 状态；

511.Term（任期）

原文：https://zwmst.com/4103.html

在 Raft 中使用了一个可以理解为周期（第几届、任期）的概念，用 Term 作为一个周期，每个 Term 都是一个连续递增的编号，每一轮选举都是一个 Term 周期，在一个 Term 中只能产生一个 Leader；当某节点收到的请求中 Term 比当前 Term 小时则拒绝该请求。

512.选举（Election）

原文：https://zwmst.com/4105.html

选举定时器

Raft 的选举由定时器来触发，每个节点的选举定时器时间都是不一样的，开始时状态都为Follower 某个节点定时器触发选举后 Term 递增，状态由 Follower 转为 Candidate，向其他节点发起 RequestVote RPC 请求，这时候有三种可能的情况发生：

该 RequestVote 请求接收到 n/2+1（过半数）个节点的投票，从 Candidate 转为 Leader，向其他节点发送 heartBeat 以保持 Leader 的正常运转。
在此期间如果收到其他节点发送过来的 AppendEntries RPC 请求，如该节点的 Term 大则当前节点转为 Follower，否则保持 Candidate 拒绝该请求。
Election timeout 发生则 Term 递增，重新发起选举

在一个 Term 期间每个节点只能投票一次，所以当有多个 Candidate 存在时就会出现每个Candidate 发起的选举都存在接收到的投票数都不过半的问题，这时每个 Candidate 都将 Term递增、重启定时器并重新发起选举，由于每个节点中定时器的时间都是随机的，所以就不会多次存在有多个 Candidate 同时发起投票的问题。

在 Raft 中当接收到客户端的日志（事务请求）后先把该日志追加到本地的 Log 中，然后通过heartbeat 把该 Entry 同步给其他 Follower，Follower 接收到日志后记录日志然后向 Leader 发送ACK，当 Leader 收到大多数（n/2+1）Follower 的 ACK 信息后将该日志设置为已提交并追加到本地磁盘中，通知客户端并在下个 heartbeat 中 Leader 将通知所有的 Follower 将该日志存储在自己的本地磁盘中。

513.安全性（Safety）

原文：https://zwmst.com/4107.html

安全性是用于保证每个节点都执行相同序列的安全机制如当某个Follower 在当前 Leader commit Log 时变得不可用了，稍后可能该 Follower 又会倍选举为 Leader，这时新 Leader 可能会用新的Log 覆盖先前已 committed 的 Log，这就是导致节点执行不同序列；Safety 就是用于保证选举出来的 Leader 一定包含先前 commited Log 的机制；

选举安全性（Election Safety）：每个 Term 只能选举出一个 Leader

Leader 完整性（Leader Completeness）：这里所说的完整性是指 Leader 日志的完整性，Raft 在选举阶段就使用 Term 的判断用于保证完整性：当请求投票的该 Candidate 的 Term 较大或 Term 相同 Index 更大则投票，该节点将容易变成 leader。

514.raft 协议和 zab 协议区别

原文：https://zwmst.com/4109.html

相同点

采用 quorum 来确定整个系统的一致性,这个 quorum 一般实现是集群中半数以上的服务器,
zookeeper 里还提供了带权重的 quorum 实现.
都由 leader 来发起写操作.
都采用心跳检测存活性
eader election 都采用先到先得的投票方式

不同点

zab 用的是 epoch 和 count 的组合来唯一表示一个值, 而 raft 用的是 term 和 index
zab 的 follower 在投票给一个 leader 之前必须和 leader 的日志达成一致,而 raft 的follower则简单地说是谁的 term 高就投票给谁
raft 协议的心跳是从 leader 到 follower, 而 zab 协议则相反
raft 协议数据只有单向地从 leader 到 follower(成为 leader 的条件之一就是拥有最新的 log)

而 zab 协议在 discovery 阶段, 一个 prospective leader 需要将自己的 log 更新为 quorum 里面最新的 log,然后才好在 synchronization 阶段将 quorum 里的其他机器的 log 都同步到一致.

515.NWR

原文：https://zwmst.com/4111.html

**N：在分布式存储系统中，有多少份备份数据 W：代表一次成功的更新操作要求至少有 w 份数据写入成功 R：代表一次成功的读数据操作要求至少有 R 份数据成功读取 NWR值的不同组合会产生不同的一致性效果，当W+R>N 的时候，整个系统对于客户端来讲能保证强一致性。而如果 R+W<=N，则无法保证数据的强一致性。以常见的 N=3、W=2、R=2 为例：

N=3，表示，任何一个对象都必须有三个副本（Replica），W=2 表示，对数据的修改操作（Write）只需要在 3 个 Replica 中的 2 个上面完成就返回，R=2 表示，从三个对象中要读取到 2个数据对象，才能返回。

516.Gossip

原文：https://zwmst.com/4115.html

Gossip 算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了 Gossip 的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的状态都是一致的，当然这也是疫情传播的特点。

517.一致性 Hash

原文：https://zwmst.com/4117.html

一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。Memcached client 也选择这种算法，解决将 key-value 均匀分配到众多 Memcached server 上的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删 Memcached Server 的问题(增删 server 会导致同一个 key,在 get 操作时分配不到数据真正存储的 server，命中率会急剧下降)。

518.一致性 Hash 特性

原文：https://zwmst.com/4119.html

平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。容易看到，上面的简单求余算法hash(object)%N 难以满足单调性要求。
平滑性(Smoothness)：平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

519.一致性 Hash 原理

原文：https://zwmst.com/4121.html

建构环形 hash 空间：

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环。

把需要缓存的内容(对象)映射到 hash 空间

接下来考虑 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布

把服务器(节点)映射到 hash 空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中，并且使用相同的 hash 算法。一般的方法可以使用服务器(节点) 机器的 IP 地址或者机器名作为hash 输入。

把对象映射到服务节点

现在服务节点和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，首先确定对象hash 值在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

520.考察 cache 的变动

原文：https://zwmst.com/4124.html

通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时，cache 会失效。

移除 cache：考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象。
添加 cache：再考虑添加一台新的 cache D 的情况，这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache 之间的对象，将这些对象重新映射到 cache D 上即可。

521.虚拟节点

原文：https://zwmst.com/4127.html

hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念，它可以如下定义：

虚拟节点（ virtual node ）是实际节点在 hash 空间的复制品（ replica ）一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。

仍以仅部署 cache A 和 cache C 的情况为例。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A； cache C1, cache C2 代表了 cache C 。此时，对象到“虚拟节点”的映射关系为：

objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；

因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如下图所示。

522.二分查找

原文：https://zwmst.com/4131.html

又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

public static int biSearch(int []array,int a){
 int lo=0;
 int hi=array.length-1;
 int mid;
 while(lo<=hi){
 mid=(lo+hi)/2;//中间位置
 if(array[mid]==a){
 return mid+1;
 }else if(array[mid]<a){ //向右查找
 lo=mid+1;
 }else{ //向左查找
 hi=mid-1;
 }
 }
 return -1;
 }

523.冒泡排序算法

原文：https://zwmst.com/4133.html

比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1 个位置。
N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。

public static void bubbleSort1(int [] a, int n){ int i, j; for(i=0; i<n; i++){//表示 n 次排序过程。 for(j=1; j<n-i; j++){ if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换 //交换 a[j-1]和 a[j] int temp; temp = a[j-1]; a[j-1] = a[j]; a[j]=temp; } } } }

524.插入排序算法

原文：https://zwmst.com/4135.html

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，**，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。

public void sort(int arr[])
 {
 for(int i =1; i<arr.length int="" insertval="arr[i];" index="i-1;" while="">=0&&insertVal</arr.length>

525.快速排序算法

原文：https://zwmst.com/4138.html

快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

public void sort(int[] a,int low,int high){
 int start = low;
 int end = high;
 int key = a[low]; 
 while(end>start){
 //从后往前比较
 while(end>start&&a[end]>=key) 
//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
 end--;
 if(a[end]<=key){
 int temp = a[end];
 a[end] = a[start];
 a[start] = temp;
 }
 //从前往后比较
 while(end>start&&a[start]<=key)
//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
 start++;
 if(a[start]>=key){
 int temp = a[start];
 a[start] = a[end];
 a[end] = temp;
 }
 //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的
值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
 }
 //递归
 if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
 if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1 到最后一个
 }
 }

526.希尔排序算法

原文：https://zwmst.com/4140.html

基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

private void shellSort(int[] a) { int dk = a.length/2; while( dk >= 1 ){ ShellInsertSort(a, dk); dk = dk/2; } } private void ShellInsertSort(int[] a, int dk) { //类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了 for(int i=dk;i<a.length;i++){ if(a[i]<a[i-dk]){ int j; int x=a[i];//x 为待插入元素 a[i]=a[i-dk]; for(j=i-dk; j>=0 && x<a[j];j=j-dk){ //通过循环，逐个后移一位找到要插入的位置。 a[j+dk]=a[j]; } a[j+dk]=x;//插入 } } }

527.归并排序算法

原文：https://zwmst.com/4145.html

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

public class MergeSortTest { 
 public static void main(String[] args) { 
 int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 
 print(data); 
 mergeSort(data); 
 System.out.println("排序后的数组："); 
 print(data); 
 } 
 public static void mergeSort(int[] data) { 
 sort(data, 0, data.length - 1); 
 } 
 public static void sort(int[] data, int left, int right) { 
 if (left >= right) 
 return; 
 // 找出中间索引 
 int center = (left + right) / 2; 
 // 对左边数组进行递归 
 sort(data, left, center); 
 // 对右边数组进行递归 
 sort(data, center + 1, right); 
 // 合并 
 merge(data, left, center, right); 
 print(data); 
 } 
 /
 * 将两个数组进行归并，归并前面 2 个数组已有序，归并后依然有序

 * @param data 
 * 数组对象
 * @param left 
 * 左数组的第一个元素的索引
 * @param center 
 * 左数组的最后一个元素的索引，center+1 是右数组第一个元素的索引
 * @param right 
 * 右数组最后一个元素的索引
 */ 
 public static void merge(int[] data, int left, int center, int right) { 
 // 临时数组 
 int[] tmpArr = new int[data.length]; 
 // 右数组第一个元素索引 
 int mid = center + 1; 
 // third 记录临时数组的索引 
 int third = left; 
 // 缓存左数组第一个元素的索引 
 int tmp = left; 
 while (left <= center && mid <= right) { 
 // 从两个数组中取出最小的放入临时数组 
 if (data[left] <= data[mid]) { 
 tmpArr[third++] = data[left++]; 
 } else { 
 tmpArr[third++] = data[mid++]; 
 } 
 } 
 // 剩余部分依次放入临时数组（实际上两个 while 只会执行其中一个） 
 while (mid <= right) { 
 tmpArr[third++] = data[mid++]; 
 } 
 while (left <= center) { 
 tmpArr[third++] = data[left++]; 
 } 
 // 将临时数组中的内容拷贝回原数组中 
 // （原 left-right 范围的内容被复制回原数组） 
 while (tmp <= right) { 
 data[tmp] = tmpArr[tmp++]; 
 } 
 } 
 public static void print(int[] data) { 
 for (int i = 0; i < data.length; i++) { 
 System.out.print(data[i] + "\t"); 
 } 
 System.out.println(); 
 } 
 }

528.桶排序算法

原文：https://zwmst.com/4147.html

桶排序的基本思想是：把数组 arr 划分为 n 个大小相同子区间（桶），每个子区间各自排序，最后合并。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

找出待排序数组中的最大值 max、最小值 min
我们使用动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max*min)/arr.length+1
遍历数组 arr，计算每个元素 arr[i] 放的桶
每个桶各自排序

 public static void bucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//创建桶
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
}

529.基数排序算法

原文：https://zwmst.com/4149.html

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

530.剪枝算法

原文：https://zwmst.com/4153.html

在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

531.回溯算法

原文：https://zwmst.com/4155.html

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

532.最短路径算法

原文：https://zwmst.com/4157.html

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA算法等。

533.最小生成树算法

原文：https://zwmst.com/4159.html

现在假设有一个很实际的问题：我们要在 n 个城市中建立一个通信网络，则连通这 n 个城市需要布置 n-1 一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？于是我们就可以引入连通图来解决我们遇到的问题，n 个城市就是图上的 n 个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有 n 个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST 性质（假设N=(V,{E})是一个连通网，U 是顶点集 V 的一个非空子集，如果（u，v）是一条具有最小权值的边，其中 u 属于 U，v 属于 V-U，则必定存在一颗包含边（u，v）的最小生成树）。

534.栈（stack）

原文：https://zwmst.com/4162.html

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶（top）。它是后进先出（LIFO）的。对栈的基本操作只有 push（进栈）和 pop（出栈）两种，前者相当于插入，后者相当于删除最后的元素。

535.队列（queue）

原文：https://zwmst.com/4164.html

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

536.链表（Link）

原文：https://zwmst.com/4166.html

链表是一种数据结构，和数组同级。比如，Java 中我们使用的 ArrayList，其实现原理是数组。而LinkedList 的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。

537.散列表（Hash Table）

原文：https://zwmst.com/4168.html

散列表（Hash table，也叫哈希表）是一种查找算法，与链表、树等算法不同的是，散列表算法在查找时不需要进行一系列和关键字（关键字是数据元素中某个数据项的值，用以标识一个数据元素）的比较操作。 散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素，因而必须要在数据元素的存储位置和它的关键字（可用 key 表示）之间建立一个确定的对应关系，使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时，只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。用的构造散列函数的方法有：

直接定址法：取关键字或关键字的某个线性函数值为散列地址。即：h(key) = key 或 h(key) = a * key + b，其中 a 和 b 为常数。
1. 数字分析法
2. 平方取值法：取关键字平方后的中间几位为散列地址。
3. 折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。
4. 除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址，即：h(key) = key MOD p p ≤ m
随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址，即：h(key) = random(key)

538.排序二叉树

原文：https://zwmst.com/4170.html

首先如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值大于它的根节点值，则这样的二叉树就是排序二叉树。

539.插入操作

原文：https://zwmst.com/4172.html

首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。

540.删除操作

原文：https://zwmst.com/4174.html

删除操作主要分为三种情况，即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。

对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
对于要删除的节点有两个子节点，则首先找该节点的替换节点（即右子树中最小的节点），接着替换要删除的节点为替换节点，然后删除替换节点。

541.查询操作

原文：https://zwmst.com/4176.html

查找操作的主要流程为：先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。

542.红黑树

原文：https://zwmst.com/4179.html

R-B Tree，全称是 Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

543.红黑树的特性

原文：https://zwmst.com/4181.html

每个节点或者是黑色，或者是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL 或NULL)的叶子节点！]
如果一个节点是红色的，则它的子节点必须是黑色的。
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

544.左旋

原文：https://zwmst.com/4183.html

对 x 进行左旋，意味着，将“x 的右孩子”设为“x 的父亲节点”；即，将 x 变成了一个左节点(x成了为 z 的左孩子)！。因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。

LEFT-ROTATE(T, x) 
y ← right[x] // 前提：这里假设 x 的右孩子为 y。下面开始正式操作
right[x] ← left[y] // 将 “y 的左孩子” 设为 “x 的右孩子”，即 将β设为 x 的右孩子
p[left[y]] ← x // 将 “x” 设为 “y 的左孩子的父亲”，即 将β的父亲设为 x
p[y] ← p[x] // 将 “x 的父亲” 设为 “y 的父亲”
if p[x] = nil[T] 
then root[T] ← y // 情况 1：如果 “x 的父亲” 是空节点，则将 y 设为根节点
else if x = left[p[x]] 
 then left[p[x]] ← y // 情况 2：如果 x 是它父节点的左孩子，则将 y 设为“x 的父节点
的左孩子”
 else right[p[x]] ← y // 情况 3：(x 是它父节点的右孩子) 将 y 设为“x 的父节点的右孩
子”
left[y] ← x // 将 “x” 设为 “y 的左孩子”
p[x] ← y // 将 “x 的父节点” 设为 “y”

545.右旋

原文：https://zwmst.com/4185.html

对 x 进行右旋，意味着，将“x 的左孩子”设为“x 的父亲节点”；即，将 x 变成了一个右节点(x成了为 y 的右孩子)！因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

 RIGHT-ROTATE(T, y) 
x ← left[y] // 前提：这里假设 y 的左孩子为 x。下面开始正式操作
left[y] ← right[x] // 将 “x 的右孩子” 设为 “y 的左孩子”，即 将β设为 y 的左孩子
p[right[x]] ← y // 将 “y” 设为 “x 的右孩子的父亲”，即 将β的父亲设为 y
p[x] ← p[y] // 将 “y 的父亲” 设为 “x 的父亲”
if p[y] = nil[T] 
then root[T] ← x // 情况 1：如果 “y 的父亲” 是空节点，则将 x 设为根节点
else if y = right[p[y]] 
 then right[p[y]] ← x // 情况 2：如果 y 是它父节点的右孩子，则将 x 设为“y 的父节
点的左孩子”
 else left[p[y]] ← x // 情况 3：(y 是它父节点的左孩子) 将 x 设为“y 的父节点的左孩
子”
right[x] ← y // 将 “y” 设为 “x 的右孩子”
p[y] ← x // 将 “y 的父节点” 设为 “x”

546.添加

原文：https://zwmst.com/4187.html

第一步: 将红黑树当作一颗二叉查找树，将节点插入。第二步：将插入的节点着色为"红色"。

根据被插入节点的父节点的情况，可以将"当节点 z 被着色为红色节点，并插入二叉树"划分为三种情况来处理。

情况说明：被插入的节点是根节点。处理方法：直接把此节点涂为黑色。
情况说明：被插入的节点的父节点是黑色。处理方法：什么也不需要做。节点被插入后，仍然是红黑树。
情况说明：被插入的节点的父节点是红色。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为 3 种情况(Case)。

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

547.删除

原文：https://zwmst.com/4190.html

第一步：将红黑树当作一颗二叉查找树，将节点删除。

这和"删除常规二叉查找树中删除节点的方法是一样的"。分 3 种情况：

被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就 OK 了。
被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。

第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。

因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。

选择重着色 3 种情况。

情况说明：x 是“红+黑”节点。处理方法：直接把 x 设为黑色，结束。此时红黑树性质全部恢复。
情况说明：x 是“黑+黑”节点，且 x 是根。处理方法：什么都不做，结束。此时红黑树性质全部恢复。
情况说明：x 是“黑+黑”节点，且 x 不是根。处理方法：这种情况又可以划分为 4 种子情况。这 4 种子情况如下表所示：

参考：https://www.jianshu.com/p/038585421b73 代码实现：https://www.cnblogs.com/skywang12345/p/3624343.html

548.B-TREE

原文：https://zwmst.com/4193.html

B-tree 又叫平衡多路查找树。一棵 m 阶的 B-tree (m 叉树)的特性如下（其中 ceil(x)是一个取上限的函数）：

树中每个结点至多有 m 个孩子；
除根结点和叶子结点外，其它每个结点至少有有 ceil(m / 2)个孩子；
若根结点不是叶子结点，则至少有 2 个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，实际上这些结点不存在，指向这些结点的指针都为 null)；
每个非终端结点中包含有 n 个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
1. Ki (i=1…n)为关键字，且关键字按顺序排序 K(i-1)< Ki。
2. Pi 为指向子树根的接点，且指针 P(i-1)指向子树种所有结点的关键字均小于 Ki，但都大于 K(i*1)。
3. 关键字的个数 n 必须满足： ceil(m / 2)-1 <= n <= m-1。

一棵 m 阶的 B+tree 和 m 阶的 B-tree 的差异在于：

有 n 棵子树的结点中含有 n 个关键字； (B-tree 是 n 棵子树有 n-1 个关键字)
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B-tree 的叶子节点并没有包括全部需要查找的信息)
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(B-tree 的非终节点也包含需要查找的有效信息)

549.位图

原文：https://zwmst.com/4195.html

位图的原理就是用一个 bit 来标识一个数字是否存在，采用一个 bit 来存储一个数据，所以这样可以大大的节省空间。 bitmap 是很常用的数据结构，比如用于 Bloom Filter 中；用于无重复整数的排序等等。bitmap 通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。 https://www.cnblogs.com/polly333/p/4760275.html

550.加密算法-AES

原文：https://zwmst.com/4197.html

高级加密标准(AES,Advanced Encryption Standard)为最常见的对称加密算法(微信小程序加密传输就是用这个加密算法的)。对称加密算法也就是加密和解密用相同的密钥，具体的加密流程如下图：

551.RSA

原文：https://zwmst.com/4200.html

RSA 加密算法是一种典型的非对称加密算法，它基于大数的因式分解数学难题，它也是应用最广泛的非对称加密算法。非对称加密是通过两个密钥（公钥-私钥）来实现对数据的加密和解密的。公钥用于加密，私钥用于解密。

552.CRC

原文：https://zwmst.com/4204.html

循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

553.MD5

原文：https://zwmst.com/4206.html

MD5 常常作为文件的签名出现，我们在下载文件的时候，常常会看到文件页面上附带一个扩展名为.MD5 的文本或者一行字符，这行字符就是就是把整个文件当作原数据通过 MD5 计算后的值，我们下载文件后，可以用检查文件 MD5 信息的软件对下载到的文件在进行一次计算。两次结果对比就可以确保下载到文件的准确性。另一种常见用途就是网站敏感信息加密，比如用户名密码，支付签名等等。随着 https 技术的普及，现在的网站广泛采用前台明文传输到后台，MD5 加密（使用偏移量）的方式保护敏感数据保护站点和数据安全。

我们一直在努力

apachecn/AiLearning