数据结构与算法

我们学习数据结构和算法，并不是为了死记硬背几个知识点。我们的目的是建立时间复杂度、空间复杂度意识，写出高质量的代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善你的人生。学会解决实际问题的方法。

算法复杂度分析

• 只关注循环执行次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

复杂度量级

• 常量阶O(1)

  public static void main(String[] args) {
  {
      func();
  }
  private void func()
  {
      int i=0;//执行1次
      i++;//执行1次
      i++;//执行1次
      i++;//执行1次
  }
  // 共执行了4次，所以时间复杂度为O(4);根据大O推导法，略去常数，所以此函数的时间复杂度为O(1);无论代码执行了多少行，其他区域不会影响到操作，这个代码的时间复杂度都是O(1)

• 对数阶O(logn)

  public static void main(String[] args) {
  {
      for(int i=0;i<n;i++) 
      {
          func();
          i = 2*i;
      }
  }
  private void func()
  {
      int i=0;//执行1次
      i++;//执行1次
      i++;//执行1次
      i++;//执行1次
  }
  // 由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由2的x次方=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。

• 线性阶O(n)

  public static void main(String[] args) {
  {
      for(int i=0;i<n;i++) // for循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此可以用O(n)来表示它的时间复杂度。
      {
          func();
          func();
      }
  }
  private void func()
  {
      int i=0;//执行1次
      i++;//执行1次
      i++;//执行1次
      i++;//执行1次
  }
  // func共被执行了2n次，main的时间复杂度为O(2n);根据大O推导法，略去常数系数，所以main的时间复杂度仍为为O(n);

• 线性对数阶O(nlogn)

  public static void main(String[] args) {
  {
      for( m = 1 ; m < n ; m++){
        for(int i=0;i<n;i++) 
        {
            func();
            i = 2*i;
        }
      }
  }
  private void func()
  {
      int i=0;//执行1次
      i++;//执行1次
      i++;//执行1次
      i++;//执行1次
  }
  // 将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)。

• 平方阶O(n2) O(n3)
• 指数阶O(2n)
• 阶乘阶O(n!)

如果一个问题用A算法需要2*n^2次操作，B算法需要100*n^2次操作，那他们的复杂度都是O(n^2)，尽管B的耗时总是A的大约50倍。复杂度只表示消耗的时间/空间随问题规模增长而增长的趋势，所以判断算法的速度不能只看复杂度。

空间复杂度就比较简单，比如申请一个长度为n的数组，空间复杂度就是O(n)。空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。通过这个举例，递归第n个斐波那契数的话，递归调用栈的深度就是n 那么每次递归的空间复杂度是O(1)， 调用栈深度为n，最后 这个递归算法的空间复杂度就是 n * 1 = O（n），递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度。（也就是算法用到的额外空间，是对一个算法在运行过程中临时占用存储空间大小的量度）
空间复杂度：算法开始运行直至结束过程中所需要的最大存储资源开销的一种度量。
一维数组的空间复杂度是 O ( n )
n*n矩阵的空间复杂度为 O ( n ^ 2 )

还可以划分成：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度

线性表

数组

线性表数据结构。连续的内存空间，存储一组具有相同类型的数据。根据下标随机访问的时间复杂度为 O(1)。

普通数组：

1. 查找复杂度，下标直接定位：O(1)
2. 添加/删除复杂度，需要移位置：O(n)

无下标数组:

有序无下标数组:

链表

Java中：LinkedList,LinkedHashMap
链表类型有：单链表，双向链表，循环链表,双向循环链表
缓存满时淘汰策略：先出策略 FIFO、最少使用策略 LFU、最近最少使用策略 LRU
关注点：单链表反转，链表中环的检测，两个有序的链表合并，删除链表倒数第 n 个结点，求链表的中间结点

1. 查找复杂度：O(n)
2. 添加/删除复杂度：O(1)

单向无序链表:

单向有序链表:

树

二叉排序树:
二叉排序树又称二叉查找树，它或是一棵空的二叉树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有节点的值均小于根节点的值
若它的右子树不空，则右子树上所有节点的值均大于根节点的值
它的左右子树也都是二叉排序树

查:
给定值的比较次数等于给定值节点在二叉排序树中的层数。如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为log2n +1,其查找效率为O(log2n)，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在O(log2n)到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。

增/删/改:
同理如查

栈

只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性。
用数组实现的栈，叫作顺序栈，用链表实现的栈，叫作链式栈。空间复杂度是 O(1)，时间复杂度是 O(1)
关注点：动态扩容

队列

队列最大的特点就是先进先出，主要的两个操作是入队和出队。它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。
关注点：柱塞队列

数组实现

链表实现

若只设头指针，则出队和入队的时间复杂度分别是（ 含头结点时为O(1)、不含头结点时为 O(n) ）和（O(n)）
若只设尾指针，则出队和入队的时间复杂度分别是（O(1)）和（ O(1)）

a) 如果只有头指针，且含头结点

1. 出队: O(1)，因为只要把头结点的下一个结点删除就好了
2. 入队: O(n)，要把新的结点插入到队尾，必须把队列历遍，找到队尾，才能插入
   b) 如果只有头指针，不含头结点
3. 出队: O(n)，要把头结点删除，必须历遍队列，找到队尾，才能更新头指针 (循环单链的缘故，如果仅仅是普通单链，则本操作也是O(1) )
4. 入队: O(n)，同 (a).2
   c) 如果只有尾指针
5. 出队: O(1)，只要把尾指针的下一个结点(没有头结点的情况)或者下下个结点(有头结点的情况)删除即可
6. 入队: O(1)，只要在尾指针的后面插入新的结点，并更新尾结点，所以是O(1)

递归

满足3点：

• 一个问题的解可以分解为几个子问题的解
• 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
• 存在递归终止条件
  关注点：堆栈溢出、重复计算、函数调用耗时多、空间复杂度高

排序算法

排序算法的执行效率：
最好情况、最坏情况、平均情况时间复杂度
时间复杂度的系数、常数 、低阶
比较次数和交换（或排序移动）次数
排序算法的内存消耗：
原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。
排序算法的稳定性：
经过某种排序算法排序之后，如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法

冒泡排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法的原理如下：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

初始： 4 5 6 3 2 1

图中每一竖列是一次比较交换：

图中可以看出，经过一次冒泡，6这个当前数组中最大的元素飘到了最上面，如果进行N次这样操作，那么数组中所有元素也就到飘到了它本身该在的位置，就像水泡从水中飘上来，所以叫冒泡排序。因为是左右交换，所以如果他们相等，肯定不会交换。所以是稳定的。

以上，第五第六次可以看到，其实第五次冒泡的时候，数组已经是有序的了，因此，还可以优化，即如果当次冒泡操作没有数据交换时，那么就已经达到了有序状态

public void bubbleSort(Integer[] arr, int n) {
    if (n <= 1) return;       //如果只有一个元素就不用排序了

    for (int i = 0; i < n; ++i) {
        // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
        boolean flag = false;
        for (int j = 0; j < n - i - 1; ++j) {        //此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，
            // 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少
            if (arr[j] > arr[j + 1]) {        //即这两个相邻的数是逆序的，交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) break;//没有数据交换，数组已经有序，退出排序
    }
}

平均时间复杂度为：O(n2)

插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

初始： 4 5 6 1 3 2
一次插入的过程：

整个过程：

选择排序（Selection Sort

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

初始： 4 5 6 3 2 1

整个过程：

	是原地排序	是否稳定	最好 最坏 平均
冒泡排序	是	是	O(n) O(n2) O(n2)
插入排序	是	是	O(n) O(n2) O(n2)
选择排序	是	否	O(n2) O(n2) O(n2)

归并排序，快速排序

归并排序

① 分解 – 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 – 递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 – 将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]。

归并排序比较：

归并排序过程：

如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？

注意点：归并函数的两个有序数组merge合并操作的技巧。

快速排序

快速排序也是用的分治的思想。如果要排序的数组下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。遍历p到r的数据，小于pivot的放在左边，大于的放在右边，pivot放中间。

根据分治与递归的思想，可以用递归排序下标从p到q-1之间的数据和下标q+1到r之间的数据，直到区间缩小为1。

上图实现O(1)空间复杂度，排序的原地算法，分区过程。如果不考虑空间消耗可以简单除暴直接建立两个临时数组，存储小于pivot与大于pivot的元素，再按顺序拷贝到A[p…r]中，但是partition()就要消耗很多额外空间，快排就不是原地排序算法了。

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理，理解快排的重点也是理解递推公式，还有 partition() 分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是 O(n2)，但是平均情况下时间复杂度都是 O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n2) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。

桶排序

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
如何根据年龄给 100 万用户排序?

计数排序

桶排序的一种特殊情况

基数排序

需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。

排序优化

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
时间复杂度是 O(logn)。
二分查找应用场景的局限性:

• 二分查找依赖的是顺序表结构，简单点说就是数组。
• 二分查找针对的是有序数据。
• 数据量太小不适合二分查找。
• 数据量太大也不适合二分查找。
  二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

如何设计数据结构和算法，快速判断某个整数是否出现在这 1000万数据中？
答：存入数组，排序，二分查找。

二分查找变形

如何快速定位IP对应的省份？
答：IP转换成对应的32位整数，数组排序，二分查找区间。

跳表

链表加多级索引的结构，就是跳表。
查询任意数据的时间复杂度就是 O(logn)。跳表的空间复杂度是 O(n)。空间换时间的设计思路。
跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。
作为一种动态数据结构，比起红黑树来说，实现要简单多了。

Redis用是跳表实现有序集合

散列表（Hash Table）

由数组演化而来。
当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。装载因子（load factor）来表示空位的多少。

Word 文档中单词拼写检查功能是如何实现的？
把词典存入散列表，快速查询

工业级散列表

如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列表性能的急剧下降，并且能抵抗散列碰撞攻击？
Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。Linked实际指的是双向链表。
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表 。
HashMap 装载因子0.75， 扩容2倍
重点关注：如何设计散列函数，如何根据装载因子动态扩容，以及如何选择散列冲突解决方法。

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。
因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列表和链表（或者跳表）结合在一起使用。
LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。

hash算法

MD5 SHA
这里就基于组合数学中一个非常基础的理论，鸽巢原理（也叫抽屉原理）。
第一个应用是唯一标识，哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。
第二个应用是用于校验数据的完整性和正确性。
第三个应用是安全加密，我们讲到任何哈希算法都会出现散列冲突，但是这个冲突概率非常小。
第四个应用是散列函数。
哈希算法在分布式系统中的应用，它们分别是：负载均衡、数据分片、分布式存储。
**一致性哈希算法 **

二叉树

链式存储法
顺序存储法，完全二叉树存储节省空间，比如堆

如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历
关键点：：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。完全二叉树，满二叉树
平衡二叉查找树，时间复杂度可以做到稳定的 O(logn)

满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满，并没有满。

二叉树比较好理解，有n叉树的，比如b树，并且二叉树比较好做搜索树这种的，一般的问题，二叉树足够搞定。b树是为了解决内存不够，减少硬盘io的问题。B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）

如果二叉树退变为列表了，则 n 个节点的高度或者说是长度变为了n，查找效率为O(n)，变成了顺序查找。

红黑树

解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
红黑树要求：
根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n　。
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。

堆

堆是一种完全二叉树。它最大的特性是：每个节点的值都大于等于（或小于等于）其子树节点的值。因此，堆被分成了两类，大顶堆和小顶堆。
堆排序。
主要应用：优先级队列、求 Top K 问题和求中位数问题。
优先级队列是一种特殊的队列，优先级高的数据先出队，而不再像普通的队列那样，先进先出。实际上，堆就可以看作优先级队列，只是称谓不一样罢了。

图

概念：无向图、有向图、带权图、顶点、边、度、入度、出度。
两个主要的存储方式：邻接矩阵和邻接表。
邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。

广度优先搜索和深度优先搜索

广度优先搜索（BFS）
深度优先搜索（DFS）

也被叫作暴力搜索算法

广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。

字符串匹配

BF 算法
RK 算法
BM（Boyer-Moore）算法
KMP算法

trie树 字典树

第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。
第三：每个单词的公共前缀作为一个字符节点保存。

搜索引擎搜索关键词提示功能，适合前缀匹配的场景

（1）词频统计：
可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？对于百亿级别的数据样本还能这么玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。

AC 自动机

多模式串匹配算法，敏感词过滤场景

贪心算法，霍夫曼编码

• 分糖果
• 钱币找零
• 区间覆盖

霍夫曼编码，根据贪心的思想，我们可以把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。

分治算法 mapreduce

原问题分解成子问题，子问题合并成原问题。
海量数据处理，克服内存限制。
比如：处理100T数据，几十亿网页

回溯算法

大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。

尽管回溯算法的原理非常简单，但是却可以解决很多问题，比如深度优先搜索、八皇后、0-1 背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配等等。

动态规划

大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的.
使用场景：购物凑单，0-1背包升级版

拓扑排序

最短路径

地图软件计算最优出行路径，Dijstra算法

位图

Java:BitSet。Redis:BitMap。Google的Guava工具包提供了BloomFilter布隆过滤器
网页爬虫URL去重。
布隆过滤器，存在误判。扩容。误判的率跟哈希函数的个数，位图大小有关。适合允许小概率误判的场景。

BloomFilter的核心思想有两点：

• 多个hash，增大随机性，减少hash碰撞的概率
• 扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率。

BloomFilter的应用

1. 黑名单
   比如邮件黑名单过滤器，判断邮件地址是否在黑名单中
2. 排序(仅限于BitSet)
   仔细想想，其实BitSet在set(int value)的时候，“顺便”把value也给排序了。
3. 网络爬虫
   判断某个URL是否已经被爬取过
4. K-V系统快速判断某个key是否存在
   典型的例子有Hbase，Hbase的每个Region中都包含一个BloomFilter，用于在查询时快速判断某个key在该region中是否存在，如果不存在，直接返回，节省掉后续的查询。

概率统计

垃圾短信过滤：

1. 基于黑名单
2. 基于规则的过滤
3. 基于概率统计的过滤

朴素贝叶斯算法
P(Y|X)=P(X|Y)P(Y)/P(X)

向量空间

应用：音乐推荐系统

基于爱好的相似度，基于相似歌曲

欧几里德距离

B+树

B树（B-tree）B是平衡，是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

B-树就是B树

B 树可以看作是对查找树的一种扩展，即他允许每个节点有M-1个子节点。

1. 每个节点最多拥有m个子树
2. 根节点至少有2个子树
3. 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
4. 所有叶子节点都在同一层、每个节点最多可以有m-1个key（可以根据key快速判断子节点大概位置），并且以升序排列

B树的搜索：从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B+树是对B树的一种变形树，它与B树的差异在于：

1. 有k个子结点的结点必然有k个关键码，每个关键码不保存数据，只用来索引，所有数据都保存在叶子节点；
2. 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
3. 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

B+ 树的优点在于：

由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

B+树 就是M叉树，写入操作要更新索引，索引分裂。
它通过存储在磁盘的多叉树结构，做到了时间、空间的平衡，既保证了执行效率，又节省了内存。
前面的讲解中，为了一步一步详细地给你介绍 B+ 树的由来，内容看起来比较零散。为了方便你掌握和记忆，我这里再总结一下 B+ 树的特点：

1. 每个节点中子节点的个数不能超过 m，也不能小于 m/2；
2. 根节点的子节点个数可以不超过 m/2，这是一个例外；
3. m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
4. 通过链表将叶子节点串联在一起，这样可以方便按区间查找；
5. 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。

而 B 树实际上是低级版的 B+ 树，或者说 B+ 树是 B 树的改进版。B 树跟 B+ 树的不同点主要集中在这几个地方：

1. B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；
2. B 树中的叶子节点并不需要链表来串联。
3. 也就是说，B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树。

搜索

曼哈顿距离

要找出起点 s 到终点 t 的最短路径，最简单的方法是，通过回溯穷举所有从 s 到达 t 的不同路径，然后对比找出最短的那个。不过很显然，回溯算法的执行效率非常低，是指数级的。

Dijkstra 算法在此基础之上，利用动态规划的思想，对回溯搜索进行了剪枝，只保留起点到某个顶点的最短路径，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，但它实际上也考察到了所有从起点到终点的路线，所以才能得到最优解。

A* 算法之所以不能像 Dijkstra 算法那样，找到最短路径，主要原因是两者的 while 循环结束条件不一样。刚刚我们讲过，Dijkstra 算法是在终点出队列的时候才结束，A* 算法是一旦遍历到终点就结束。

A* 算法属于一种启发式搜索算法（Heuristically Search Algorithm）。实际上，启发式搜索算法并不仅仅只有 A* 算法，还有很多其他算法，比如 IDA* 算法、蚁群算法、遗传算法、模拟退火算法等。

启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。这种算法找出的路线，并不是最短路线。但是，实际的软件开发中的路线规划问题，我们往往并不需要非得找最短路线。所以，鉴于启发式搜索算法能很好地平衡路线质量和执行效率，它在实际的软件开发中的应用更加广泛。

索引

海量数据快速查找某个数据

类似 Redis 这样的 Key-Value 数据库中的索引，又是怎么实现的呢？底层依赖的又是什么数据结构呢？
索引这个概念，非常好理解。你可以类比书籍的目录来理解。如果没有目录，我们想要查找某个知识点的时候，就要一页一页翻。通过目录，我们就可以快速定位相关知识点的页数，查找的速度也会有质的提高。
对于系统设计需求，我们一般可以从功能性需求和非功能性需求两方面来分析，这个我们之前也说过。因此，这个问题也不例外。

功能性需求：

• 数据是格式化数据还是非格式化数据
• 数据是静态数据还是动态数据
• 索引存储在内存还是硬盘
• 单值查找还是区间查找
• 单关键词查找还是多关键词组合查找

像 MySQL 这种结构化数据的查询需求，我们可以实现针对多个关键词的组合，建立索引；对于像搜索引擎这样的非结构数据的查询需求，我们可以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。

非功能性需求：

• 不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大
• 在考虑索引查询效率的同时，我们还要考虑索引的维护成本

构建索引常用的数据结构有哪些？
散列表、红黑树、跳表、B+ 树。除此之外，位图、布隆过滤器可以作为辅助索引，有序数组可以用来对静态数据构建索引。

我们知道，散列表增删改查操作的性能非常好，时间复杂度是 O(1)。一些键值数据库，比如 Redis、Memcache，就是使用散列表来构建索引的。这类索引，一般都构建在内存中。
红黑树作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是 O(logn)，也非常适合用来构建内存索引。Ext 文件系统中，对磁盘块的索引，用的就是红黑树。
B+ 树比起红黑树来说，更加适合构建存储在磁盘中的索引。B+ 树是一个多叉树，所以，对相同个数的数据构建索引，B+ 树的高度要低于红黑树。当借助索引查询数据的时候，读取 B+ 树索引，需要的磁盘 IO 次数非常更少。所以，大部分关系型数据库的索引，比如 MySQL、Oracle，都是用 B+ 树来实现的。
跳表也支持快速添加、删除、查找数据。而且，我们通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis 中的有序集合，就是用跳表来构建的。
除了散列表、红黑树、B+ 树、跳表之外，位图和布隆过滤器这两个数据结构，也可以用于索引中，辅助存储在磁盘中的索引，加速数据查找的效率。我们来看下，具体是怎么做的？

实际上，有序数组也可以被作为索引。如果数据是静态的，也就是不会有插入、删除、更新操作，那我们可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据。

其他应用：ES中单排索引用了trie树，对每个需要的key维护了一个trie树，用于定位这个key在文件中的位置，然后用有序列表直接去访问对应的documents。区块链，以太坊，存储用的是leveldb，数据存储用的是帕特利夏树，一种高级trie树，很好的做了数据压缩。消息中间件像kafka，会做持久化，每个partition都会有很多数据，每个partition也会建立索引，快速访问。

并行算法

如果算法无法优化了，利用并行处理提高算法执行效率。

并行排序

归并排序并行化处理
快速排序并行化处理

并行查找

比如散列表扩容，可以把大散列表分隔成小散列表分别根据情况扩容

并行字符串匹配

大文本分隔成小文本，比如分隔成16份。解决词组被分隔的情况，比如词组长度m，可以把文本结尾开始各取m，两个文本开头结尾2m重新查找。

并行搜索

增加队列配合

假设我们有 n 个任务，为了提高执行的效率，我们希望能并行执行任务，但是各个任务之间又有一定的依赖关系，如何根据依赖关系找出可以并行执行的任务？
答：用一个有向图存储任务直接的依赖关系，然后用拓扑排序的思想执行任务，每个任务都找到入度为0的，放在队列里，启动线程池执行，队列里的任务并行执行完毕，再调用拓扑排序找到入度为0的放入队列，知道所有任务执行完毕。

Disruptor

性能影响

需要具体分析，比如你原先执行一个业务是循环更新数据库中的数据，如果增加一个业务是更新之前再做个判断是否存在，如果存在则更新不存在则插入，其实性能消耗提升并不多，不是说会把系统拖垮10倍100倍那种。假设更新需要1秒，加上校验可能变成1.5秒，这些都是可以接受的。