场景 同一个网页链接被包含在多个页面中时，会导致爬虫在爬取的过程中，重复爬取相同的网页，如何避免这些重复的爬取呢？ 解决方案 记录已经爬取过的URL，爬取新网页前查看是否爬取过 已爬取过则忽略 未爬取过则先爬取后记录 注意点： 查询和添加操作要高效 上亿的网页，消耗内存非常高，存储效率要高 满足上述需求的数据结构有： 散列表 红黑树 跳表 在支持快速查询和插入的同时需要关注内存的消耗。 假设有10亿网页，一条URL平均长度64byte，全部存储起来需要大约60GB的内存。散列表需要保证较低的装填因子，采用链表法则还需要保存指针，实际使用的存储空间可能需要超过100GB。大型搜索引擎会使用分治的思想将这100GB的数据保存在多台服务器上。 分治+散列表的思路可以实现，那么在添加、查询和内存消耗上是否还有优化空间？ 注意：时间复杂度只是表示执行时间随数据规模的变化趋势，并不能度量在特定的数据规模下，代码执行时间的多少。在数据量很大的情况下，常数、系数和低阶的优化都能带来非常可观的收益。 性能优化 执行效率 分治+散列表思路中耗时的点在于：通过哈希函数定位到某个链表之后，还要依次比对每个链表中的 URL。 一方面，链表中的结点在内存中不是连续存储的，不能一下子加载到 CPU 缓存中，没法很好地利用到 CPU 高速缓存，所以数据访问性能方面会打折扣。 另一方面，链表中的每个数据都是 URL，而 URL 不是简单的数字，是平均长度为 64 字节的字符串，要让待判重的 URL，跟链表中的每个 URL，做字符串匹配。这样一个字符串匹配操作，比起单纯的数字比对，要慢很多。 内存消耗 在内存消耗方面的优化，可以将散列表更换为布隆过滤器。布隆过滤器基于位图，且对位图进行了改进。 位图 问题 如何在数据范围是1~1亿之间的1千万个整数中快速查找某个整数是否存在。 散列表可以解决，位图也可以解决。 解决方案 使用位图来解决。 申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组 将这 1 千万个整数作为数组下标，将对应的数组值设置成 true，如整数 5 对应下标为 5 的数组值设置为 true（array[5]=true） 查询某个整数 K 是否存在，只要将对应的数组值 array[K] 取出来判断是否为true 如果等于 true，说明存在整数 K 如果不等于true，说明不存在整数 K 注意：很多编程语言中提供的布尔类型，大小是 1 byte，并不能节省太多内存空间。实际上，表示 true 和 false 两个值，只需要用一个二进制位（bit）就可以。 如何通过编程语言，来表示一个二进制位（bit）可以使用位运算。 借助编程语言中提供的数据类型，比如 int、long、char 等类型，通过位运算，用其中的某个位表示某个数字。如下示例： // byte占1个字节，8bit type BitMap struct { bytes []byte nbits int } func NewBitMap(bits int) *BitMap { return &BitMap{ bytes: make([]byte, bits/8+1), nbits: bits, } } func (b *BitMap) set(k int) { if k > b.nbits { return } byteIndex := k / 8 bitIndex := k % 8 b.bytes[byteIndex] |= 1 << bitIndex } func (b *BitMap) get(k int) bool { if k > b.nbits { return false } byteIndex := k / 8 bitIndex := k % 8 return (b.bytes[byteIndex] & (1 << bitIndex)) != 0 } 位图通过数组下标来定位数据，所以访问效率非常高 每个数字用一个二进制位（bit）表示，在数字范围不大的情况下，需要的内存空间非常节省 数据范围是1~1亿之间的1千万数据： 散列表存储：每个数据占32位（4个字节），总共有1千万个数据需要大约40MB 位图存储：每个数据占1位，数据最大范围1亿需要大约12.5MB 如果数据的范围更大，是1~10亿，数据量还是1千万，那么位图存储的空间是125MB，这就远大于散列表需要的存储空间。 这是就需要布隆过滤器来解决数据范围非常大这个问题了。 布隆过滤器 数据范围是1~10亿之间的1千万数据，使用布隆过滤器的处理策略是： 创建一个 1 亿个二进制大小的位图 通过哈希函数（如f(x)=x%n，n表示位图大小，即对数字跟位图的大小进行取模求余），对数字进行处理，让它落在这 1 到 1 亿范围内 注意：哈希会存在冲突，如一亿零一和 1 两个数字最终都存储在1这个位置。为了降低这种冲突概率，可以设计一个复杂点、随机点的哈希函数。 布隆过滤器的处理方法是：一个哈希函数可能会存在冲突，用多个哈希函数一块儿定位一个数据，来降低冲突的概率。 使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，分别记作 X1，X2，X3，…，XK 把这 K 个数字作为位图中的下标，将对应的 BitMap[X1]，BitMap[X2]，BitMap[X3]，…，BitMap[XK]都设置成 true，用 K 个二进制位，来表示一个数字的存在 查询某个数字是否存在的时候，用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，YK 看这 K 个哈希值，对应位图中的数值是否都为 true 如果都是 true，则说明这个数字存在 如果其中任意一个不为 true，说明这个数字不存在 对于两个不同的数字来说，经过一个哈希函数处理，可能会产生相同的哈希值。但是经过 K 个哈希函数处理之后，K 个哈希值都相同的概率就非常低了。 尽管采用 K 个哈希函数之后，两个数字哈希冲突的概率降低了，但是，这种处理方式又带来了新的问题，那就是容易误判。 bloom filter: False is always false. True is maybe true. 布隆过滤器只会对存在有误判： 如果某个数字经过布隆过滤器判断不存在，那这个数字真的不存在，不会误判 如果某个数字经过布隆过滤器判断存在，这时有可能误判，可能数字并不存在 只要调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，就可以将这种误判的概率降到非常低。 布隆过滤器的误判率，主要跟哈希函数的个数、位图的大小有关。 往布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来越高。所以，对于无法事先知道要判重的数据个数的情况，需要支持自动扩容的功能 当布隆过滤器中，数据个数与位图大小的比例超过某个阈值，就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中 如果要判断某个数据是否在布隆过滤器中已经存在，就需要查看多个位图，相应的执行效率就降低了一些 一般不用来删除，如果非要支持删除，可以再弄个数据结构记录删除的数据。 应用 尽管布隆过滤器会存在误判，但是，这并不影响它发挥大作用。很多场景对误判有一定的容忍度。 比如要解决的爬虫判重这个问题，即便一个没有被爬取过的网页，被误判为已经被爬取，对于搜索引擎来说，也并不是什么大事情，是可以容忍的，毕竟网页太多了，搜索引擎也不可能 100% 都爬取到。 布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。 比如，统计一个大型网站的每天的 UV（Unique Visitor，独立访客） 数，就可以使用布隆过滤器，对重复访问的用户进行去重。 存储优化 使用布隆过滤器解决爬虫去重问题： 用布隆过滤器来记录已经爬取过的网页链接 假设需要判重的网页有 10 亿，那可以用一个 10 倍大小的位图（100 亿个二进制位，约 1.2GB）来存储 用散列表判重，需要至少 100GB 的空间 相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多 执行优化 布隆过滤器用多个哈希函数对同一个网页链接进行处理 CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的 在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的 CPU 计算要比内存访问更快速，所以，理论上布隆过滤器的判重方式，更加快速 工业实现 Java 中的 BitSet 类是一个位图 Redis 提供了 BitMap 位图类 Google 的 Guava 工具包提供了 BloomFilter 布隆过滤器的实现
0.1. 贪心算法 0.1.1. 例子 0.1.2. 定义 0.1.3. 实战 0.1.3.1. 分糖果 0.1.3.2. 钱币找零 0.1.3.3. 区间覆盖 0.1.4. 霍夫曼编码 0.2. 分治算法 0.2.1. 分治算法应用 0.2.2. 分治算法海量数据应用 0.3. 回溯算法 0.3.1. 经典应用 0.3.1.1. 0-1背包 0.3.1.2. 正则表达式 0.4. 动态规划 0.4.1. 动态规划问题模型 0.4.1.1. 0-1背包问题 0.4.1.1.1. 回溯解题 0.4.1.1.2. 动态规划解题 0.4.1.2. -1背包问题升级版 0.4.2. 动态规划理论 0.4.2.1. 具体问题 0.4.3. 动态规划解题思路 0.4.3.1. 状态转移表法 0.4.3.2. 状态转移方程法 0.4.4. 动态规划实战 0.4.4.1. 编程计算莱文斯坦距离 0.4.4.2. 编程计算最长公共子串长度 0.5. 四种算法比较 0.5.1. 回溯 0.5.2. 动态规划 0.5.3. 分治 0.5.4. 贪心 0.1. 贪心算法 贪心算法有很多经典的应用，比如：
霍夫曼编码（Huffman Coding） Prim Kruskal 最小生成树算法 Dijkstra 单源最短路径算法 0.1.1. 例子 假设有一个可以容纳 100kg 物品的背包，可以装各种物品。 有以下 5 种豆子，每种豆子的总量和总价值都各不相同。 为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？ 物品 总量(KG) 总价值(元) 黄豆 100 100 绿豆 30 90 红豆 60 120 黑豆 20 80 青豆 50 75 先算一算每个物品的单价，按照单价由高到低依次来装 单价从高到低排列，依次是：黑豆、绿豆、红豆、青豆、黄豆 所以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆 这个问题的解决思路本质上就是贪心算法。
0.1.2. 定义 第一步，当看到这个问题的时候，首先要联想到贪心算法：针对一组数据（5种豆子），定义了限制值（100kg）和期望值（总价值），希望从中选出几个数据，在满足限制值的情况下，期望值最大。
第二步，尝试下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量（重量相同）的情况下，对期望值（总价值）贡献最大的数据。
第三步，举几个例子看贪心算法产生的结果是否是最优。大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。
实际上，用贪心算法解决问题的思路，并不总能给出最优解。
在一个有权图中，从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。
贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。
按照这种思路，求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。
但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径，路径的长度是 2+2+2=6。
在这个问题上，贪心算法不工作的主要原因是，前面的选择，会影响后面的选择。如果第一步从顶点 S 走到顶点 A，那接下来面对的顶点和边，跟第一步从顶点 S 走到顶点 B，是完全不同的。所以，即便第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。
0.1.3. 实战 0.1.3.1. 分糖果 有 m 个糖果和 n 个孩子，现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配给一部分孩子。每个糖果的大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。如何分配糖果，能尽可能满足最多数量的孩子？
把这个问题抽象成：
一组数据：从 n 个孩子中，抽取一部分孩子分配糖果 限制值：糖果个数 m 期望值：让满足的孩子的个数是最大的 用贪心算法来解决。
对于一个孩子来说，如果小的糖果可以满足，就没必要用更大的糖果，这样更大的就可以留给其他对糖果大小需求更大的孩子。对糖果大小需求小的孩子更容易被满足，所以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对期望值的贡献是一样的。 每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。 0.1.3.2. 钱币找零 假设有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。现在要用这些钱来支付 K 元，最少要用多少张纸币呢？
把这个问题抽象成：
一组数据：若干纸币 限制值：K元 期望值：纸币数量最少 用贪心算法来解决。在贡献相同期望值的情况下，希望多贡献金额。
每次选择小于K元的面额的纸币中面额最大的 选择该面额若干张，保证面额总和小于K 对剩余的值继续上述两个操作 0.1.3.3. 区间覆盖 假设有 n 个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？
把这个问题抽象成：
一组数据：n个区间 限制值：区间不相交 期望值：区间数量最多 用贪心算法来解决。
假设这 n 个区间中最左端点是 lmin，最右端点是 rmax。这个问题就相当于选择几个不相交的区间，从左到右将[lmin, rmax]覆盖上 按照起始端点从小到大的顺序对这 n 个区间排序 每次选择左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间 0.1.4. 霍夫曼编码 霍夫曼编码，利用贪心算法来实现对数据压缩编码，有效节省数据存储空间。
假设有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），存储这 1000 个字符就一共需要 8000bits，那有没有更加节省空间的存储方式呢？
假设通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f 而 3 个二进制位（bit）就可以表示 8 个不同的字符，所以，为了尽量减少存储空间，每个字符用 3 个二进制位来表示 存储这 1000 个字符只需要 3000bits 就可以了，比原来的存储方式节省了很多空间 a(000)、b(001)、c(010)、d(011)、e(100)、f(101) 还有更加节省空间的存储方式，霍夫曼编码，一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。
霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。
霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率。
如何给不同频率的字符选择不同长度的编码呢？
把这个问题抽象成：
一组数据：给定的文本 限制值：单个字符的长度 期望值：存储空间最小 用贪心算法来解决。
把出现频率比较多的字符，用稍微短一些的编码 把出现频率比较少的字符，用稍微长一些的编码 对于等长的编码来说，解压缩起来很简单。比如上面例子中abcdef用 3 个 bit 表示一个字符。在解压缩的时候，每次从文本中读取 3 位二进制码，然后翻译成对应的字符。
霍夫曼编码是不等长的，每次应该读取读取的位数无法确定，这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。
假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f。 编码成如下表格，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。 经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。
字符 出现频率 编码 总二进制位数 a 450 1 450 b 350 01 700 c 90 001 270 d 60 0001 150 f 20 00000 100 霍夫曼编码中，如何根据字符出现频率的不同，给不同的字符进行不同长度的编码，这里的处理稍微有些技巧。
把每个字符看作一个节点，并且附带着把频率放到优先级队列中 从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C（频率小的放在左边） 把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点 再把 C 节点放入到优先级队列中 重复这个过程，直到队列中没有数据
给每一条边加上一个权值：
指向左子节点的边统统标记为 0 指向右子节点的边，统统标记为 1 从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。
实际上，贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法，这些算法都用到了贪心算法。
0.2. 分治算法 分治算法（divide and conquer）的核心思想其实就是四个字，分而治之，将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：
分解：将原问题分解成一系列子问题 解决：递归地求解各个子问题，若子问题足够小，则直接求解 合并：将子问题的结果合并成原问题 分治算法能解决的问题，一般需要满足下面这几个条件：
原问题与分解成的小问题具有相同的模式 原问题分解成的子问题可以独立求解，子问题之间没有相关性（这是分治与动态规划的明显区别） 具有分解终止条件，当问题足够小时，可以直接求解 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果 0.2.1. 分治算法应用 使用分治算法解决排序问题。在排序算法中，用有序度来表示一组数据的有序程度，用逆序度表示一组数据的无序程度。
假设有 n 个数据，期望数据从小到大排列，那完全有序的数据的有序度就是 n(n-1)/2，逆序度等于 0；相反，倒序排列的数据的有序度就是 0，逆序度是 n(n-1)/2。除了这两种极端情况外，通过计算有序对或者逆序对的个数，来表示数据的有序度或逆序度，如何编程求出一组数据的有序对个数或者逆序对个数。
解法一：将每个数字与后面的数字比较，看有几个比它小，记作k，依次类推，每个数都考察一遍，将k值球和，得到逆序对个数。时间复杂度
0.1. 单模式串匹配算法 0.1.1. BF算法 0.1.2. Rk算法 0.1.2.1. 时间复杂度 0.1.2.2. 散列冲突 0.1.3. BM算法 0.1.3.1. 坏字符规则 0.1.3.2. 好后缀规则 0.1.3.3. 实现过程优化 0.1.3.4. 性能分析 0.1.4. KMP算法 0.2. 多模式串匹配算法 0.2.1. Trie树 0.2.1.1. 实现Trie树 0.2.1.2. 时间复杂度 0.2.1.3. 空间复杂度 0.2.1.4. 空间优化 0.2.1.5. Trie 树与散列表、红黑树的比较 0.2.2. AC自动机 0.2.2.1. 场景：敏感词过滤 0.2.2.2. 构建AC自动机 0.2.2.3. 匹配AC自动机 0.2.2.4. 时间复杂度 如果要在字符串 A（长度n）中查找字符串 B（长度m），那么：
主串：A 模式串：B n>m 0.1. 单模式串匹配算法 0.1.1. BF算法 BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。
BF 算法的思想在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。极端情况下，算法的时间复杂度是O(n*m)
虽然理论上时间复杂度较高，但在实际开发中挺常用的：
大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，统计意义上，大部分情况下，算法执行效率要比O(n*m)高很多 思想简单、代码简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选（KISS原则） 所以，在实际的软件开发中，绝大部分情况下，朴素的字符串匹配算法就够用了，处理小规模的字符串很好用。
0.1.2. Rk算法 RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。RK 算法是 BF 算法的改进，它巧妙借助了哈希算法，让匹配的效率有了很大的提升。
模式串长度为 m 主串长度为 n 主串中有 n-m+1 个长度为 m 的子串 对比这 n-m+1 个子串与模式串，找出主串与模式串匹配的子串 每次检查主串与子串是否匹配，需要依次比对每个字符，时间复杂度高，引入哈希算法，时间复杂度立刻就会降低。
RK 算法的思路：
通过哈希算法对主串中的 n-m+1 个子串分别求哈希值 逐个与模式串的哈希值比较大小 如果某个子串的哈希值与模式串相等，那就匹配了（先不考虑散列冲突） 哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
但是，通过哈希算法计算子串的哈希值时，需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。
继续改进，优化哈希算法的设计。
假设要匹配的字符串的字符集中只包含 K 个字符，用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。
比如要处理的字符串只包含 a～z 这 26 个小写字母，就用二十六进制来表示一个字符串。把 a～z 这 26 个字符映射到 0～25 这 26 个数字。
在十进制的表示法中，一个数字的值是通过下面的方式计算出来的：
0.1. 图定义 0.2. 存储图 0.2.1. 邻接矩阵 0.2.2. 邻接表 0.3. 搜索算法 0.3.1. 广度优先搜索 0.3.2. 深度优先搜索 0.1. 图定义 树一种非线性表数据结构，树中的元素称为节点 图（Graph）另一种非线性表数据结构，图中的元素叫作顶点（vertex） 图比树更加复杂，图中的一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫作边（edge）。 以微博为例，把每个用户看作一个顶点。如果两个用户之间互相关注，那就在两者之间建立一条边。所以，整个微博的粉丝关系就可以用一张图来表示。其中，每个用户有多少个粉丝，对应到图中，就叫作顶点的度（degree），就是跟顶点相连接的边的条数。 如果用户 A 关注了用户 B，就在图中画一条从 A 到 B 的带箭头的边，来表示边的方向。 如果用户 A 和用户 B 互相关注，就画一条从 A 指向 B 的边，再画一条从 B 指向 A 的边。 这种边有方向的图叫作“有向图”。以此类推，边没有方向的图就叫作“无向图”。 无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，把度分为入度（In-degree）和出度（Out-degree）。 顶点的入度，表示有多少条边指向这个顶点；入度就表示有多少粉丝 顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点；出度就表示关注了多少人 再来看QQ，它的社交关系要更复杂一点。QQ 不仅记录了用户之间的好友关系，还记录了两个用户之间的亲密度，如果两个用户经常往来，那亲密度就比较高；如果不经常往来，亲密度就比较低。 这里就要用到带权图（weighted graph），每条边都有一个权重（weight），可以通过这个权重来表示 QQ 好友间的亲密度。 0.2. 存储图 0.2.1. 邻接矩阵 图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。 邻接矩阵的底层依赖一个二维数组。 对于无向图，如果顶点 i 与顶点 j 之间有边，就将 A[i][j]和 A[j][i]标记为 1 对于有向图：如果顶点 i 到顶点 j 之间： 有一条箭头从顶点 i 指向顶点 j 的边，就将 A[i][j]标记为 1 有一条箭头从顶点 j 指向顶点 i 的边，就将 A[j][i]标记为 1 对于带权图，数组中就存储相应的权重 用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。 对于无向图来说，如果 A[i][j]等于 1，那 A[j][i]也肯定等于 1。实际上，只需要存储一个就可以了，另外一半白白浪费掉了。 如果存储的是稀疏图（Sparse Matrix），顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。 邻接矩阵的优点： 存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效 方便计算，因为可以将很多图的运算转换成矩阵之间的运算。比如求解最短路径问题时会提到一个Floyd-Warshall 算法，就是利用矩阵循环相乘若干次得到结果 0.2.2. 邻接表 针对邻接矩阵比较浪费内存空间的问题，使用邻接表（Adjacency List）来存储图。乍一看，邻接表有点像散列表，每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。 有向图的邻接表存储方式，每个顶点对应的链表中，存储的是指向的顶点 无向图的邻接表存储方式，每个顶点对应的链表中，存储的是跟这个顶点有边相连的顶点 邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。 邻接表存储起来比较节省空间，但是使用起来就比较耗时间。 如果链过长，为了提高查找效率，可以将邻接表中的链表改成平衡二叉查找树。实际开发中，可以选择用红黑树。这样，可以更加快速地查找两个顶点之间是否存在边了。 二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。 还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。 使用邻接表存储出度，使用逆邻接表存储入度。 0.3. 搜索算法 算法是作用于具体数据结构之上的，深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。 图这种数据结构的表达能力很强，大部分涉及搜索的场景都可以抽象成“图”。 图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。具体方法有很多，比如两种最简单、最“暴力”的深度优先、广度优先搜索，还有 A*、IDA* 等启发式搜索算法。 图有两种主要存储方法，邻接表和邻接矩阵，下面用邻接表来存储图。 深度优先搜索算法和广度优先搜索算法，既可以用在无向图，也可以用在有向图上。 0.3.1. 广度优先搜索 广度优先搜索（Breadth-First-Search，BFS）。它是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。 尽管广度优先搜索的原理挺简单，但代码实现还是稍微有点复杂度。 代码里面有三个重要的辅助变量 visited、queue、prev。 visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q]会被设置为 true。 queue 是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。当访问到第 k 层的顶点的时候，需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，用这个队列来实现记录的功能。 prev 用来记录搜索路径。当从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w]存储的是，顶点 w 是从哪个前驱顶点遍历过来的。为了正向打印出路径，需要递归地来打印，使用print()函数的实现。 时间复杂度：最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。对于一个连通图（图中的所有顶点都是连通的）来说，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E) 空间复杂度：空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V) 0.3.2. 深度优先搜索 深度优先搜索（Depth-First-Search，DFS），最直观的例子就是“走迷宫”。 在图中应用深度优先搜索，来找某个顶点到另一个顶点的路径。搜索的起始顶点是 s，终止顶点是 t，希望在图中寻找一条从顶点 s 到顶点 t 的路径。 用深度递归算法，把整个搜索的路径标记出来了。这里面实线箭头表示遍历，虚线箭头表示回退。从图中可以看出，深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最短路径。 实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程，非常适合用递归来实现。 深度优先搜索代码实现也用到了 prev、visited 变量以及 print() 函数，它们跟广度优先搜索代码实现里的作用是一样的。 不过，深度优先搜索代码实现里，有个比较特殊的变量 found，它的作用是，当我们已经找到终止顶点 t 之后，就不再递归地继续查找了。 时间复杂度：从上图可以看出，每条边最多会被访问两次，一次是遍历，一次是回退。所以，深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数 空间复杂度：消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是O(V) 广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法，比起其他高级的搜索算法，比如 A、IDA 等，要简单粗暴，没有什么优化，所以，也被叫作暴力搜索算法。所以，这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。
0.1. 堆 0.1.1. 实现堆 0.1.1.1. 存储方式 0.1.1.2. 往堆中插入一个元素 0.1.1.3. 删除堆顶元素 0.2. 基于堆实现排序 0.2.1. 建堆 0.2.2. 排序 0.3. 应用 0.3.1. 优先级队列 0.3.1.1. 合并有序小文件 0.3.1.2. 高性能定时器 0.3.2. 求TopK 0.3.2.1. 静态数据 0.3.2.2. 动态数据 0.3.3. 求中位数 0.3.4. 求百分位数据 堆是一种特殊的数据结构，应用场景很多，堆排序是一种原地排序，时间复杂度O(nlogn)。
0.1. 堆 堆是一种特殊的树，满足以下两点就是一个堆：
堆是一个完全二叉树（除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列）
堆中每一个节点的值都必须大于等于（或小于等于）其左右子节点的值
对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆” 对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆” 0.1.1. 实现堆 0.1.1.1. 存储方式 堆是完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。
从图中可以看到，数组中下标为 i 的节点：
左子节点：是下标为 i∗2 的节点 右子节点：是下标为 i∗2+1 的节点 父节点：是下标为
递归代码的时间复杂度分析起来很麻烦。利用递推公式求解，但是，有些情况，用递推公式的话，会涉及非常复杂的数学推导。除了用递推公式这种比较复杂的分析方法，还可以借助递归树来分析递归算法的时间复杂度。
递归树与时间复杂度分析 递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。
如果把这个一层一层的分解过程画成图，其实就是一棵树（递归树）。
如下是一棵斐波那契数列的递归树，节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。
归并排序是一个自上而下的分治过程，每次会将数据规模一分为二。把归并排序画成递归树，如下所示：
每次分解都是一分为二，所以代价很低，把时间上的消耗记作常量1。 比较耗时的是归并操作，也就是把两个子数组合并为大数组。 从图中可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。把每一层归并操作消耗的时间记作n。
现在，只需要知道这棵树的高度h，用高度h乘以每一层的时间消耗n，就可以得到总的时间复杂度
0.1. 平衡二叉查找树定义 0.2. 红黑树 0.2.1. 近似平衡的红黑树 二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O(logn)。 二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log2n 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。 为了解决这个复杂度退化的问题，需要设计一种平衡二叉查找树。 0.1. 平衡二叉查找树定义 平衡二叉树的定义：二叉树中任意一个节点的左右子树的高度相差不能大于1。 从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。 平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。 最先被发明的平衡二叉查找树是AVL树，它严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。 但是很多平衡二叉查找树并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。 发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。所以，平衡二叉查找树中“平衡”的意思，是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 0.2. 红黑树 平衡二叉查找树其实有很多，比如： Splay Tree（伸展树） Treap（树堆）等， 但是提到平衡二叉查找树，基本都是红黑树，甚至默认平衡二叉查找树就是红黑树。 红黑树的英文是“Red-Black Tree”，简称 R-B Tree，它是一种不严格的平衡二叉查找树。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求： 根节点是黑色的 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据(简化代码而设置的要求) 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点 0.2.1. 近似平衡的红黑树 平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以： “平衡”的意思可以等价为性能不退化 “近似平衡”就等价为性能不会退化的太严重
0.1. 树的定义 0.2. 二叉树 0.2.1. 存储二叉树 0.2.1.1. 链式存储 0.2.1.2. 顺序存储 0.2.2. 遍历二叉树 0.2.3. 二叉查找树 0.2.3.1. 查找操作 0.2.3.2. 插入操作 0.2.3.3. 删除操作 0.2.3.4. 其他操作 0.2.3.5. 时间复杂度分析 0.2.4. 支持重复数据的二叉查找树 0.2.4.1. 插入操作 0.2.4.2. 查找操作 0.2.4.3. 删除操作 0.2.5. 二叉查找树与散列表的对比 0.2.5.1. 数据有序性 0.2.5.2. 稳定性 0.2.5.3. 执行效率 0.2.5.4. 复杂度 0.2.5.5. 存储空间利用率 树是一种非线性表结构比线性表的数据结构要复杂得多。 0.1. 树的定义 “树”中每个元素叫作“节点”；用来连线相邻节点之间的关系，叫作“父子关系”。 如下图所示： A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。 B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。 没有父节点的节点叫作根节点，如图中的节点 E。 没有子节点的节点叫作叶节点，如图中的 G、H、I、J、K、L 都是叶子节点。 树还有三个比较相似的概念： 高度（Height）：节点到叶子节点的最长路径（边数），从下往上看，起点为0 深度（Depth）：根节点到这个节点所经历的边的个数，从上往下看，起点为0 层（Level）：节点深度+1，从上往下看，起点为1 树的高度：根节点的高度+1 0.2. 二叉树 二叉树，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。 二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。 如上图所示： 编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。 编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。 0.2.1. 存储二叉树 要理解完全二叉树定义的由来，需要先了解，如何表示（或者存储）一棵二叉树。想要存储一棵二叉树，有两种方法： 一种是基于指针的二叉链式存储法 一种是基于数组的顺序存储法 0.2.1.1. 链式存储 从图可以看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。 只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种结构来实现的。 0.2.1.2. 顺序存储 基于数组的顺序存储法。 把根节点存储在下标 i=1 的位置 左子节点存储在下标 2*i=2 的位置 右子节点存储在下标 2*i+1=3 的位置 以此类推 所以，图中 D 节点的左子节点存储在 2*i=2*2=4 的位置，右子节点存储在 2*i+1=2*2+1=5 的位置。 如果节点 X 存储在数组中下标为 i 的位置： 下标为 2*i 的位置存储的就是左子节点 下标为 2*i+1 的位置存储的就是右子节点 下标为 i/2 的位置存储就是它的父节点 通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。 如果是一棵完全二叉树只会浪费下标为0的存储位置，如果是一棵非完全二叉树会浪费较多存储空间。 所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。 这也是为什么完全二叉树要求最后一层的子节点都靠左的原因。堆其实就是一种完全二叉树，最常用的存储方式就是数组。 0.2.2. 遍历二叉树 如何将所有节点都遍历打印出来，经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。 前序遍历：对于树中的任意节点，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。 中序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它本身，最后打印它的右子树。 后序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它的右子树，最后打印它本身。 实际上，二叉树的前、中、后序遍历就是一个递归的过程。 递归的关键是递推公式和终止条件，递推公式的关键是问题拆分，如果要解决问题 A，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。 # 前序遍历的递推公式： preOrder(r) = print r->preOrder(r->left)->preOrder(r->right) # 中序遍历的递推公式： inOrder(r) = inOrder(r->left)->print r->inOrder(r->right) # 后序遍历的递推公式： postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r # 伪代码 void preOrder(Node* root) { if (root == null) return; print root // 此处为伪代码，表示打印root节点 preOrder(root->left); preOrder(root->right); } void inOrder(Node* root) { if (root == null) return; inOrder(root->left); print root // 此处为伪代码，表示打印root节点 inOrder(root->right); } void postOrder(Node* root) { if (root == null) return; postOrder(root->left); postOrder(root->right); print root // 此处为伪代码，表示打印root节点 } 二叉树遍历的时间复杂度是O(n)。 0.2.3. 二叉查找树 二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。 散列表也是支持这些操作的，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 O(1)。 二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树，是为了实现快速查找而生的。它还支持快速插入、删除一个数据。这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。 0.2.3.1. 查找操作 先取根节点，如果它等于我们要查找的数据，那就返回 如果要查找的数据比根节点的值小，那就在左子树中递归查找 如果要查找的数据比根节点的值大，那就在右子树中递归查找 0.2.3.2. 插入操作 插入过程有点类似查找操作。 新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系 如果要插入的数据比节点的数据大 如果节点的右子树为空，就将新数据直接插到右子节点的位置 如果节点的右子树不为空，就再递归遍历右子树，查找插入位置 如果要插入的数据比节点数值小 如果节点的左子树为空，就将新数据插入到左子节点的位置 如果不为空，就再递归遍历左子树，查找插入位置 0.2.3.3. 删除操作 删除操作就比较复杂。针对要删除节点的子节点个数的不同，分三种情况来处理： 第一种情况是，如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。 实际上，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。而且，这种处理方法也并没有增加插入、查找操作代码实现的难度。 0.2.3.4. 其他操作 二叉查找树中快速地查找最大节点和最小节点、前驱节点和后继节点。 中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。 0.2.3.5. 时间复杂度分析 图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。 大部分情况下，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。将高度转为层数，第 K 层包含的节点个数就是 2^(K-1)。最后一层的节点个数在 1 个到 2^(L-1) 个之间（假设最大层数是 L）。 所以得到如下公式： n >= 1+2+4+8+...+2^(L-2)+1 n <= 1+2+4+8+...+2^(L-2)+2^(L-1) 借助等比数列的求和公式，可以计算出，L 的范围是[log2(n+1), log2n +1]。 需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，这就是平衡二叉查找树。平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。 0.2.4. 支持重复数据的二叉查找树 在实际的软件开发中，二叉查找树中存储的，是一个包含很多字段的对象。利用对象的某个字段作为键值（key）来构建二叉查找树，把对象中的其他字段叫作卫星数据。 0.2.4.1. 插入操作 如果存储的两个对象键值相同，有两种解决方法： 第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。 第二种方法比较不好理解，不过更加优雅。每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，就将这个要插入的数据放到这个节点的右子树，即把这个新插入的数据当作大于这个节点的值来处理。 0.2.4.2. 查找操作 当要查找数据的时候，遇到值相同的节点，并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。 0.2.4.3. 删除操作 对于删除操作，需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。 0.2.5. 二叉查找树与散列表的对比 散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效 二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn) 0.2.5.1. 数据有序性 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序 二叉查找树只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列 0.2.5.2. 稳定性 散列表扩容耗时很多，当遇到散列冲突时，性能不稳定 二叉查找树的性能不稳定，但在工程中最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn) 0.2.5.3. 执行效率 散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快 加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高 0.2.5.4. 复杂度 散列表的构造比二叉查找树要复杂，需要考虑的东西很多，比如： 散列函数的设计 冲突解决办法 扩容 缩容 平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。 0.2.5.5. 存储空间利用率 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。 平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。在实际的开发过程中，需要结合具体的需求来选择使用哪一个。
0.1. 哈希算法定义 0.1.1. MD5 0.2. 哈希算法的应用 0.2.1. 安全加密 0.2.2. 唯一标识 0.2.3. 数据校验 0.2.4. 散列函数 0.2.5. 负载均衡 0.2.6. 数据分片 0.2.6.1. 统计“搜索关键词”出现的次数 0.2.6.2. 快速判断图片是否在图库 0.2.7. 分布式存储 0.2.8. 解决用户密码存储问题 0.1. 哈希算法定义 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 一个优秀的哈希算法需要满足如下要求： 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法） 对输入数据非常敏感，哪怕原始数据只修改了1个Bit，最后得到的哈希值也大不相同 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值 0.1.1. MD5 MD5 的哈希值是 128 位的 Bit 长度 （16进制长度为32位)。 sugoi@sugoi:~$ echo "今天我来讲哈希算法" | md5sum eb4f874d1ef429470bb2808ae32323dc - sugoi@sugoi:~$ echo "今天我来讲哈希算法!" | md5sum a2cbc0646f7ce8ba5bb9d74821d4a6c9 - sugoi@sugoi:~$ echo "jiajia" | md5sum 4ced003def1157c81e8a1a2832c2f9f7 - 输出的结果长度固定 输入数据有细微差别，输出结果也差别很大 0.2. 哈希算法的应用 安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储，后三个应用与分布式系统有关。 0.2.1. 安全加密 最常用于加密的哈希算法是 ： MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法） SHA（Secure Hash Algorithm，安全散列算法） 其他加密算法 DES（Data Encryption Standard，数据加密标准） AES（Advanced Encryption Standard，高级加密标准） 当哈希算法用于加密时，很难根据哈希值反向推导出原始数据和散列冲突的概率要很小这两点就显得尤为重要。 加密的目的就是防止原始数据泄露，所以很难通过哈希值反向推导原始数据，这是一个最基本的要求。 不管是什么哈希算法，只能尽量减少碰撞冲突的概率，理论上是没办法做到完全不冲突的。为什么哈希算法无法做到零冲突？ 抽屉原理：如果有 10 个鸽巢，有 11 只鸽子，那肯定有 1 个鸽巢中的鸽子数量多于 1 个，换句话说就是，肯定有 2 只鸽子在 1 个鸽巢内。 哈希算法产生的哈希值的长度是固定且有限的。如 MD5 的哈希值是固定的 128 位二进制串，能表示的数据是有限的，最多能表示 2^128=340282366920938463463374607431768211456 个数据，而需要哈希的数据是无穷的。 基于抽屉原理，如果对 2^128+1 个数据求哈希值，就必然会存在哈希值相同的情况。所以，一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。 虽然哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像 MD5，有2^128个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于1/2^128。 如果拿到一个 MD5 哈希值，希望通过毫无规律的穷举的方法，找到跟这个 MD5 值相同的另一个数据，那耗费的时间应该是个天文数字。所以，即便哈希算法存在冲突，但是在有限的时间和资源下，哈希算法还是被很难破解的。 没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。比如 SHA-256 比 SHA-1 要更复杂、更安全，相应的计算时间就会比较长。在实际的开发过程中，需要权衡破解难度和计算时间，来决定使用哪种加密算法。 0.2.2. 唯一标识 如果要在海量的图库中，搜索一张图是否存在，不能单纯地用图片的元信息（比如图片名称）来比对，因为可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。 任何文件在计算中都可以表示成二进制码串，所以，可以拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。但是，每个图片小则几十KB、大则几MB，转化成二进制是一个非常长的串，比对起来非常耗时。 可以给每一个图片取一个唯一标识（或信息摘要）。比如： 从图片的二进制码串开头取 100 个字节 从中间取 100 个字节 从最后再取 100 个字节 然后将这 300 个字节放到一块 通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识 通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。 继续提高效率： 把每个图片的唯一标识和相应的图片文件在图库中的路径信息，都存储在散列表中 查看某个图片是不是在图库中的时候，先通过哈希算法对这个图片取唯一标识 然后在散列表中查找是否存在这个唯一标识 如果不存在，那就说明这个图片不在图库中 如果存在，再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样 如果一样，就说明已经存在 如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片 0.2.3. 数据校验 BT 下载的原理是基于 P2P 协议的。 从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分割成很多文件块（比如可以分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件。 网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的，又或者下载过程中出现了错误，导致下载的文件块可能不是完整的。如果没有能力检测这种恶意修改或者文件下载出错，就会导致最终合并后的电影无法观看，甚至导致电脑中毒。 BT 协议很复杂，校验方法也有很多，可以通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。 哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。 0.2.4. 散列函数 散列函数也是哈希算法的一种应用。 散列函数是设计一个散列表的关键。 它直接决定了散列冲突的概率和散列表的性能。 相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，都可以通过开放寻址法或者链表法解决。 散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。 散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。 0.2.5. 负载均衡 负载均衡算法有很多，比如轮询、随机、加权轮询等。 实现一个会话粘滞（session sticky）的负载均衡算法，也就是说，同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。 最直接的方法就是，维护一张映射关系表，这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找应该路由到的服务器编号，然后再请求编号对应的服务器。 这种方法简单直观，但也有几个弊端： 如果客户端很多，映射表可能会很大，比较浪费内存空间； 客户端下线、上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就会很大； 如果借助哈希算法，可以非常完美地解决。通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，就可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。 0.2.6. 数据分片 哈希算法用于数据的分片。 0.2.6.1. 统计“搜索关键词”出现的次数 在1T的日志文件中，记录用户搜索关键词，如何快速统计每个关键词被搜索的次数？ 难点： 日志量大，无法放在一台服务器的内存中 只用一台服务器处理，耗时太长 解决方案： 对数据进行分片 多台服务器处理，提高处理速度 具体思路： 为了提高处理的速度，用 n 台机器并行处理 从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号 同一个搜索关键词会被分配到同一个机器上，每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果 实际上，这里的处理过程也是 MapReduce 的基本设计思想。 0.2.6.2. 快速判断图片是否在图库 在唯一标识的应用中，给每个图片取唯一标识（或者信息摘要），然后构建散列表，来判断图片是否存在。 当图片数量巨大如上亿张图片时，在单台服务器上构建散列表是行不通的。因为单台机器的内存有限，而上亿张图片构建散列表显然远远超过了单台机器的内存上限。 同样对数据进行分片，然后采用多机处理。 准备 n 台服务器，让每台机器只维护某一部分图片对应的散列表 每次从图库中读取一个图片，计算唯一标识，然后与机器个数 n 求余取模，得到的值就对应要分配的机器编号 将这个图片的唯一标识和图片路径发往对应的机器构建散列表 当判断一个图片是否在图库中时，通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数 n 求余取模。假设得到的值是 k，那就去编号 k 的机器构建的散列表中查找。 假设图片数量是1亿张，散列表中每个数据单元包含哈希值和图片文件的路径。使用MD5算法生成的哈希值是128位（16字节），文件路径长度的上限是256字节（假设平均长度128字节）。使用链表法来解决冲突，每个指针占用8个字节，所以散列表一个数据单元大概152字节。 假设一台机器内存2GB，散列表装填因子0.75，那么一台机器可以给大约1000万（2GB×0.75./152B）图片构建索引。所以大概需要十几台机器。 借助数据分片的思路，可以突破单机内存、CPU等资源资源限制。 0.2.7. 分布式存储 面对海量数据和用户，为了提高数据的读写能力，一般都采用分布式的方式来存储数据，比如分布式缓存。对于海量数据的缓存，需要将缓存分布在多台机器上。 同样借助数据分片的思想，通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。 但是随着数据的增多就需要扩容，这里的扩容并不是简单的增加机器，就像散列表的扩容一样，会涉及到数据缓存位置的重新计算，然后数据迁移到新的机器上。这样就相当于，缓存数据一下子全部失效了。所有的数据请求都会穿透缓存，直接去请求数据库，发生雪崩效应，压垮数据库。 需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移，这就是一致性哈希算法。 假设有 k 个机器，数据的哈希值的范围是[0, MAX]。将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。 除了分布式缓存，实际上，一致性哈希算法的应用非常广泛，在很多分布式存储系统中，都可以见到一致性哈希算法的影子。 0.2.8. 解决用户密码存储问题 通过哈希算法，对用户密码进行加密之后再存储，选择相对安全的加密算法，比如 SHA 等（因为 MD5 已经号称被破解了）。 字典攻击：维护一个常用密码的字典表，把字典中的每个密码用哈希算法计算哈希值，然后拿哈希值跟脱库后的密文比对。如果相同，基本上就可以认为，这个加密之后的密码对应的明文就是字典中的这个密码。 针对字典攻击，可以引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度，将组合之后的字符串做哈希算法加密，将它存储到数据库中，进一步增加破解的难度。 安全和攻击是一种博弈关系，不存在绝对的安全。所有的安全措施，只是增加攻击的成本而已。
0.1. 应用 0.2. 散列函数 0.3. 散列冲突 0.3.1. 开放寻址法 0.3.1.1. 线性探测 0.3.1.2. 二次探测 0.3.1.3. 双重散列 0.3.2. 链表法 0.4. 设计散列表 0.4.1. 常用散列函数设计方法 0.4.2. 避免装载因子过大 0.4.3. 避免低效扩容 0.4.3.1. 对于插入操作 0.4.3.2. 对于查询操作 0.4.4. 散列冲突解决办法 0.4.4.1. 开放寻址法 0.4.4.2. 链表法 0.5. 工业级散列表 0.5.1. LRU缓存淘汰算法 0.5.2. Redis有序集合 0.5.3. Java LInkedHashMap 散列表用的是数组支持按照下标随机访问数据的特性，时间复杂度是O(1)，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。 按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。 散列表两个核心问题是散列函数设计和散列冲突解决。散列函数设计的好坏决定了散列冲突的概率，也就决定散列表的性能。
0.1. 应用 Microsoft Word中拼写检查功能的实现。
常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。
对于现在的计算机来说，这个大小完全可以放在内存里面，所以可以用散列表来存储整个英文单词词典。
当用户输入某个英文单词时，拿用户输入的单词去散列表中查找 如果查到，则说明拼写正确 如果没有查到，则说明拼写可能有误，给予提示 借助散列表这种数据结构，可以轻松实现快速判断是否存在拼写错误。
0.2. 散列函数 散列函数在散列表中起着非常关键的作用，它是一个函数，把它定义成 hash(key)，其中 ：
key 表示元素的键值 hash(key) 的值表示经过散列函数计算得到的散列值 散列函数设计的三点基本要求：
散列函数计算得到的散列值是一个非负整数：因为数组下标从0开始 如果 key1 = key2，那 hash(key1) == hash(key2) 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2) 对于第三点看起来合情合理，但是在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。
即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。
MD5（MD5 Message-Digest Algorithm）：密码散列函数，可以产生出一个128位的散列值，用于确保信息传输完整一致，曾被用于文件校验，但存在明显缺陷。 SHA（Secure Hash Algorithm）：密码散列函数家族，能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。 CRC（Cyclic redundancy check）：根据网络数据包或电脑文件等数据产生简短固定位数校验码的散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。 所以几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，所以针对散列冲突问题，需要通过其他途径来解决。
0.3. 散列冲突 再好的散列函数也无法避免散列冲突，常用的散列冲突解决方法有两类：
开放寻址法（open addressing） 链表法（chaining） 0.3.1. 开放寻址法 开放寻址法的核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。
0.3.1.1. 线性探测 如何重新探测新的位置，比较简单的探测方法，线性探测（Linear Probing）。
当往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
在散列表中查找元素的过程有点儿类似插入过程。
通过散列函数求出要查找元素的键值对应的散列值 然后比较数组中下标为散列值的元素和要查找的元素 如果相等，则说明就是要找的元素 否则就顺序往后依次查找 如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中 散列表跟数组一样，不仅支持插入、查找操作，还支持删除操作。
对于使用线性探测法解决冲突的散列表，删除操作稍微有些特别。不能单纯地把要删除的元素设置为空。
因为在查找的时候，一旦通过线性探测方法，找到一个空闲位置，就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。
因此将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
线性探测法存在很大问题，当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。
极端情况下，可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。
0.3.1.2. 二次探测 为了解决开放寻址冲突的问题，所谓二次探测，跟线性探测很像：
线性探测：每次探测的步长是 1，探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2…… 二次探测：探测的步长就变成了原来的“二次方”，探测的下标序列就是 hash(key)+0，hash(key)+1^2，hash(key)+2^2…… 0.3.1.3. 双重散列 为了解决开放寻址冲突的问题，所谓双重散列，就是不仅要使用一个散列函数。
使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……
先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，会尽可能保证散列表中有一定比例的空闲槽位，用装载因子（load factor）来表示空位的多少。
装载因子的计算公式是：散列表的装载因子=填入表中的元素个数/散列表的长度，装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
0.3.2. 链表法 链表法是一种更常用的散列冲突解决办法，相比开放寻址法，它要简单很多。
如下图所示，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中。
插入时，只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。 查找/删除时，通过散列函数计算出对应的槽，然后遍历链表查找或者删除。 查找或删除这两个操作的时间复杂度跟链表的长度 k 成正比即O(k)。对于散列比较均匀的散列函数来说，理论上讲，
0.1. 跳表定义 0.1.1. 时间复杂度 0.1.2. 空间复杂度 0.1.3. 高效的动态插入和删除 0.1.3.1. 插入 0.1.3.2. 删除 0.1.4. 索引动态更新 因为二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。
如果数据存储在链表中，如何使用二分查找算法呢？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表（Skip list）。
跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。
Redis 中的有序集合（Sorted Set）就是用跳表来实现的。红黑树同样也可以实现快速的插入、删除和查找操作。那 Redis 为什么会选择用跳表来实现有序集合呢？
Redis 中的有序集合支持的核心操作主要有下面这几个：
插入一个数据； 删除一个数据； 查找一个数据； 按照区间查找数据（比如查找值在[100, 356]之间的数据）； 迭代输出有序序列。 其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到
0.1. 定义 0.2. 时间复杂度 0.3. 最简单情况的代码实现 0.4. 应用场景的局限性 0.5. 常见变形问题的代码实现 0.5.1. 查找第一个值等于给定值的元素 0.5.2. 查找最后一个值等于给定值的元素 0.5.3. 查找第一个大于等于给定值的元素 0.5.4. 查找最后一个小于等于给定值的元素 0.1. 定义 针对有序数据集合的查找算法：二分查找（Binary Search）算法，也叫折半查找算法。
假设有10个数据：8，11，19，23，27，33，45，55，67，98，快速找到19这个值是否在数据中。
利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围。过程如下图所示，其中，low 和 high 表示待查找区间的下标，mid 表示待查找区间的中间元素下标。
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。 每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 0.2. 时间复杂度 假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。
这是一个等比数列。 其中
0.1. 分析排序算法 0.1.1. 执行效率 0.1.2. 内存消耗 0.1.3. 稳定性 0.2. 常见排序算法 0.2.1. 冒泡排序 0.2.1.1. 有序度 0.2.2. 插入排序 0.2.3. 选择排序 0.2.4. 插入比冒泡更受欢迎 0.2.5. 三者对比 0.2.6. 归并排序 0.2.6.1. 性能分析 0.2.7. 快速排序 0.2.7.1. 性能分析 0.2.8. 归并与快排对比 0.3. 线性排序算法 0.3.1. 桶排序 0.3.2. 计数排序 0.3.2.1. 例子 0.3.3. 基数排序 0.4. 排序优化 0.4.1. 选择合适的排序算法 0.4.2. 优化快速排序 0.4.3. 实例 0.1. 分析排序算法 0.1.1. 执行效率 对于排序算法执行效率的分析，一般会从这几个方面来衡量：
最好情况、最坏情况、平均情况时间复杂度（最好、最坏情况对应的待排序原始数据是什么样的？）：有序度不同的数据，对排序的执行时间有影响 时间复杂度的系数、常数 、低阶：实际开发中，待排序的数据规模是 10/100/1000 这样的小规模，所以，在对同一阶时间复杂度的排序算法性能对比时，要把系数、常数、低阶也考虑进来 比较次数和交换（或移动）次数：基于比较的排序算法的执行过程，会涉及元素比较和元素交换/移动的操作。所以，在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去 0.1.2. 内存消耗 算法的内存消耗通过空间复杂度来衡量，针对排序算法的空间复杂度，要引入了一个新的概念，原地排序（Sorted in place），原地排序算法，就是特指空间复杂度是
0.1. 递归定义 0.1.1. 递归需要满足的三个条件 0.2. 编写递归代码 0.3. 递归遇到的问题 0.3.1. 警惕堆栈溢出 0.3.2. 警惕重复计算 递归代码调试 0.4. 递归改写为非递归 0.1. 递归定义 递归是一种应用非常广泛的算法（或者编程技巧）。很多数据结构和算法的编码实现都要用到递归，比如： DFS深度优先搜索 前中后序二叉树遍历 标准的递归求解问题的分解过程： 去的过程叫“递”， 回来的过程叫“归”。 基本上，所有的递归问题都可以用递推公式来表示，如f(n)=f(n-1)+1，其中f(1)=1转换为代码： func f(n int) int { if n == 1 { return 1 } return f(n-1) + 1 } 0.1.1. 递归需要满足的三个条件 只要同时满足以下三个条件，就可以用递归来解决。 一个问题的解可以分解为几个子问题（数据规模更小的问题）的解 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 存在递归终止条件：把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环 0.2. 编写递归代码 写递归代码最关键的是写出递推公式，找到终止条件，剩下将递推公式转化为代码就很简单了。 假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？ 实际上，可以根据第一步的走法把所有走法分为两类： 第一类是第一步走了 1 个台阶 另一类是第一步走了 2 个台阶 所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法，加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：f(n) = f(n-1)+f(n-2)。 有了递推公式，递归代码基本上就完成了一半。 再来看下终止条件，当有一个台阶时，不需要再继续递归，就只有一种走法，所以 f(1)=1。 可以用 n=2，n=3 这样比较小的数试验一下，上述递归终止条件是否满足。 n=2 时，f(2)=f(1)+f(0)。如果递归终止条件只有一个 f(1)=1，那 f(2) 就无法求解了 所以，还要有 f(0)=1，表示走 0 个台阶有一种走法，不过这样子看起来就不符合正常的逻辑思维了 所以，可以把 f(2)=2，作为一种终止条件，表示走 2 个台阶，有两种走法，一步走完或者分两步来走 n=3 时，f(3)=f(2)+f(1)，求解为3，终止条件正确。 综上，递推公式和终止条件并转化为代码： /* 递推公式:f(n)=f(n-1)+f(n-2) 终止条件:f(1)=1,f(2)=2 */ func f(n int) int { if n == 1 { return 1 } if n == 2 { return 2 } return f(n-1) + f(n-2) } 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 当递归调用只有一个分支，即“一个问题只需要分解为一个子问题”时，很容易能够想清楚“递“和”归”的每一个步骤，所以写起来、理解起来都不难。但是，当一个问题要分解为多个子问题的情况，递归代码就没那么好理解了，人脑几乎没办法把整个“递”和“归”的过程一步一步都想清楚。 计算机擅长做重复的事情，所以递归正和它的胃口，而人脑更喜欢平铺直叙的思维方式。当我们看到递归时，总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。 正确的思维方式应该是：如果一个问题 A 可以分解为若干子问题 B、C、D，可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。 因此，编写递归代码的关键是，只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。 写出递推公式 找到终止条件 翻译成递归代码 0.3. 递归遇到的问题 0.3.1. 警惕堆栈溢出 在实际的软件开发中，编写递归代码时，会遇到很多问题，比如堆栈溢出。而堆栈溢出会造成系统性崩溃，后果会非常严重。 回顾上一节内容“栈”，函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。 以Java为例，将JVM的堆栈大小设置为1KB，在求解较大数据规模时会出现如下堆栈报错Exception in thread "main" java.lang.StackOverflowError。 可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，就不继续往下再递归了，直接返回报错。 但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。 0.3.2. 警惕重复计算 使用递归时还会出现重复计算的问题，例如上面求解楼梯走法的问题： 从图中，可以直观地看到： 计算 f(5)，需要先计算 f(4) 和 f(3) 计算 f(4) 还需要计算 f(3) f(3) 就被计算了很多次 这就是重复计算问题。 为了避免重复计算，可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算。 将上面求解楼梯走法的代码优化： var process = make(map[int]int) func f(n int) int { if n == 1 { return 1 } if n == 2 { return 2 } if process[n-1] != 0 { return process[n-1] + f(n-2) } process[n-1] = f(n - 1) return f(n-1) + f(n-2) } // 求解30层楼梯，从4ms下降到56us，已经不是一个数量级了 在时间复杂度上，递归多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本 在空间复杂度上，递归调用一次就会在内存栈中保存一次现场数据，所以需要额外考虑这部分的开销 递归代码调试 平时调试代码使用 IDE 的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。 常用的做法： 打印日志发现，递归值 结合条件断点，golang中Delve调试器使用delve debug进入 break设置断点 condition设置条件 0.4. 递归改写为非递归 递归操作有点像遍历单链表，需要有指针记录前一个节点，递归代码的非递归实现，也需要有变量记录上一个步骤的结果。 递归有利有弊： 利：是递归代码的表达力很强，写起来非常简洁 弊：是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题 所以，在开发过程中，要根据实际情况来选择是否需要用递归的方式来实现。 func f(n int) int { if n == 1 { return 1 } if n == 2 { return 2 } pre := 2 prepre := 1 ret := 0 for i := 3; i <= n; i++ { ret = pre + prepre prepre = pre pre = ret } return ret } // 求解30层楼梯，在490ns 笼统地讲，所有的递归代码都可以改为这种迭代循环的非递归写法。因为递归本身就是借助栈（系统或者虚拟机本身提供的）来实现的。 如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也并没有解决如递归堆栈溢出或重复计算的问题，徒增了实现的复杂度。
0.1. 顺序队列和链式队列 0.2. 循环队列 0.3. 阻塞队列和并发队列 0.4. 应用 先进者先出，这就是典型的“队列”，最基本的操作也是两个： 入队 enqueue()，放一个数据到队列尾部 出队 dequeue()，从队列头部取一个元素 队列跟栈一样，也是一种操作受限的线性表数据结构。 0.1. 顺序队列和链式队列 队列可以用数组来实现，也可以用链表来实现。 用数组实现的队列叫作顺序队列 用链表实现的队列叫作链式队列 相比于栈只需要一个栈顶指针，队列需要两个指针: head指针：指向队头 tail指针：指向队尾 随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。因此需要进行数据搬移，每次进行出队操作都相当于删除数组下标为 0 的数据，要搬移整个队列中的数据，这样出队操作的时间复杂度就会从原来的 O(1) 变为 O(n)。 实际上，在出队时可以不用搬移数据。如果没有空闲空间了，只需要在入队时，再集中触发一次数据的搬移操作。 当队列的 tail 指针移动到数组的最右边后，如果有新的数据入队，可以将 head 到 tail 之间的数据，整体搬移到数组中 0 到 tail-head 的位置。 这种实现思路中，出队操作的时间复杂度仍然是 O(1)，但入队操作的时间复杂度还是 O(1)。 基于链表的实现，同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。 如图所示： 入队时，tail->next= new_node, tail = tail->next 出队时，head = head->next 0.2. 循环队列 使用数组实现队列时，当tail==n，会有数据搬移操作，这样入队操作的性能会受到影响。可以使用循环队列解决这个问题。 原本数组是有头有尾的，是一条直线。现在把首尾相连，扳成了一个环。如下图所示： 图中队列的大小为 8，当前 head=4，tail=7。 当有一个新的元素 a 入队时，放入下标为 7 的位置。此时，不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。 当再有一个元素 b 入队时，将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。 在 a，b 依次入队之后，循环队列中的元素就变成如下图所示： 这样可以避免数据搬移操作。循环队列实现的关键是，确定好队空和队满的判定条件。 数组实现的非循环队列中， 队满的判断条件是 tail == n 队空的判断条件是 head == tail 数组实现的循环队列中， 队满的判断条件是 （tail + 1）%n == head 队空的判断条件是 head == tail 当队满即(tail+1)%n=head时，tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。 0.3. 阻塞队列和并发队列 一些具有特殊特性的队列在实际开发中应用广泛，如阻塞队列和并发队列。 阻塞队列：在队列基础上增加了阻塞操作， 在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回 可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”，这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。 基于阻塞队列，还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。如配置多个“消费者”，来应对一个“生产者”。 在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，线程安全的队列叫作并发队列。 最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。 基于数组的循环队列，利用 CAS（compare and swap，比较并交换） 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。 比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。 该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。 0.4. 应用 CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。 当线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？一般有两种处理策略。 第一种是非阻塞的处理方式，直接拒绝任务请求； 另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。 如何存储排队的请求呢？我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。 队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢？ 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。 基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。设置一个合理的队列大小，也是非常有讲究的： 队列太大导致等待的请求太多 队列太小会导致无法充分利用系统资源、发挥最大性能 队列应用在线程池请求排队的场景，队列也可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。 实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
0.1. 实现栈 0.2. 动态扩容 0.3. 栈的应用 0.3.1. 栈在函数中的应用 0.3.2. 栈在表达式求值中的应用 0.3.3. 栈在括号匹配中的应用 0.3.4. 栈在浏览器中的应用 后进者先出，先进者后出，这就是典型的“栈”结构。 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据 从功能上来说，数组或链表确实可以替代栈，但特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选“栈”这种数据结构。 0.1. 实现栈 栈主要包含两个操作: 入栈：在栈顶插入一个数据 出栈：从栈顶删除一个数据 栈既可以用数组来实现，也可以用链表来实现。 用数组实现的栈，我们叫作顺序栈 用链表实现的栈，我们叫作链式栈 不管是顺序栈还是链式栈，存储数据只需要一个大小为 n 的数组就够了。 入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。 入栈和出栈过程中，只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。 注意，存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。 0.2. 动态扩容 顺序栈在初始化时需要事先指定栈的大小 链式栈大小虽然不受限制，但是存储next指针，内存消耗相对较多 数组动态扩容：当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。 如果要实现一个支持动态扩容的栈，只需要底层依赖一个支持动态扩容的数组就可以了。实际上，支持动态扩容的顺序栈，平时开发中并不常用到。此时出栈的时间复杂度是O（1），入栈的时间复杂度分为有空间O(1)和需要扩容O(n)，入栈的均摊时间复杂度为O(1)。 0.3. 栈的应用 0.3.1. 栈在函数中的应用 栈比较经典的一个应用场景就是函数调用栈。 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。 func main() { a, ret, res := 1, 0, 0 ret = add(3, 5) res = a + ret fmt.Printf("%d", res) } func add(x, y int) int { sum := 0 sum = x + y return sum } 上面代码mian()函数调用add()函数，获取计算结果，并且与临时变量a相加，最后打印res的值。在执行add()函数时，函数调用栈的情况如下图： 0.3.2. 栈在表达式求值中的应用 编译器通过两个栈实现表达式求值，其中一个栈保存操作数，另一个栈保存运算符。 从左向右遍历表达式 当遇到数字，直接压入操作数栈 当遇到运算符，就与运算符栈的栈顶元素比较 如果比栈顶元素优先级高，就将当前运算符压入栈 如果比栈顶元素优先级低或相同，从运算符栈中取栈顶元素，从操作数栈中取两个操作数，进行计算 把计算结果压入栈操作数栈 继续 如下示例为计算3+5*8-6： 0.3.3. 栈在括号匹配中的应用 假设表达式中只包含三种括号： 圆括号() 方括号[] 花括号{} 它们可以任意嵌套。 比如： 合法格式：{[] ()[{}]}或[{()}([])]等 不合法格式：{[}()]或[({)]等 用栈来判断一个包含三种括号的表达式字符串是否合法。 用栈来保存未匹配的左括号，从左到右依次扫描字符串。 当扫描到左括号时，则将其压入栈中； 当扫描到右括号时，从栈顶取出一个左括号。 如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。 如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。 当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。 0.3.4. 栈在浏览器中的应用 使用两个栈实现浏览器中前进后退的功能，假设两个栈分别为X和Y。 把首次浏览的页面压入栈X 当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次压入栈Y中 当点击前进按钮时，再依次从栈Y中出栈，并将出栈的数据依次压入栈X中 当X中没有数据，说明没有可以继续后退浏览的页面 当Y中没有数据，说明没有可以继续前进浏览的页面
0.1. 应用场景 0.1.1. 基于链表实现LRU淘汰算法 0.2. 链表结构 0.2.1. 单链表 0.2.2. 循环链表 0.2.3. 双向链表 0.2.4. 删除操作 0.2.4.1. 删除某个值对应的节点 0.2.4.2. 删除某个指针对应的节点 0.3. 链表与数组性能比较 0.1. 应用场景 一个经典的链表应用场景，那就是 LRU（Least Recently Used，最近最少使用） 缓存淘汰算法。 缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见: CPU缓存 数据库缓存 浏览器缓存等 缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留，由缓存淘汰策略来决定。常见的策略有三种： 先进先出策略 FIFO（First In，First Out） 最少使用策略 LFU（Least Frequently Used） 最近最少使用策略 LRU（Least Recently Used） 缓存就是利用了空间换时间的设计思想。 如果把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。 对于执行较慢的程序，通过消耗更多的内存（空间换时间）来进行优化 对于消耗过多内存的程序，通过消耗更多的时间（时间换空间）来降低内存的消耗 0.1.1. 基于链表实现LRU淘汰算法 维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。 如果此数据之前已经被缓存在链表中了，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。 如果此数据没有在缓存链表中，又可以分为两种情况： 如果此时缓存未满，则将此结点直接插入到链表的头部； 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。 无论缓存是否满了，都需要遍历一遍链表，所以基于链表的实现思路，缓存访问的时间复杂度为 O(n)。 继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。 0.2. 链表结构 对比链表与数组的底层存储结构： 数组需要一块连续的内存空间来存储，对内存的要求比较高。如果申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。 链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。如果申请 100MB 大小的链表，根本不会有问题。 链表结构五花八门，最常见的三种链表结构：单链表、双向链表和循环链表。 0.2.1. 单链表 链表通过指针将一组零散的内存块串联在一起，其中的内存块称为链表的“结点”。 为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针next。 图中有两个结点是比较特殊的，它们分别是第一个结点（头结点）和最后一个结点（尾结点）。 头结点用来记录链表的基地址。有了它，就可以遍历得到整条链表。 尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。 与数组一样，链表也支持数据的查找、插入和删除操作。 在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据，并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的,只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。 链表要想随机访问第 k个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。所以，链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。 0.2.2. 循环链表 循环链表是一种特殊的单链表。与单链表唯一的区别就在尾结点。 单链表的尾结点指针指向空地址，表示这就是最后的结点了。 循环链表的尾结点指针是指向链表的头结点。它像一个环一样首尾相连，所以叫作“循环”链表。 和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表（如约瑟夫问题）。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。 0.2.3. 双向链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。 双向链表，支持两个方向，每个结点有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。 从图中看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。 如果存储同样多的数据，双向链表要比单链表占用更多的内存空间 两个指针比较浪费存储空间，但支持双向遍历操作更灵活 从结构上来看，双向链表可以支持 O(1) 时间复杂度找到前驱结点，这使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。 0.2.4. 删除操作 在实际开发中，从链表中删除一个数据无外乎这两种情况： 删除结点中“值等于某个给定值”的结点 删除给定指针指向的结点 0.2.4.1. 删除某个值对应的节点 不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过指针操作将其删除。 删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。 0.2.4.2. 删除某个指针对应的节点 已知要删除的结点的指针，但是删除某个结点 q 需要知道其前驱结点： 单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点，所以删除操作需要 O(n) 的时间复杂度 双向链表中的结点已经保存了前驱结点的指针，不需要再遍历，所以删除操作只需要 O(1) 的时间复杂度 同理在某个节点前插入节点也分两种情况，单链表时间复杂度O(n)，双链表时间复杂度O(1)。 对于有序链表，双向链表的按值查询的效率也要比单链表高。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。 这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。这也是用空间换时间的设计思想。 如果内存空间充足，更加追求代码的执行速度，可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。 如果内存比较紧缺，比如代码跑在手机或者单片机上，就要反过来用时间换空间的设计思路。 0.3. 链表与数组性能比较 数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。 操作 数组 链表 插入删除 O(n) O(1) 随机访问 O(1) O(n) 数组和链表的对比，并不能局限于时间复杂度。在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。 链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。 链表本身没有大小的限制，天然地支持动态扩容，这也是它与数组最大的区别。 除此之外，如果代码对内存的使用非常苛刻，那数组就更适合你。 因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。 而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。 所以，在实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。
0.1. 如何实现随机访问 0.2. 低效的插入和删除 0.2.1. 插入操作 0.2.2. 删除操作 0.2.3. 警惕数组的访问越界问题 0.3. 容器能否完全替代数组 数组不仅是一种编程语言中的数据类型，还是一种最基础的数据结构。 在大部分编程语言中，数组都是从 0 开始编号的，但你是否下意识地想过，为什么数组要从 0 开始编号，而不是从 1 开始呢？ 从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移(offset)”。如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k * type_size。 但是，如果数组从 1 开始计数，那计算数组元素 a[k]的内存地址就会变为：a[k]_address = base_address + (k-1)*type_size。 对比两个公式，不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。 数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。 可能还有历史原因，从C语言使用0作为下标开始，其他语言借鉴了这个设计，如Python还是负数下标。 0.1. 如何实现随机访问 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 线性表（Linear List），就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。链表、队列、栈等也是线性表结构。 非线性表，比如二叉树、堆、图等。在非线性表中，数据之间并不是简单的前后关系。 连续的内存空间和相同类型的数据。正是因为这两个限制，有利也有弊： 优势：随机访问 劣势：很多操作变得非常低效，如，删除、插入一个数据（为了保证连续性，就需要做大量的数据搬移工作） 创建一个长度为10的整型数组a := [10]int{}，数组内默认十个0。如下图所示，计算机给数组a，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。 计算机会给每个内存单元分配一个地址，通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址： a[i]_address = base_address + i * data_type_size data_type_size：表示数组中每个元素的大小（上面的例子中，存储的是int，所以是4个字节） 数组支持随机访问，根据下标随机访问的时间复杂度是O(1)。 0.2. 低效的插入和删除 数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。 0.2.1. 插入操作 假设数组的长度为 n，如果要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位，所以，插入操作的时间复杂度是： 最好：O(1) 最坏：O(n) 平均：O(n) 均摊：O(n) 如果数组中的数据是有序的，在某个位置插入一个新的元素时，就必须按照上面的方法搬移 k 之后的数据。 如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。 0.2.2. 删除操作 跟插入数据类似，如果要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了，所以删除操作的时间复杂度是： 最好：O(1) 最坏：O(n) 平均：O(n) 均摊：O(n) 实际上，在某些特殊场景下，并不一定非得追求数组中数据的连续性。如果将多次删除操作集中在一起执行，删除的效率就会提高不少。 为了避免后续数据会被多次搬移，可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。JVM 标记清除垃圾回收算法的核心思想。 0.2.3. 警惕数组的访问越界问题 根据语言的不同，数组越界的问题不同，在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据前面讲的数组寻址公式，越界的数组访问了不属于数组的内存地址上，得到上个内存地址上保存的值。 数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误，这种情况下，一般都会出现莫名其妙的逻辑错误。 很多计算机病毒正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。 但并非所有的语言都像 C 一样，把数组越界检查的工作丢给程序员来做，像 Java 本身就会做越界检查，抛出java.lang.ArrayIndexOutOfBoundsException。 0.3. 容器能否完全替代数组 针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、C++ STL 中的 vector。 以Java为例，ArrayList 优势： 将数组操作的细节封装起来（如插入、删除数据时需要搬移其他数据等） 支持动态扩容（存储空间不够时，不需要关心底层的扩容逻辑，会将空间自动扩容为 1.5 倍大小） 注意：因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。 也存在一些局限性： Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。 表示多维数组时，用数组往往会更加直观，Object[][] arrayVSArrayList<ArrayList<object>>array。 对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
0.1. 数据结构与算法 0.2. 分析、统计算法的执行效率和资源消耗 0.2.1. 事后统计法 0.2.2. 大O复杂度表示法 0.2.3. 时间复杂度分析 0.2.3.1. 只关注循环执行次数最多的一段代码 0.2.3.2. 加法法则：总复杂度等于量级最大的那段代码的复杂度 0.2.3.3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 0.2.3.4. 常见时间复杂度分析 0.2.3.4.1.
0.1. Redis中数据结构 0.1.1. 键和值的结构组织 0.1.2. 哈希表操作阻塞 0.1.3. 集合数据操作效率 0.1.3.1. 压缩列表 0.1.3.2. 跳表 0.1.4. 操作的效率 0.1.4.1. 单元素操作 0.1.4.2. 范围操作 0.1.4.3. 统计操作 0.1.4.4. 例外情况 Redis的快主要表现在，它接受到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。 Redis是内存数据库，所有操作都是在内存中完成，内存的访问速度本身就很快 Redis中的键值对是按一点的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，高效的数据结构是Redis快速处理数据的基础 0.1. Redis中数据结构 底层数据结构共6种： 简单动态字符串 双向链表 压缩列表 哈希表 跳表 整数数组 从上图可以看出，String类型的底层实现只有一种数据结构，就是简单动态字符串，List、Hash、Set、Sorted Set底层都有两种实现结构，它们的特点是一个键对应了一个集合的数据，这些数据结构都是值的底层实现。 0.1.1. 键和值的结构组织 为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。 一个哈希表其实就是一个数组，数组的每个元素称为一个哈希桶，所以一个哈希表由多个哈希桶组成，每个哈希桶中保持了键值对数据。哈希桶中实际上并不保存值本身，而是指向具体值的指针。 如下图所示，哈希桶中的entry元素中保存了*key和*value指针，分别指向了实际的键和值，这样即使值是一个集合，也可以通过*value指针被查找到。 这个哈希表中保存了所有的键值对，称为全局哈希表，有了它只需要O(1)的时间复杂度来快速查找到键值对。 0.1.2. 哈希表操作阻塞 某一时刻，可能哈希表的操作变慢了，因为存在哈希冲突问题和refresh可能带来操作阻塞。 随着数据量的增加，哈希冲突不可避免，Redis使用链表法（同一个桶中多个元素用一个链表来保存）来解决冲突。 如上图所示，entry1、entry2、entry3都需要保存在哈希桶3中，导致了哈希冲突，因此使用*next指针来链接它们。 哈希冲突链上的元素只能通过指针逐一查找来操作，随着数据的增大，冲突变多，链表过长，进而导致这个链表上元素的查找耗时长，效率低下。 为了解决链表过长导致查找效率低下这个问题，Redis对哈希表做refresh操作（增加现有桶的数量），让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中元素数量，减少单个桶中的冲突。 为了是refresh操作更高效，Redis默认使用两个全局哈希表（哈希表1和哈希表2）： 刚插入数据时，默认使用哈希表1，此时哈希表2并没有被分配空间 随着数量逐步增多，Redis开始执行refresh 给哈希表2分配更大空间（哈希表1的2倍） 把哈希表1中的数据重新映射并拷贝到哈希表2中（这里涉及大量数据拷贝，优化：渐进式，每处理一个请求，从哈希表1的第一个索引位置开始，将所有entry拷贝到哈希表2中） 释放哈希表1的空间 refresh中第二步的优化操作，如上图所示，巧妙的将一次性大量拷贝的开销，分摊到了多次处理请求的过程中。 0.1.3. 集合数据操作效率 Redis的键和值是通过哈希表组织的， String类型的数据，找到哈希桶就能直接增删改查，操作复杂度O(1) 集合类型的数据 通过全局哈希表查找到对应的哈希桶位置 在集合中再增删改查 集合类型的数据： 操作效率与集合底层数据结构有关。使用哈希表实现的集合要比使用链表实现的集合访问效率高。 操作效率与操作本身的执行特点有关。读写一个元素的操作要比读写所有元素的效率高。 总共有5中底层的数据结构： 数据结构 操作特征 操作复杂度 整数数组 顺序读写，通过下标访问 O(n) 双向链表 顺序读写，通过指针逐个访问 O(n) 哈希表 通过计算哈希值访问 O(1) 压缩列表 可快速定位头尾 O(n) 跳表 通过多级索引访问 O(logn) 0.1.3.1. 压缩列表 类似数据，数组中每一个元素都对应保存一个数据，不同点在于表头有zlbytes（列表长度）、zktail（列表尾的偏移量）、zllen（类别中entry个数），在列表尾部zlend（列表结束符）。 在压缩列表中： 查找第一个和最后一个元素：通过表头三个字段和长度直接定位，时间复杂度O(1) 查找其他元素：逐个查找，时间复杂度O(n) 0.1.3.2. 跳表 有序链表只能逐一查找元素，导致操作缓慢，跳表在链表的基础上，增加多级索引，通过索引位置的几个跳转，实现数据的快速定位，时间复杂度O(logn) 0.1.4. 操作的效率 集合类型的操作很多： 读写单个集合元素：HGET、HS 操作多个元素：SADD 对整个集合进行遍历：SMEMBERS 单元素操作时基础，范围操作非常耗时，统计操作通常高效、例外情况只有几个。 0.1.4.1. 单元素操作 每一种集合类型对单个数据实现的增删改查操作。 Hash类型的HGET、HSET、HDEL：O(1) Set类型的SADD、SREM、SRANDMEMBR：O(1) 这次操作的复杂度由集合采用的数据结构决定。 集合类型支持同时多多个元素进行增删改查，此时时间复杂度由当元素操作的时间复杂度和元素个数决定： Hash类型的HMGET、HMSEZT：O(m)，同时操作m个元素 Set类型的SADD 0.1.4.2. 范围操作 集合类型中的遍历操作，可以返回集合中所有数据： Hash类型的HGETALL Set类型的SMEMBERS 也可以返回一个范围内的部分数据： List类型的LRANGE：O(n) ZSet类型的ZRANGE：O(n) 2.8版本，增加HSCAN操作，渐进式遍历，避免了一次性返回所有元素导致Redis阻塞。 0.1.4.3. 统计操作 集合类型对集合中所有元素个数的记录。例如LLEN和SCARD，时间复杂度O(1)，因为当集合类型采用压缩列表、双向链表、整数数组时，这些数据结构中会专门记录元素的个数。 0.1.4.4. 例外情况 某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。 对于List类型的LPOP、RPOP、LPUSH、RPUSH操作时在列表的头尾进行增删元素，通过偏移量直接定位，时间复杂度是O(1)。