数据结构和算法基础

前言

什么是数据结构？什么是算法？

数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

为什么要学习数据结构和算法？

为了提高代码的性能，利用数据结构和算法解决如何更省、更快地存储和处理数据的问题

如何衡量？

使用时间和空间复杂度来考量效率和资源的消耗

本篇主要介绍10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

学习数据结构和算法，应该学习它的由来、特性、适用的场景以及它能解决的问题。

参考：

  • 《数据和结构之美》–王铮

在线阅读推荐： Hello算法

复杂度分析-大 O 复杂度表示法

时间复杂度分析

1. 只关注循环执行次数最多的一段代码

1
2
3
4
5
6
7
8
int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

时间复杂度就是 O(n)

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }
 
   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

时间复杂度就为 O(n2)

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cal(int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

时间复杂度就为 O(n2)

几种常见的时间复杂度

1. O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。

1
int i = 8; int j = 6; int sum = i + j;

只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，*一般情况下*，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)**。

2. O(logn)、O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。 

1
2
3
4
i=1; 
while (i <= n)  { 
  i = i * 2; 
  }

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：

image.png

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x ，x=log2n，所以，这段代码的时间复杂度就是 O(log2n)。
如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

3. O(m+n)、O(m*n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }
 
  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }
 
  return sum_1 + sum_2;
}

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int cal(int m, int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int m) {
  int sum = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为乘法法则 O(m*n)

空间复杂度分析

1
2
3
4
5
6
7
8
9
10
11
void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }
 
  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。

复杂度量级和增长关系

image.png
image.png

数组

定义

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表（Linear List）：数组，链表、队列、栈等。

非线性表：二叉树、堆、图等。在非线性表中，数据之间并不是简单的前后关系。

代码演示

1
2
3
4
5
6
7
8
9
public class Test {  
    public static void main(String[] args) throws InterruptedException, ClassNotFoundException {  
        int[] arr={1,2,3,4,5,6};  
        for (int i = 0; i < arr.length; i++) {  
            System.out.println("i = " + arr[i]);  
        }  
  
    }  
}

特点

查询效率高，插入、删除效率低

查询效率高的原理

支持随机访问，即通过下标索引访问。

如何实现随机访问？

由于数组的存储方式是线性的，且为连续的内存空间，故可以通过寻址公式来访问指定的数据。

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10] 来举例。在我画的这个图中，计算机给数组 a[10]，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。

image.png

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

1
a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里，数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。

插入、删除效率低的原因

数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。
假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。
删除，同理，也需要迁移数据。

警惕数组的访问越界问题

 Java 本身就会做越界检查，会抛出 java.lang.ArrayIndexOutOfBoundsException。

1
2
int[] a = new int[3];
a[3] = 10;

应用

JVM 标记清除垃圾回收算法的核心思想

数组 a[10] 中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。

image.png

为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、C++ STL 中的 vector。在项目开发中，什么时候适合用数组，什么时候适合用容器呢？

Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗。对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

链表

介绍

从图中我们看到，数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。

而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。

image.png

单链表

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。

image.png

单链表有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Test {  
    public static void main(String[] args) throws InterruptedException, ClassNotFoundException {  
        ListNode l1 = new ListNode(4);  
        ListNode l2 = new ListNode(3,l1);  
        ListNode l3 = new ListNode(2,l2);  
        ListNode l4 = new ListNode(1,l3);  
  
        //第3个节点之前插入一个5  
        ListNode insertL5 = new ListNode(5);  
        ListNode dumy=l4;  
        int i=0;  
        while (dumy!=null){  
            i++;  
            if(i==2){  
                insertL5.next=dumy.next;  
                dumy.next=insertL5;  
            }  
            dumy=dumy.next;  
        }  
  
        ListNode head=l4;  
        while (head!=null){  
            System.out.println("head = " + head.val);  
            head=head.next;  
        }  
  
    }  
  
    public static class ListNode{  
        int val;  
        ListNode next;  
  
        public ListNode(int val) {  
            this.val = val;  
        }  
  
        public ListNode(ListNode next) {  
            this.next = next;  
        }  
  
        public ListNode(int val, ListNode next) {  
            this.val = val;  
            this.next = next;  
        }  
    }  
}

特点

插入、删除效率高，查询效率低。

针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。

image.png

但是，有利就有弊。链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

你可以把链表想象成一个队伍，队伍中的每个人都只知道自己后面的人是谁，所以当我们希望知道排在第 k 位的人是谁的时候，我们就需要从第一个人开始，一个一个地往下数。所以，链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。

警惕指针丢失和内存泄漏

image.png
如图所示，我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。

1
2
p->next = x;  // 将 p 的 next 指针指向 x 结点；
x->next = p->next;  // 将 x 的结点的 next 指针指向 b 结点；

初学者经常会在这儿犯错。p->next 指针在完成第一步操作之后，已经不再指向结点 b 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next，自己指向自己。因此，整个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了。

对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。所以，我们插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。所以，对于刚刚的插入代码，我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。

同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。

应用

用双向链表实现 LRU 缓存淘汰策略

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

LinkedHashMap底层是双向链表，使用LinkedHashMap实现LRUCache。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Test {  
    public static void main(String[] args)  {  
        LRUCache<String, Integer> lru = new LRUCache<>(5);  
        lru.put("1",1);  
        lru.put("2",2);  
        lru.put("3",3);  
        lru.put("4",4);  
        while (true){  
            Scanner sc = new Scanner(System.in);  
            System.out.println(  
                    "请选择操作编号：" +  
                    "1：插入；" +  
                    "2: 查询；");  
            int select  = sc.nextInt();  
            String key;  
            int val;  
            switch (select){  
                case 1:  
                    System.out.println("请输入key：");  
                    key = sc.next();  
                    System.out.println("请输入value：");  
                    val = sc.nextInt();  
                    lru.put(key,val);  
                    System.out.println("lru = " + lru);  
                    break;  
                case 2:  
                    System.out.println("请输入key：");  
                    key = sc.next();  
                    System.out.println("val = " + lru.get(key));  
                    System.out.println("lru = " + lru);  
                    break;  
            }  
  
  
        }  
    }  
    public static class LRUCache<K, V> extends LinkedHashMap<K, V> {  
        private final int capacity; // 缓存的容量  
  
        // 构造函数，设置初始容量和负载因子，并开启按访问顺序排列  
        public LRUCache(int capacity) {  
            super(capacity, 0.75f, true); // true 表示按访问重新排序  
            this.capacity = capacity;  
        }  
  
        // 当缓存中的元素个数超过容量时，自动删除最久未使用的元素,要重写该方法，否则就是正常的map  
        @Override  
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {  
            return size() > capacity;  
        }  
          
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
请选择操作编号：1：插入；2: 查询；
2
请输入key：
1
val = 1
lru = {2=2, 3=3, 4=4, 1=1}
请选择操作编号：1：插入；2: 查询；
1
请输入key：
5
请输入value：
5
lru = {2=2, 3=3, 4=4, 1=1, 5=5}
请选择操作编号：1：插入；2: 查询；
1
请输入key：
6
请输入value：
6
lru = {3=3, 4=4, 1=1, 5=5, 6=6}

用循环链表实现约瑟夫问题

栈

介绍

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Test {  
    public static void main(String[] args)  {  
        ArrayDeque<Integer> stack = new ArrayDeque<>();  
        stack.push(1);  
        stack.push(2);  
        stack.push(3);  
        System.out.println("stack = " + stack);  
        System.out.println("stack.peek() = " + stack.peek());  
        System.out.println("stack.pop() = " + stack.pop());  
        System.out.println("stack = " + stack);  
        /**  
         * stack = [3, 2, 1]         
         * stack.peek() = 3         
         * stack.pop() = 3         
         * stack = [2, 1]         
        */    
         
	}  
}
  • **Stack**：传统的线程安全栈实现，基于 Vector，性能较差，已不推荐使用。
  • **ArrayDeque**：更高效的、现代化的双端队列实现，既可用作栈，也可用作队列，推荐在单线程或手动处理同步的多线程环境中使用。

特点

只在栈顶插入和删除一个数据，先进后出

应用

队列

介绍

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

我们知道，栈只支持两个基本操作：**入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()**，从队列头部取一个元素。

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class QueueDemo {  
    public static void main(String[] args) {  
        // 创建一个队列  
        Queue<String> queue = new LinkedList<>();  
  
        // 向队列中添加元素  
        queue.offer("1");  
        queue.offer("2");  
        queue.offer("3");  
          
        // 显示队列内容  
        System.out.println("Queue: " + queue);  
  
        // 查看队首元素，不移除  
        String peekElement = queue.peek();  
        System.out.println("Peek element: " + peekElement);  
  
        // 移除队首元素  
        String removedElement = queue.poll();  
        System.out.println("Removed element: " + removedElement);  
  
        // 再次显示队列内容  
        System.out.println("Queue after poll: " + queue);  
  
        // 检查队列是否为空  
        boolean isEmpty = queue.isEmpty();  
        System.out.println("Is queue empty? " + isEmpty);  
  
        // 获取队列的大小  
        int size = queue.size();  
        System.out.println("Queue size: " + size);  
  
//        Queue: [1, 2, 3]  
//        Peek element: 1  
//        Removed element: 1  
//        Queue after poll: [2, 3]  
//        Is queue empty? false  
//        Queue size: 2  
    }  
}

特点

先进先出

作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

应用

递归算法

介绍

递归函数是在自身内部调用自己的函数。

代码演示

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FactorialDemo {

    // 定义递归函数，计算n的阶乘
    public static int factorial(int n) {
        // 基准条件：当n为0时返回1
        if (n == 0) {
            return 1;
        }
        // 递归调用：n * (n-1)!
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int number = 5;
        int result = factorial(number);
        System.out.println(number + "! = " + result);
    }
}

警惕堆栈溢出和重复计算

递归代码要警惕堆栈溢出

函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

那么，如何避免出现堆栈溢出呢？
我们可以通过在代码中限制递归调用的最大深度的方式可以一定程度上解决这个问题。

1
2
3
4
5
6
7
8
9
10
// 全局变量，表示递归的深度。
int depth = 0;
 
int f(int n) {
  ++depth；
  if (depth > 1000) throw exception;
  
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归代码要警惕重复计算

1
2
3
4
5
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

image.png

从图中，我们可以直观地看到，想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。

为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。

将递归代码改写为非递归代码

递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。
可以将递归代码改为迭代循环的非递归写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  int ret = 0;
  int pre = 2;
  int prepre = 1;
  for (int i = 3; i <= n; ++i) {
    ret = pre + prepre;
    prepre = pre;
    pre = ret;
  }
  return ret;
}

应用

递归算法在计算机科学中有许多应用，以下是一些常见的：

  1. 排序算法：

    • 快速排序 (Quick Sort) 和 归并排序 (Merge Sort) 都是基于递归的排序算法。快速排序通过递归地分割数组并对每个部分排序，归并排序则通过递归地分解问题并合并结果。

  2. 树结构遍历：

    • 对二叉树、B树等数据结构的遍历通常使用递归。例如，中序遍历、前序遍历、后序遍历等。

  3. 分治算法：

    • 递归常用于分治算法（Divide and Conquer）。例如，斐波那契数列、最大子数组和问题等都可以通过递归来分解问题。

  4. 图的遍历：

    • 图的深度优先搜索 (DFS) 和广度优先搜索 (BFS) 一般采用递归方式实现。

  5. **动态规划 (DP)**：

    • 在某些动态规划问题中，可以用递归来描述状态转移。尤其是带有重叠子问题的情形，通常结合记忆化搜索来优化递归算法。

  6. 回溯算法：

    • 回溯法本质上是一种递归方法，常用于解决组合问题、排列问题、数独等。例如，求解八皇后问题。

  7. 数学问题：

    • 许多数学问题可以通过递归解决，例如阶乘计算、斐波那契数列、汉诺塔问题等。

排序算法

常用的排序算法有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度把它们分成了三类：
image.png
如果对小规模数据进行排序，可以选择时间复杂度是 O(n2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
时间复杂度是 O(nlogn) 的排序算法不止一个，有归并排序、快速排序、堆排序。

冒泡排序

像气泡一样，每一轮把最大的数“冒”到最后。

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
image.png

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 冒泡排序，a 表示数组，n 表示数组大小
public void bubbleSort(int[] a, 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) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

插入排序

像插扑克牌一样，每次把新元素插入到前面已经排序好的部分。

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。
image.png

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 插入排序，a 表示数组，n 表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;
 
  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

选择排序

每次找到剩下元素中的最小值，放到正确位置。

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
image.png

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 定义一个选择排序的方法
public void selectionSort(int[] array) {
	int n = array.length;  // 获取数组的长度

	// 外层循环，从数组的第一个元素开始，依次固定位置
	for (int i = 0; i < n - 1; i++) {
		int minIndex = i;  // 假设当前 i 位置的元素是最小值

		// 内层循环，寻找剩下未排序部分中的最小值
		for (int j = i + 1; j < n; j++) {
			if (array[j] < array[minIndex]) {
				minIndex = j;  // 更新最小值的索引
			}
		}

		// 如果找到的最小值不是当前的元素，则交换
		if (minIndex != i) {
			int temp = array[i];
			array[i] = array[minIndex];
			array[minIndex] = temp;
		}
	}
}

冒泡、插入、选择排序这三种排序算法，它们的时间复杂度都是 O(n2)，比较高，适合小规模数据的排序。归并排序和快速排序，这两种排序算法适合大规模的数据排序，时间复杂度为 O(nlogn) 。

归并

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
image.png

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//归并
public static void mergeSort(int[] intervals, int lo, int hi) {
	if(lo>=hi)return;
	int mid=lo+((hi-lo)>>1);
	mergeSort(intervals,lo,mid);
	mergeSort(intervals,mid+1,hi);

	mergeSortRec(intervals,lo,mid,hi);

}

private static void mergeSortRec(int[] intervals, int lo, int mid, int hi) {
	int[] tmp = new int[hi - lo+1];
	int index=0;
	int p1=lo;
	int p2=mid+1;
	while (p1 <=mid || p2 <= hi) {//有一个没遍历完就继续添加
		if(p1>mid){//左边遍历完了
			tmp[index++]=intervals[p2++];
		}else if(p2>hi){//右边遍历完了
			tmp[index++]=intervals[p1++];
		} else if(intervals[p1]<=intervals[p2]){//左右都没遍历完
			tmp[index++]=intervals[p1++];
		}else{
			tmp[index++]=intervals[p2++];
		}

	}


	//System.arraycopy(tmp,0,intervals,lo,index);
	//自己实现
	for (int i = 0; i < tmp.length; i++) {
		intervals[lo+i]=tmp[i];
	}

}

快排

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

image.png

image.png

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static void quickSort(int[] nums, int lo, int hi) {
	if(lo>=hi )return;
	int pivot=partition(nums,lo,hi);
	quickSort(nums,lo,pivot-1);
	quickSort(nums,pivot+1,hi);
}

//快慢指针
private static int partition(int[] nums, int lo, int hi) {
	int pivot=nums[hi];
	int slow=lo;
	int speed=lo;
	while(speed<hi){
		if(nums[speed]<pivot){
			int tmp = nums[speed];
			nums[speed]=nums[slow];
			nums[slow]=tmp;
			slow++;
			speed++;
		}else{
			speed++;
		}
	}
	nums[speed]=nums[slow];
	nums[slow]=pivot;
	return slow;
}

桶排序

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
image.png
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

实际上，桶排序对要排序数据的要求是非常苛刻的。
首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

我们都经历过高考，高考查分数系统你还记得吗？我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？

考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

我们都经历过高考，高考查分数系统你还记得吗？我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？

基数排序

考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

我们再来看这样一个排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？

我们之前讲的快排，时间复杂度可以做到 O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢？现在我就来介绍一种新的排序算法，基数排序。

刚刚这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。

借助稳定排序算法，这里有一个巧妙的实现思路。还记得我们第 11 节中，在阐述排序算法的稳定性的时候举的订单的例子吗？我们这里也可以借助相同的处理思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

应用

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

我们选择数组区间 A[0…n-1] 的最后一个元素 A[n-1] 作为 pivot，对数组 A[0…n-1] 原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。

如果 p+1=K，那 A[p] 就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间，我们再按照上面的思路递归地在 A[p+1…n-1] 这个区间内查找。同理，如果 K<p+1，那我们就在 A[0…p-1] 区间查找。

现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？

每次从各个文件中取一条数据，在内存中根据数据时间戳构建一个最小堆，然后每次把最小值给写入新文件，同时将最小值来自的那个文件再出来一个数据，加入到最小堆中。这个空间复杂度为常数，但没能很好利用1g内存，而且磁盘单个读取比较慢，所以考虑每次读取一批数据，没了再从磁盘中取，时间复杂度还是一样O(n)。

分治算法

MapReduce 是 Google 大数据处理的三驾马车之一，另外两个是 GFS 和 Bigtable。它在倒排索引、PageRank 计算、网页分析等搜索引擎相关的技术中都有大量的应用。
 MapRedue 的本质就是分治算法，分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
 
归并排序就是使用的分治的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//归并
public static void mergeSort(int[] intervals, int lo, int hi) {
	if(lo>=hi)return;
	int mid=lo+((hi-lo)>>1);
	mergeSort(intervals,lo,mid);
	mergeSort(intervals,mid+1,hi);

	mergeSortRec(intervals,lo,mid,hi);

}

private static void mergeSortRec(int[] intervals, int lo, int mid, int hi) {
	int[] tmp = new int[hi - lo+1];
	int index=0;
	int p1=lo;
	int p2=mid+1;
	while (p1 <=mid || p2 <= hi) {//有一个没遍历完就继续添加
		if(p1>mid){//左边遍历完了
			tmp[index++]=intervals[p2++];
		}else if(p2>hi){//右边遍历完了
			tmp[index++]=intervals[p1++];
		} else if(intervals[p1]<=intervals[p2]){//左右都没遍历完
			tmp[index++]=intervals[p1++];
		}else{
			tmp[index++]=intervals[p2++];
		}

	}


	//System.arraycopy(tmp,0,intervals,lo,index);
	//自己实现
	for (int i = 0; i < tmp.length; i++) {
		intervals[lo+i]=tmp[i];
	}

}

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找是一种非常高效的查找算法，高效到什么程度呢？我们来分析一下它的时间复杂度。

我们假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。
image.png
可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

代码演示

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
 
  while (low <= high) {
    int mid = (low + high) / 2; //low+((high-low)>>1)
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
 
  return -1;
}

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}
 
private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;
 
  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}

使用场景

底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

应用

变体一：查找第一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

变体二：查找最后一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

变体三：查找第一个大于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

变体四：查找最后一个小于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

跳表

介绍

二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表（Skip list）
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。
那怎么来提高查找效率呢？如果像图中那样，对链表建立一级“索引”，查找起来是不是就会更快一些呢？每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引或索引层。你可以看我画的图。图中的 down 表示 down 指针，指向下一级结点。

image.png
这种链表加多级索引的结构，就是跳表。

当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。跳表是通过随机函数来维护前面提到的“平衡性”。
当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？

我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。
image.png

代码演示

链表的实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
class SkipListNode {  
    int value;  
    SkipListNode next;   // 当前层的下一节点  
    SkipListNode down;   // 下一层的节点  
  
    public SkipListNode(int value, SkipListNode next, SkipListNode down) {  
        this.value = value;  
        this.next = next;  
        this.down = down;  
    }  
}  
  
public class SkipList {  
    private static final int MAX_LEVEL = 16; // 跳表的最大层数  
    private SkipListNode head;  // 跳表的头节点  
    private int level;  // 当前跳表的层数  
    private Random random;  // 用于随机生成层数  
  
    public SkipList() {  
        this.level = 0;  // 初始化时跳表层数为0  
        this.head = new SkipListNode(-1, null, null);  // 头节点初始化，值为-1表示哨兵  
        this.random = new Random();  
    }  
  
    // 随机生成一个层数  
    private int randomLevel() {  
        int lvl = 0;  
        while (lvl < MAX_LEVEL && random.nextInt(2) == 1) {  // 以1/2的概率增加层数  
            lvl++;  
        }  
        return lvl;  
    }  
  
    // 查找元素  
    public boolean search(int target) {  
        SkipListNode current = head;  
  
        // 从最高层开始查找  
        while (current != null) {  
            while (current.next != null && current.next.value < target) {  
                current = current.next;  
            }  
            // 如果目标元素在当前层，直接返回  
            if (current.next != null && current.next.value == target) {  
                return true;  
            }  
            current = current.down;  // 向下跳到下一层  
        }  
        return false;  
    }  
  
    // 插入元素  
    public void insert(int value) {  
        SkipListNode current = head;  
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];//存储要插入位置的前驱节点  
  
        // 查找插入位置  
        for (int i = level; i >= 0; i--) {  
            while (current.next != null && current.next.value < value) {  
                current = current.next;  
            }  
            update[i] = current;  
            if (i > 0) {  
                current = current.down;  // 向下跳到下一层  
            }  
        }  
  
        // 随机生成一个层数  
        int newLevel = randomLevel();  
  
        // 如果新生成的层数比当前跳表层数大，需要创建新层  
        if (newLevel > level) {  
            level = newLevel;  
            head = new SkipListNode(-1, null, head);  // 新的头节点  
        }  
  
        SkipListNode downNode = null;  
        // 从0层开始插入节点  
        for (int i = 0; i <= newLevel; i++) {  
            SkipListNode newNode = new SkipListNode(value, update[i].next, downNode);  
            update[i].next = newNode;  
            downNode = newNode;  // 当前层的节点作为下一层的down节点  
        }  
    }  
  
    // 删除元素  
    public boolean delete(int value) {  
        SkipListNode current = head;  
        boolean found = false;  
  
        // 查找并删除目标节点  
        while (current != null) {  
            while (current.next != null && current.next.value < value) {  
                current = current.next;  
            }  
            if (current.next != null && current.next.value == value) {  
                found = true;  
                current.next = current.next.next;  // 删除当前层的节点  
            }  
            current = current.down;  // 向下跳到下一层  
        }  
  
        return found;  
    }  
  
    // 打印跳表  
    public void printList() {  
        SkipListNode current = head;  
        int levelCount = level;  
  
        while (current != null) {  
            System.out.print("Level " + levelCount-- + ": ");  
            SkipListNode node = current.next; //真正的头节点  
            while (node != null) {  
                System.out.print(node.value + " ");  
                node = node.next;  
            }  
            System.out.println();  
            current = current.down;  
        }  
    }  
  
    // 主方法用于测试  
    public static void main(String[] args) {  
        SkipList skipList = new SkipList();  
  
        skipList.insert(1);  
        skipList.insert(2);  
        skipList.insert(3);  
        skipList.insert(4);  
        skipList.insert(5);  
        skipList.insert(6);  
  
        System.out.println("跳表内容:");  
        skipList.printList();  
  
        System.out.println("\n查找3: " + skipList.search(3)); // true  
        System.out.println("查找7: " + skipList.search(7));   // false  
  
        skipList.delete(3);  
        System.out.println("\n删除3后跳表内容:");  
        skipList.printList();  
    }  
}

数组的实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
class SkipListNode {  
    int value;  
    SkipListNode[] forward;  // forward数组表示多级索引  
  
    // 构造函数  
    public SkipListNode(int value, int level) {  
        this.value = value;  
        this.forward = new SkipListNode[level + 1]; // 创建 level 层的 forward 指针  
    }  
}  
  
public class SkipList {  
    private static final int MAX_LEVEL = 16; // 跳表的最大层数  
    private SkipListNode head;  // 跳表的头节点  
    private int level;  // 当前跳表的层数  
    private Random random;  // 用于随机生成层数  
  
    public SkipList() {  
        this.level = 0;  // 初始化时跳表层数为0  
        this.head = new SkipListNode(-1, MAX_LEVEL);  // 头节点初始化，值为-1表示哨兵  
        this.random = new Random();  
    }  
  
    // 随机生成一个层数  
    private int randomLevel() {  
        int lvl = 0;  
        while (lvl < MAX_LEVEL && random.nextInt(2) == 1) {  // 以1/2的概率增加层数  
            lvl++;  
        }  
        return lvl;  
    }  
  
    // 查找元素  
    public boolean search(int target) {  
        SkipListNode current = head;  
        // 从最顶层开始查找  
        for (int i = level; i >= 0; i--) {  
            while (current.forward[i] != null && current.forward[i].value < target) {  
                current = current.forward[i];  // 前进到下一节点  
            }  
        }  
        current = current.forward[0];  // 到达第0层  
        return current != null && current.value == target;  
    }  
  
    // 插入元素  
    public void insert(int value) {  
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];  
        SkipListNode current = head;  
  
        // 查找插入位置  
        for (int i = level; i >= 0; i--) {  
            while (current.forward[i] != null && current.forward[i].value < value) {  
                current = current.forward[i];  
            }  
            update[i] = current;  // 记录每一层的前驱节点  
        }  
  
        // 随机生成一个层数  
        int newLevel = randomLevel();  
  
        // 如果新生成的层数比当前跳表层数大，需要更新头节点的forward  
        if (newLevel > level) {  
            for (int i = level + 1; i <= newLevel; i++) {  
                update[i] = head;  
            }  
            level = newLevel;  // 更新当前跳表的层数  
        }  
  
        // 创建新节点并插入到每一层  
        SkipListNode newNode = new SkipListNode(value, newLevel);  
        for (int i = 0; i <= newLevel; i++) {  
            newNode.forward[i] = update[i].forward[i];  
            update[i].forward[i] = newNode;  
        }  
    }  
  
    // 删除元素  
    public boolean delete(int value) {  
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];  
        SkipListNode current = head;  
  
        // 查找待删除节点的前驱节点  
        for (int i = level; i >= 0; i--) {  
            while (current.forward[i] != null && current.forward[i].value < value) {  
                current = current.forward[i];  
            }  
            update[i] = current;  
        }  
  
        current = current.forward[0];  
  
        // 如果目标节点存在  
        if (current != null && current.value == value) {  
            // 删除该节点在每一层的前驱指针  
            for (int i = 0; i <= level; i++) {  
                if (update[i].forward[i] != current) {  
                    break;  
                }  
                update[i].forward[i] = current.forward[i];  
            }  
  
            // 如果删除后导致某些层没有节点，减少跳表层数  
            while (level > 0 && head.forward[level] == null) {  
                level--;  
            }  
            return true;  
        }  
        return false;  
    }  
  
    // 打印跳表  
    public void printList() {  
        for (int i = level; i >= 0; i--) {  
            SkipListNode node = head.forward[i];  
            System.out.print("Level " + i + ": ");  
            while (node != null) {  
                System.out.print(node.value + " ");  
                node = node.forward[i];  
            }  
            System.out.println();  
        }  
    }  
  
    // 主方法用于测试  
    public static void main(String[] args) {  
        SkipList skipList = new SkipList();  
  
        skipList.insert(1);  
        skipList.insert(2);  
        skipList.insert(3);  
        skipList.insert(4);  
        skipList.insert(5);  
        skipList.insert(6);  
  
  
        System.out.println("跳表内容:");  
        skipList.printList();  
  
        System.out.println("\n查找3: " + skipList.search(3)); // true  
        System.out.println("查找7: " + skipList.search(7));   // false  
  
        skipList.delete(3);  
        System.out.println("\n删除3后跳表内容:");  
        skipList.printList();  
    }  
}

选择哪种实现方式？

1. 查询为主的场景：

如果你的跳表主要用于 查询操作，并且插入和删除的频率相对较低，数组实现会是一个更好的选择。因为它能够通过索引直接访问节点，具备更好的缓存性能。

适用场景：

  • 频繁查询但插入和删除较少，如缓存系统、搜索引擎索引。
  • 数据结构比较稳定，大量操作集中在读取和查询上。

2. 插入/删除频繁的场景：

如果你的应用场景需要 频繁插入和删除操作，那么链表实现的跳表会更加合适。链表的动态性和灵活性能够有效地减少插入和删除时的开销。

适用场景：

  • 数据集动态变化频繁，插入、删除操作较多的系统。
  • 数据规模较大，且插入和删除操作要求更高的实时性。

3. 内存敏感的场景：

如果你的场景对内存占用非常敏感，链表实现也会更加节省空间，避免了数组实现中预分配导致的浪费。

如何提高平衡性：

由于跳表的层级分布依赖于随机数生成，如果希望使跳表更平衡，可以尝试以下方式：

  1. 调试随机层数的生成概率：目前的实现中，randomLevel() 方法通过 50% 概率递增层级。可以调小递增概率，使得每层的节点更为稀疏，从而增大高层的跨度。但这样做也可能导致部分操作效率下降。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    private int randomLevel() {
        int lvl = 0;
        while (lvl < MAX_LEVEL && random.nextInt(4) == 1) {  
        // 调整为1/4的概率递增层数
            lvl++;
        }
        return lvl;
    }

  2. 增加插入数据的规模：跳表的平衡性与插入数据的规模有关。插入更多数据时，随机化的效果会更加明显，从而更容易产生更好的平衡性。

  3. 手动调整层数：为了保证更好的性能，可以手动控制某些关键节点的层数，使得每层都能有较好的索引分布，但这会破坏跳表的随机化本质。

使用场景

跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。跳表的空间复杂度是 O(n)。

散列表

介绍

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

image.png

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列表两个核心问题是散列函数设计和散列冲突解决。散列冲突有两种常用的解决方法，开放寻址法和链表法。散列函数设计的好坏决定了散列冲突的概率，也就决定散列表的性能。

散列函数

三点散列函数**设计的**基本要求：

  1. 散列函数计算得到的散列值是一个非负整数；

  2. 如果 key1 = key2，那 hash(key1) == hash(key2)；

  3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

散列冲突

再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢？我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。

开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？我先讲一个比较简单的探测方法，线性探测
image.png

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。我们来看这个图，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
image.png

HashMap工业级的散列表分析

1. 初始大小

HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。

2. 装载因子和动态扩容

最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

3. 散列冲突解决方法

HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能。

于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

4. 散列函数

1
2
3
4
int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
}

哈希算法

介绍

哈希算法历史悠久，业界著名的哈希算法也有很多，比如 MD5、SHA 等。在我们平时的开发中，基本上都是拿现成的直接用。
哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。
设计一个优秀的哈希算法需要满足的几点要求：

  • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；

  • 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；

  • 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；

  • 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

应用

安全加密

说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。

唯一标识

我先来举一个例子。如果要在海量的图库中，搜索一张图是否存在。我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识。

数据校验

电驴这样的 BT 下载软件你肯定用过吧？我们知道，BT 下载的原理是基于 P2P 协议的。我们从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分割成很多文件块（比如可以分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。

我们通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

散列函数

散列函数也是哈希算法的一种应用。

负载均衡

我们知道，负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。

我们可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。 这样，我们就可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。

数据分片

假如我们有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？

我们来分析一下。这个问题有两个难点，第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。

针对这两个难点，我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的：为了提高处理的速度，我们用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。

这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

实际上，这里的处理过程也是 MapReduce 的基本设计思想。

分布式存储

现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。我们有海量的数据需要缓存，所以一个缓存机器肯定是不够的。于是，我们就需要将数据分布在多台机器上。

该如何决定将哪个数据放到哪个机器上呢？我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
但是，如果数据增多，原来的 10 个机器已经无法承受了，我们就需要扩容了，比如扩到 11 个机器，这时候麻烦就来了。因为，这里并不是简单地加个机器就可以了。
所有的数据都要重新计算哈希值，然后重新搬移到正确的机器上。这样就相当于，缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。

一致性哈希算法，使得在新加入一个机器后，并不需要做大量的数据搬移。
假设我们有 k 个机器，数据的哈希值的范围是 [0, MAX]。我们将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

具体实现详见[[一致性hash算法]]

二叉树

介绍

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
image.png

image.png

其中，编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

二叉树可以基于数组，也可以基于链表。基于指针或者引用的二叉链式存储法，基于数组的顺序存储法。

二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。堆其实就是一种完全二叉树，最常用的存储方式就是数组。

二叉树的遍历

  • 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

  • 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

  • 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
    image.png

二叉树遍历的时间复杂度是 O(n)

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 节点
}

二叉查找树（Binary Search Tree）

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

特点

二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。
中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。
平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。

代码演示

查找
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class BinarySearchTree {
  private Node tree;
 
  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }
 
  public static class Node {
    private int data;
    private Node left;
    private Node right;
 
    public Node(int data) {
      this.data = data;
    }
  }
}

插入
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }
 
  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

删除
二叉查找树的查找、插入操作都比较简单易懂，但是它的删除操作就比较复杂了 。针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。

第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。

第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public void delete(int data) {
  Node p = tree; // p 指向要删除的节点，初始化指向根节点
  Node pp = null; // pp 记录的是 p 的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到
 
  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP 表示 minP 的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将 minP 的数据替换到 p 中
    p = minP; // 下面就变成了删除 minP 了
    pp = minPP;
  }
 
  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p 的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;
 
  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

应用

在一些分布式系统中，一致性哈希（Consistent Hashing）常常使用二叉搜索树来管理节点和数据的映射关系，尤其是在负载均衡、分布式缓存、分布式数据库等系统中。

  • 应用：二叉搜索树可以帮助在节点数变化时（如节点加入或退出）高效地重新分配数据，确保负载均衡并减少数据迁移。

红黑树

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
image.png

发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。

所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。它的出镜率甚至要高于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树，我前面说了，它的定义是不严格符合平衡二叉查找树的定义的。

顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

  • 根节点是黑色的；

  • 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

我们在上一节讲过，二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。

AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。

红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。

所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

一棵合格的红黑树需要满足这样几个要求：

  • 根节点是黑色的；

  • 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

在插入、删除节点的过程中，第三、第四点要求可能会被破坏，而我们今天要讲的“平衡调整”，实际上就是要把被破坏的第三、第四点恢复过来。

在正式开始之前，我先介绍两个非常重要的操作，左旋（rotate left）、右旋（rotate right）。左旋全称其实是叫围绕某个节点的左旋，那右旋的全称估计你已经猜到了，就叫围绕某个节点的右旋。

堆

介绍

只要满足这两点，它就是一个堆。

  • 堆是一个完全二叉树；

  • 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。
image.png
其中第 1个和第 2 个是大顶堆，第 3 个是小顶堆，第 4个不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。

插入一个数据的时候，我们把新插入的数据放到数组的最后，然后从下往上堆化；删除堆顶数据的时候，我们把数组中的最后一个元素放到堆顶，然后从上往下堆化。这两个操作时间复杂度都是 O(logn)。

代码演示

插入，从下而上堆化
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Heap {
  private int[] a; // 数组，从下标 1 开始存储数据
  private int n;  // 堆可以存储的最大数据个数
  private int count; // 堆中已经存储的数据个数
 
  public Heap(int capacity) {
    a = new int[capacity + 1];
    n = capacity;
    count = 0;
  }
 
  public void insert(int data) {
    if (count >= n) return; // 堆满了
    ++count;
    a[count] = data;
    int i = count;
    while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
      swap(a, i, i/2); // swap() 函数作用：交换下标为 i 和 i/2 的两个元素
      i = i/2;
    }
  }
 }

删除，从上而下堆化
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void removeMax() {
  if (count == 0) return -1; // 堆中没有数据
  a[1] = a[count];
  --count;
  heapify(a, count, 1);
}
 
private void heapify(int[] a, int n, int i) { // 自上往下堆化
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

特性

堆排序是一种原地的、时间复杂度为 O(nlogn)的排序算法。
大顶堆，堆顶为最大值；小顶堆，堆顶为最小值

应用

优先级队列-合并有序小文件

在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。
实现一个优先级队列，用堆来实现是最直接、最高效的。这是因为，堆和优先级队列非常相似。一个堆就可以看作一个优先级队列。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。
很多语言中，都提供了优先级队列的实现，比如，Java 的 PriorityQueue，C++ 的 priority_queue 等。

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。

整体思路有点像归并排序中的合并函数。我们从这 100 个文件中，各取第一个字符串，放入数组中，然后比较大小，把最小的那个字符串放入合并后的大文件中，并从数组中删除。

假设，这个最小的字符串来自于 13.txt 这个小文件，我们就再从这个小文件取下一个字符串，并且放到数组中，重新比较大小，并且选择最小的放入合并后的大文件，并且将它从数组中删除。依次类推，直到所有的文件中的数据都放入到大文件为止。

这里我们用数组这种数据结构，来存储从小文件中取出来的字符串。每次从数组中取最小字符串，都需要循环遍历整个数组，显然，这不是很高效。有没有更加高效方法呢？

这里就可以用到优先级队列，也可以说是堆。我们将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。

我们知道，删除堆顶数据和往堆中插入数据的时间复杂度都是 O(logn)，n 表示堆中的数据个数，这里就是 100。是不是比原来数组存储的方式高效了很多呢？

堆求 Top K

动态维护topk，不用存储所有的数据，减少内存的占用。
我们可以一直都维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以里立刻返回给他。

堆求中位数（99% 响应时间）

对于一组静态数据，中位数是固定的，我们可以先排序，第 n/2个数据就是中位数。每次询问中位数的时候，我们直接返回这个固定的值就好了。所以，尽管排序的代价比较大，但是边际成本会很小。但是，如果我们面对的是动态数据集合，中位数在不停地变动，如果再用先排序的方法，每次询问中位数的时候，都要先进行排序，那效率就不高了。

借助堆这种数据结构，我们不用排序，就可以非常高效地实现求中位数操作。
我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

也就是说，如果有 n 个数据，n 是偶数，我们从小到大排序，那前 n/2 个数据存储在大顶堆中，后 n/2 个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 n/2+1 个数据，小顶堆中就存储 n/2个数据。

图

树中的元素我们称为节点，图中的元素我们就叫作顶点（vertex）。一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫作边（edge）。

微信的好友关系就可以用一张图来表示。其中，每个用户有多少个好友，对应到图中，就叫作顶点的度（degree），就是跟顶点相连接的边的条数。

微博允许单向关注，如果用户 A 关注了用户 B，我们就在图中画一条从 A 到 B 的带箭头的边，来表示边的方向。如果用户 A 和用户 B 互相关注了，那我们就画一条从 A 指向 B 的边，再画一条从 B 指向 A 的边。我们把这种边有方向的图叫作“有向图”。以此类推，我们把边没有方向的图就叫作“无向图”。
无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。
顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。对应到微博的例子，入度就表示有多少粉丝，出度就表示关注了多少人。

QQ 亲密度功能， 不仅记录了用户之间的好友关系，还记录了两个用户之间的亲密度，如果两个用户经常往来，那亲密度就比较高；如果不经常往来，亲密度就比较低。这里就要用到另一种图，带权图（weighted graph）。在带权图中，每条边都有一个权重（weight），我们可以通过这个权重来表示 QQ 好友间的亲密度。

图存储

邻接矩阵存储方法

邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j] 和 A[j][i] 标记为 1；对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i][j] 标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i] 标记为 1。对于带权图，数组中就存储相应的权重。
image.png

邻接表存储方法

每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。
image.png

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Graph {
  private int v; // 顶点的个数
  private LinkedList<Integer> adj[]; // 邻接表
 
  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) {
      adj[i] = new LinkedList<>();
    }
  }
 
  public void addEdge(int s, int t) { // s 先于 t，边 s->t
    adj[s].add(t);
  }
}

如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，我们可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。但是如果像微博那样有上亿的用户，数据规模太大，我们就无法全部存储在内存中了。这个时候该怎么办呢？

我们可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。你可以看下面这幅图，我们在机器 1 上存储顶点 1，2，3 的邻接表，在机器 2 上，存储顶点 4，5 的邻接表。逆邻接表的处理方式也一样。当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。

image.png

深度和广度优先搜索

介绍

广度优先搜索（Breadth-First-Search），我们平常都把简称为 BFS。直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
 * 104. 二叉树的最大深度
 * <p>
 * 给定一个二叉树，找出其最大深度。
 * <p>
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class TreeNode5 {

    public static void main(String[] args) {
        //头插法
        TreeNode node13 = new TreeNode(13, null, null);
        TreeNode node14 = new TreeNode(14, node13, null);
        TreeNode node15 = new TreeNode(15, null, null);
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node20 = new TreeNode(20, node15, node7);
        TreeNode node9 = new TreeNode(9, node14, null);
        TreeNode node3 = new TreeNode(3, node9, node20);
        System.out.println("maxDepth(node3) = " + maxDepth(node3));
    }
    //BFS 迭代 耗时大
    /*public static int maxDepth(TreeNode root) {
        //LinkedList<LinkedList<Integer>> lists = new LinkedList<>();
        int depth=0;
        if(root==null)return depth;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //LinkedList<Integer> list = new LinkedList<>();
            int n = queue.size();//每一层的元素个数
            //遍历一层的节点，添加到列表，并添加子节点到队列中
            for (int i = 0; i < n; i++) {
                TreeNode poll = queue.poll();
                //list.add(poll.val);
                if(poll.left!=null)queue.offer(poll.left);
                if(poll.right!=null)queue.offer(poll.right);
            }
            //lists.add(list);
            depth++;
        }
        //return lists.size();
        return depth;
    }*/

    //DFS 后序
    /*public static int maxDepth(TreeNode root) {
        int depth = 0;
        if (root == null) return depth;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {//递过程 、归过程条件
            while (root != null) {//入栈，先遍历左子树
                stack.push(root);
                root = root.left;
            }
            //没有左子树了，先不弹栈，要先判断是否有右子树，最后注意栈里剩下右子树的逆序弹栈，需要除去已经遍历过的，
            TreeNode peek = stack.peek();
            if (peek.right != null&&peek.right!=pre) {
                root = peek.right;
            } else {
                depth=Math.max(depth,stack.size());
                stack.pop();
                pre=peek;
            }
        }
        return depth;
    }*/

    //DFS 递归
    public static int maxDepth(TreeNode root) {
        if(root==null)return 0;
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return Math.max(left,right)+1;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

字符串匹配

单模式匹配

单模式串匹配的算法: BF 算法、RK 算法、BM 算法、KMP 算法。

单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。

BF 算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。

image.png

从上面的算法思想和例子，我们可以看出，在极端情况下，比如主串是“aaaaa…aaaaaa”（省略号表示有很多重复的字符 a），模式串是“aaaaab”。我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。

尽管理论上，BF 算法的时间复杂度很高，是 O(n*m)，但在实际的开发中，它却是一个比较常用的字符串匹配算法。

RK 算法（哈希检索算法）

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。

BF 算法每次检查主串与子串是否匹配，需要依次比对每个字符，所以 时间复杂度就比较高，是 O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。

这就需要哈希算法设计的非常有技巧了。我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。表述起来有点抽象，我举了一个例子，看完你应该就能懂了。

比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。

在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含 a 到 z 这 26 个字符的字符串，计算哈希的时候，我们只需要把进位从 10 改成 26 就可以。

image.png

整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们前面也分析了，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。

模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。

BM 算法（摩尔投票）

我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。
在这个例子里，主串中的 c，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 c 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 c 的后面。

image.png
BM 算法，本质上其实就是借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

BM 算法原理分析

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来看，这两个规则分别都是怎么工作的。

1.坏字符规则

前面两节讲的算法，在匹配的过程中，我们都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。

image.png

当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，我这里说的下标，都是字符在模式串的下标）。

不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。

2. 好后缀规则

好后缀规则实际上跟坏字符规则的思路很类似。你看我下面这幅图。当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。

我们把已经匹配的 bc 叫作好后缀，记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。

image.png

如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。

image.png

不过，当模式串中不存在等于{u}的子串时，我们直接将模式串滑动到主串{u}的后面。这样做是否有点太过头呢？我们来看下面这个例子。这里面 bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串{u*}，但是如果我们将模式串移动到好后缀的后面，如图所示，那就会错过模式串和主串可以匹配的情况。

image.png

所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。

我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免我们前面提到的，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix);
  int i = 0; // j 表示主串与模式串匹配的第一个字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    int x = j - bc[(int)a[i+j]];
    int y = 0;
    if (j < m-1) { // 如果有好后缀的话
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}
 
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后缀长度
  if (suffix[k] != -1) return j - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}

private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
  for (int i = 0; i < SIZE; ++i) {
    bc[i] = -1; // 初始化 bc
  }
  for (int i = 0; i < m; ++i) {
    int ascii = (int)b[i]; // 计算 b[i] 的 ASCII 值
    bc[ascii] = i;
  }
}

// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
  for (int i = 0; i < m; ++i) { // 初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (int i = 0; i < m - 1; ++i) { // b[0, i]
    int j = i;
    int k = 0; // 公共后缀子串长度
    while (j >= 0 && b[j] == b[m-1-k]) { // 与 b[0, m-1] 求公共后缀子串
      --j;
      ++k;
      suffix[k] = j+1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标
    }
    i
    if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串
  }
}

多模式匹配

多模式串匹配算法：Trie 树和 AC 自动机。

Trie树(字典树)

搜索引擎的搜索关键词提示功能，我想你应该不陌生吧？为了方便快速输入，当你在搜索引擎的搜索框中，输入要搜索的文字的某一部分的时候，搜索引擎就会自动弹出下拉框，里面是各种关键词提示。

像 Google、百度这样的搜索引擎，它们的关键词提示功能非常全面和精准，肯定做了很多优化，但万变不离其宗，底层最基本的原理就是今天要讲的这种数据结构：Trie 树。

Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。
image.png

根节点不包
含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

如果要在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度 和）。构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

经典的多模式串匹配算法：AC 自动机

很多支持用户发表文本内容的网站，比如 BBS，大都会有敏感词过滤功能，用来过滤掉用户输入的一些淫秽、反动、谩骂等内容。你有没有想过，这个功能是怎么实现的呢？

实际上，这些功能最基本的原理就是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容之后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。如果有，就用“***”把它替代掉。

我们前面讲过好几种字符串匹配算法了，它们都可以处理这个问题。但是，对于访问量巨大的网站来说，比如淘宝，用户每天的评论数有几亿、甚至几十亿。这时候，我们对敏感词过滤系统的性能要求就要很高。毕竟，我们也不想，用户输入内容之后，要等几秒才能发送出去吧？我们也不想，为了这个功能耗费过多的机器吧？那如何才能实现一个高性能的敏感词过滤系统呢？这就要用到今天的多模式串匹配算法。

AC 自动机算法，全称是 Aho-Corasick 算法。其实，Trie 树跟 AC 自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟 KMP 算法之间的关系一样，只不过前者针对的是多模式串而已。所以，AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。

AC 自动机的构建，包含两个操作：

  • 将多个模式串构建成 Trie 树；

  • 在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。

如果没有失败指针，那么我们只能回到根节点重新开始匹配，这样效率非常低。失败指针的作用就是在当前节点匹配失败时，能帮助我们找到一个更合适的节点继续尝试。
image.png
失败指针指向那个最长匹配后缀子串对应的模式串的前缀的最后一个节点

匹配的时间复杂度就是 O(nlen)。因为敏感词并不会很长，而且这个时间复杂度只是一个非常宽泛的上限，实际情况下，可能近似于 O(n)，所以 AC 自动机做敏感词过滤，性能非常高。

从时间复杂度上看，AC 自动机匹配的效率跟 Trie 树一样啊。实际上，因为失效指针可能大部分情况下都指向 root 节点，所以绝大部分情况下，在 AC 自动机上做匹配的效率要远高于刚刚计算出的比较宽泛的时间复杂度。只有在极端情况下，如图所示，AC 自动机的性能才会退化的跟 Trie 树一样。

image.png

贪心算法

针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。当我们看到这类问题的时候，首先要联想到贪心算法。

完全背包问题

在完全背包问题中，每个物品可以选择多个，前提是总重量不超过背包的容量。这个问题在动态规划中略有不同，因为在状态转移时会考虑每个物品可以选择多次的情况。

假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。 我们有以下 5 种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？
image.png

我们只要先算一算每个物品的单价，按照单价由高到低依次来装就好了。单价从高到低排列，依次是：黑豆、绿豆、红豆、青豆、黄豆，所以，我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。

实际上，用贪心算法求最优解，需满足贪心选择性 。通过局部最优的选择，能产生全局的最优选择。否则通过贪心算法得不到最优解。
在一个有权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。按照这种思路，我们求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。
image.png

但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径，因为这条路径的长度是 2+2+2=6。
在这个问题上，贪心算法不工作的主要原因是，前面的选择，会影响后面的选择。如果我们第一步从顶点 S 走到顶点 A，那接下来面对的顶点和边，跟第一步从顶点 S 走到顶点 B，是完全不同的。所以，即便我们第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

应用

0-1 背包问题

在0-1背包问题中，有一个容量固定的背包和若干物品。每个物品都有一定的重量和价值。目标是在不超过背包容量的前提下，选择若干物品装入背包，使得这些物品的总价值最大。每个物品只能选择放入背包或不放入背包，不能拆分。

通常使用动态规划（DP）算法来求解小规模问题，或者采用启发式算法、近似算法来处理大规模问题。

背包问题有广泛的实际应用，比如：

  • 资源分配：如何在有限资源下进行最优的资源分配。
  • 投资组合：选择一定数量的投资组合以获得最大回报。
  • 物流问题：在运输中，如何在空间或重量受限的情况下装载最大价值的货物。

总结来说，背包问题的核心是如何在有限容量（或资源）限制下，选择最优组合使得总收益或价值最大。

回溯算法

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

八皇后问题

我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。你可以看我画的图，第一幅图是满足条件的一种方法，第二幅图是不满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式。
image.png

我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前的方法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种方法，继续尝试。

0-1背包

我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
今天讲的这个背包问题，物品是不可分割的，要么装要么不装，所以叫 0-1 背包问题。显然，这个问题已经无法通过贪心算法来解决了。我们现在来看看，用回溯算法如何来解决。

对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2^n 种，去掉总重量超过 Wkg 的，从剩下的装法中选择总重量最接近 Wkg 的。不过，我们如何才能不重复地穷举出这 2^n 种装法呢？
我们假设背包的最大承载重量是 9。我们有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。如果我们把这个例子的回溯求解过程，用递归树画出来，就是下面这个样子：
image.png
递归树中的每个节点表示一种状态，我们用（i, cw）来表示。其中，i 表示将要决策第几个物品是否装入背包，cw 表示当前背包中物品的总重量。比如，（2，2）表示我们将要决策第 2 个物品是否装入背包，在决策前，背包中物品的总重量是 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
// cw 表示当前已经装进去的物品的重量和；i 表示考察到哪个物品了；
// w 背包重量；items 表示每个物品的重量；n 表示物品个数
// 假设背包可承受重量 100，物品个数 10，物品重量存储在数组 a 中，那可以这样调用函数：
// f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {
  if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已经考察完所有的物品
    if (cw > maxW) maxW = cw;
    return;
  }
  f(i+1, cw, items, n, w);
  if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
    f(i+1,cw + items[i], items, n, w);
  }
}

回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。

动态规划

介绍

回溯算法，有些子问题的求解是重复的，比如图中 f(2, 2) 和 f(3,4) 都被重复计算了两次。回溯算法把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。

我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量），也就是例子中的 9。于是，我们就成功避免了每层状态个数的指数级增长。

我们用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。

第 0 个（下标从 0 开始编号）物品的重量是 2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是 0 或者 2。我们用 states[0][0]=true 和 states[0][2]=true 来表示这两种状态。

第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用 states[1][0]=true，states[1][2]=true，states[1][4]=true 来表示这三种状态。

以此类推，直到考察完所有的物品后，整个 states 状态数组就都计算好了。我把整个计算的过程画了出来，你可以看看。图中 0 表示 false，1 表示 true。我们只需要在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
weight: 物品重量，n: 物品个数，w: 背包可承载重量
public int knapsack(int[] weight, int n, int w) {
  boolean[][] states = new boolean[n][w+1]; // 默认值 false
  states[0][0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
  states[0][weight[0]] = true;
  for (int i = 1; i < n; ++i) { // 动态规划状态转移
    for (int j = 0; j <= w; ++j) {// 不把第 i 个物品放入背包
      if (states[i-1][j] == true) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= w-weight[i]; ++j) {// 把第 i 个物品放入背包
      if (states[i-1][j]==true) states[i][j+weight[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[n-1][i] == true) return i;
  }
  return 0;
}

回溯算法解决这个问题的时间复杂度 O(2^n)，是指数级的。动态规划,耗时最多的部分就是代码中的两层 for 循环，所以时间复杂度是 O(n*w)。n 表示物品个数，w 表示背包可以承载的总重量。

尽管动态规划的执行效率比较高，但是就刚刚的代码实现来说，我们需要额外申请一个 n 乘以 w+1 的二维数组，对空间的消耗比较多。所以，有时候，我们会说，动态规划是一种空间换时间的解决思路。你可能要问了，有什么办法可以降低空间消耗吗？

实际上，我们只需要一个大小为 w+1 的一维数组就可以解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int knapsack2(int[] items, int n, int w) {
  boolean[] states = new boolean[w+1]; // 默认值 false
  states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
  states[items[0]] = true;
  for (int i = 1; i < n; ++i) { // 动态规划
    for (int j = w-items[i]; j >= 0; --j) {// 把第 i 个物品放入背包
	  //j 需要从大到小来处理。如果我们按照 j 从小到大处理的话，会出现 for 循环重复计算的问题
      if (states[j]==true) states[j+items[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[i] == true) return i;
  }
  return 0;
}

空间复杂度从 O(n*w) 降低为 O(w)

适合用动态规划解决的问题的特征

什么样的问题适合用动态规划来解决呢？换句话说，动态规划能解决的问题有什么规律可循呢？实际上，动态规划作为一个非常成熟的算法思想，很多人对此已经做了非常全面的总结。这部分理论总结为“一个模型三个特征”。
一个模型：多阶段决策最优解模型
三个特征：最优子结构、无后效性和重复子问题。

多阶段决策最优解模型

我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

重复子问题

如果在递归求解问题时，子问题的求解是重复的，且可以通过记忆化或递推的方法来避免冗余计算，那么该问题具有重叠子问题性质。这意味着很多子问题会被多次求解，而动态规划通过保存这些子问题的解，可以避免重复计算，提高效率。

动态规划解题思路

1. 状态转移表法

一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。所以，当我们拿到问题的时候，我们可以先用简单的回溯算法解决，找到重复子问题之后，接下来，我们有两种处理思路，第一种是直接用回溯加“备忘录”的方法，来避免重复子问题。从执行效率上来讲，这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法，状态转移表法。我们先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。使用状态表记录状态值，避免重复计算。

2. 状态转移方程法

状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。

假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
image.png

i 表示行，j 表示列
回溯算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private int minDist = Integer.MAX_VALUE; // 全局变量或者成员变量
// 调用方式：minDistBacktracing(0, 0, 0, w, n);
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
  // 到达了 n-1, n-1 这个位置了，这里看着有点奇怪哈，你自己举个例子看下
  if (i == n && j == n) {
    if (dist < minDist) minDist = dist;
    return;
  }
  if (i < n) { // 往下走，更新 i=i+1, j=j
    minDistBT(i + 1, j, dist+w[i][j], w, n);
  }
  if (j < n) { // 往右走，更新 i=i, j=j+1
    minDistBT(i, j+1, dist+w[i][j], w, n);
  }
}

状态转移表法
image.png
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int minDistDP(int[][] matrix, int n) {
  int[][] states = new int[n][n];
  int sum = 0;
  for (int j = 0; j < n; ++j) { // 初始化 states 的第一行数据
    sum += matrix[0][j];
    states[0][j] = sum;
  }
  sum = 0;
  for (int i = 0; i < n; ++i) { // 初始化 states 的第一列数据
    sum += matrix[i][0];
    states[i][0] = sum;
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < n; ++j) {
      states[i][j] = 
            matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
    }
  }
  return states[n-1][n-1];
}

状态方程转移法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int[][] matrix = 
         {{1，3，5，9}, {2，1，3，4}，{5，2，6，7}，{6，8，4，3}};
private int n = 4;
private int[][] mem = new int[4][4];
public int minDist(int i, int j) { // 调用 minDist(n-1, n-1);
  if (i == 0 && j == 0) return matrix[0][0];
  if (mem[i][j] > 0) return mem[i][j]; //避免重复计算
  int minLeft = Integer.MAX_VALUE;
  if (j-1 >= 0) {
    minLeft = minDist(i, j-1);
  }
  int minUp = Integer.MAX_VALUE;
  if (i-1 >= 0) {
    minUp = minDist(i-1, j);
  }
  
  int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
  mem[i][j] = currMinDist;
  return currMinDist;
}

四种算法思想，贪心、分治、回溯和动态规划，它们之间有什么区别和联系。

如果我们将这四种算法思想分一下类，那贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类，因为它跟其他三个都不大一样。为什么这么说呢？前三个算法解决问题的模型，都可以抽象成我们今天讲的那个多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

应用

淘宝的“双十一”购物节有各种促销活动，比如“满 200 元减 50 元”。假设你女朋友的购物车中有 n 个（n>100）想买的商品，她希望从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件（200 元），这样就可以极大限度地“薅羊毛”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// items 商品价格，n 商品个数, w 表示满减条件，比如 200
public static void double11advance(int[] items, int n, int w) {
  boolean[][] states = new boolean[n][3*w+1];// 超过 3 倍就没有薅羊毛的价值了
  states[0][0] = true;  // 第一行的数据要特殊处理
  states[0][items[0]] = true;
  for (int i = 1; i < n; ++i) { // 动态规划
    for (int j = 0; j <= 3*w; ++j) {// 不购买第 i 个商品
      if (states[i-1][j] == true) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= 3*w-items[i]; ++j) {// 购买第 i 个商品
      if (states[i-1][j]==true) states[i][j+items[i]] = true;
    }
  }
 
  int j;
  for (j = w; j < 3*w+1; ++j) { 
    if (states[n-1][j] == true) break; // 输出结果大于等于 w 的最小值
  }
  if (j == 3*w+1) return; // 没有可行解
  for (int i = n-1; i >= 1; --i) { // i 表示二维数组中的行，j 表示列
    if(j-items[i] >= 0 && states[i-1][j-items[i]] == true) {
      System.out.print(items[i] + " "); // 购买这个商品
      j = j - items[i];
    } // else 没有购买这个商品，j 不变。
  }
  if (j != 0) System.out.print(items[0]);
}

最长公共子序列（LCS）长度

如何量化两个字符串之间的相似程度呢？有一个非常著名的量化方法，那就是编辑距离（Edit Distance）。

顾名思义，编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

根据所包含的编辑操作种类的不同，编辑距离有多种不同的计算方式，比较著名的有莱文斯坦距离（Levenshtein distance）和最长公共子序列长度（Longest common substring length）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。

而且，莱文斯坦距离和最长公共子串长度，从两个截然相反的角度，分析字符串的相似程度。莱文斯坦距离的大小，表示两个字符串差异的大小；而最长公共子串的大小，表示两个字符串相似程度的大小。

关于这两个计算方法，我举个例子给你说明一下。这里面，两个字符串 mitcmu 和 mtacnu 的莱文斯坦距离是 3，最长公共子串长度是 4。

image.png

区分最长公共子序列和最长公共子串

  • 最长公共子序列（LCS）：两个字符串中最长的不要求连续的公共序列。
    • 例如，字符串 “abcde” 和 “ace” 的最长公共子序列是 “ace”。
  • 最长公共子串（LCSS）：两个字符串中最长的连续的公共子串。
    • 例如，字符串 “abcde” 和 “bcd” 的最长公共子串是 “bcd”。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lcs(char[] a, int n, char[] b, int m) {
	int[][] maxlcs = new int[n][m];
	for (int j = 0; j < m; ++j) {// 初始化第 0 行：a[0..0] 与 b[0..j] 的 maxlcs
		if (a[0] == b[j]) maxlcs[0][j] = 1;
		else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1];
		else maxlcs[0][j] = 0;
	}
	for (int i = 0; i < n; ++i) {// 初始化第 0 列：a[0..i] 与 b[0..0] 的 maxlcs
		if (a[i] == b[0]) maxlcs[i][0] = 1;
		else if (i != 0) maxlcs[i][0] = maxlcs[i-1][0];
		else maxlcs[i][0] = 0;
	}
	for (int i = 1; i < n; ++i) { // 填表
		for (int j = 1; j < m; ++j) {
			if (a[i] == b[j]) maxlcs[i][j] = maxlcs[i-1][j-1]+1;
			else maxlcs[i][j] = Math.max(
					maxlcs[i-1][j], maxlcs[i][j-1]);
		}
	}
	return maxlcs[n-1][m-1];
}

拓扑排序

拓扑排序本身就是基于有向无环图(DAG)的一个算法。一个有向无环图可以有一个或多个拓扑排序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Graph {
  private int v; // 顶点的个数
  private LinkedList<Integer> adj[]; // 邻接表
 
  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) {
      adj[i] = new LinkedList<>();
    }
  }
 
  public void addEdge(int s, int t) { // s 先于 t，边 s->t
    adj[s].add(t);
  }
}

拓扑排序有两种实现方法,分别是Kahn 算法和DFS 深度优先搜索算法,时间复杂度就是 O(V+E)（V 表示顶点个数，E 表示边的个数）。
注意，这里的图可能不是连通的，有可能是有好几个不连通的子图构成，所以，E 并不一定大于 V，两者的大小关系不确定。所以，在表示时间复杂度的时候，V、E 都要考虑在内。

Kahn 算法(BFS)

Kahn ，找出一个入度为 0 的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减 1）。我们循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void topoSortByKahn() {
  int[] inDegree = new int[v]; // 统计每个顶点的入度
  for (int i = 0; i < v; ++i) {
    for (int j = 0; j < adj[i].size(); ++j) {
      int w = adj[i].get(j); // i->w
      inDegree[w]++;
    }
  }
  LinkedList<Integer> queue = new LinkedList<>();
  for (int i = 0; i < v; ++i) {
    if (inDegree[i] == 0) queue.add(i);
  }
  while (!queue.isEmpty()) {
    int i = queue.remove();
    System.out.print("->" + i);
    for (int j = 0; j < adj[i].size(); ++j) {
      int k = adj[i].get(j);
      inDegree[k]--;
      if (inDegree[k] == 0) queue.add(k);//拿到新的入度点
    }
  }
}

DFS 算法

画出递归树
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Graph {  
    private int V;   // 图中顶点的数量  
    private LinkedList<Integer> adj[]; // 邻接表  
  
    // 构造函数，初始化图  
    Graph(int v) {  
        V = v;  
        adj = new LinkedList[v];  
        for (int i = 0; i < v; ++i)  
            adj[i] = new LinkedList<>();  
    }  
  
    // 向图中添加边  
    void addEdge(int v, int w) {  
        adj[v].add(w);  
    }  
  
    // 辅助函数：递归进行DFS并完成拓扑排序  
    private void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {  
        // 将当前节点标记为已访问  
        visited[v] = true;  
  
        // 递归访问所有邻接节点  
        for (Integer neighbor : adj[v]) {  
            if (!visited[neighbor]){  
                topologicalSortUtil(neighbor, visited, stack);  
            }  
  
        }  
        // 当前节点的所有邻居都访问完了，加入栈中  
        stack.push(v);  
    }  
  
    // 主函数：执行拓扑排序  
    void topologicalSort() {  
        Stack<Integer> stack = new Stack<>();  
  
        // 初始化所有节点未访问  
        boolean[] visited = new boolean[V];  
  
        // 对每个未被访问的节点执行DFS  
        for (int i = 0; i < V; i++) {  
            if (!visited[i]) {  
                System.out.println("i = " + i);  
                topologicalSortUtil(i, visited, stack);  
            }  
        }  
  
        // 打印栈中的拓扑排序结果（逆序）  
        while (!stack.isEmpty()) {  
            System.out.print(stack.pop() + " ");  
        }  
    }  
}  
  
// 使用示例  
public class Main {  
    public static void main(String args[]) {  
        // 创建图，包含6个顶点  
        Graph dag = new Graph(5);  
  
        // 添加边  
        dag.addEdge(0,1);  
        dag.addEdge(0,3);  
        dag.addEdge(1,2);  
        dag.addEdge(1,3);  
        dag.addEdge(2,4);  
        dag.addEdge(3,2);  
        dag.addEdge(3,4);  
  
        System.out.println("拓扑排序结果：");  
        dag.topologicalSort();  
    }  
}

最短路径

单源最短路径算法(Dijkstra迪杰斯特拉算法)

在一个有权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。按照这种思路，我们求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。
image.png

但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径，因为这条路径的长度是 2+2+2=6。
在这个问题上，贪心算法不工作的主要原因是，前面的选择，会影响后面的选择。如果我们第一步从顶点 S 走到顶点 A，那接下来面对的顶点和边，跟第一步从顶点 S 走到顶点 B，是完全不同的。所以，即便我们第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

Dijkstra 算法：虽然使用贪心策略，但它每次选择当前已知的最短路径，并且在选择时会更新并保存每个节点的最短路径值，排除不必要的路径，这大大提高了检索效率。。这使得 Dijkstra 算法可以在局部做出选择的同时，保证最终得到全局最优解。

Dijkstra 算法过程

1. 初始化

  • 起点 S 的初始距离为 0。
  • 其他所有节点的初始距离为无穷大（∞），因为还未找到通往这些节点的路径。
节点 距离
S 0
A ∞
B ∞
E ∞
D ∞
T ∞

2. 第一步：从 S 开始

  • S 是起点，当前路径长度为 0。
  • 从 S 出发有两条边可供选择：
    • S -> A，距离是 1。
    • S -> B，距离是 2。

由于 Dijkstra 算法采用贪心策略，优先选择距离最短的节点，因此首先选择距离更短的 S -> A。

更新节点 A 的距离为 1，节点 B 的距离为 2（同时也更新）。

节点 距离
S 0
A 1
B 2
E ∞
D ∞
T ∞

3. 第二步：选择距离最短的节点 A

  • 当前距离最短的节点是 A（距离为 1）。
  • 从 A 出发有一条边 A -> E，边的权重是 4。
    • 因此，路径 S -> A -> E 的距离是 (1 + 4 = 5)。

更新节点 E 的距离为 5。

节点 距离
S 0
A 1
B 2
E 5
D ∞
T ∞

4. 第三步：选择距离最短的节点 B

  • 当前距离最短的节点是 B（距离为 2）。
  • 从 B 出发有一条边 B -> D，边的权重是 2。
    • 因此，路径 S -> B -> D 的距离是 (2 + 2 = 4)。

更新节点 D 的距离为 4。

节点 距离
S 0
A 1
B 2
E 5
D 4
T ∞

5. 第四步：选择距离最短的节点 D

  • 当前距离最短的节点是 D（距离为 4）。
  • 从 D 出发有一条边 D -> T，边的权重是 2。
    • 因此，路径 S -> B -> D -> T 的距离是 (4 + 2 = 6)。

更新终点 T 的距离为 6。

节点 距离
S 0
A 1
B 2
E 5
D 4
T 6

6. 第五步：选择距离最短的节点 E

  • 当前节点 E（距离为 5）是下一个距离最短的节点。
  • 从 E 出发有一条边 E -> T，边的权重是 4。
    • 因此，路径 S -> A -> E -> T 的距离是 (5 + 4 = 9)。

然而，T 当前的最短路径距离已经是 6，比这条路径的 9 要小，因此 T 的距离不会被更新。

节点 距离
S 0
A 1
B 2
E 5
D 4
T 6

Dijkstra 算法如何通过选择性搜索来避免暴力搜索？

  • 局部选择最短路径：Dijkstra算法每一步都选择当前最短的路径节点进行处理，而不是盲目穷举所有路径。刚开始时，它优先选择从 S -> A 走，因为这是当前最短的路径，随后继续探索其他未处理的节点，如 B 和 D。

  • 最短路径更新：每当找到一个节点的新路径时，Dijkstra算法会更新该节点的最短路径估计值。在这个例子中，虽然我们在早期发现了 S -> A -> E -> T 这一路径，但因为 S -> B -> D -> T 更短，算法会优先使用后者，并跳过不必要的计算。这种动态更新最短路径的机制避免了暴力枚举。

  • 避免无效路径的搜索：当 Dijkstra算法发现更短的路径时，它会停止继续延伸某些路径。例如，虽然从 S -> A -> E -> T 的路径也通向终点 T，但由于 S -> B -> D -> T 是当前最优的，算法会优先处理该路径并最终输出它为最短路径。这意味着路径 S -> A -> E -> T 没有必要继续搜索。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Dijkstra {

    // 定义表示图中边的类
    static class Edge {
        int targetNode; // 目标节点
        int weight; // 边的权重

        Edge(int targetNode, int weight) {
            this.targetNode = targetNode;
            this.weight = weight;
        }
    }

    // Dijkstra算法：找到从源节点到其他所有节点的最短路径
    public static int[] dijkstra(List<List<Edge>> graph, int source) {
        // 节点数量
        int nodeCount = graph.size();

        // 存储从源节点到每个节点的最短距离
        int[] distances = new int[nodeCount];
        // 初始化所有节点的最短距离为无穷大，源节点距离为0
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;

        // 优先队列，存储节点及其当前的距离，按照距离升序排列
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(pair -> pair[1]));
        // 将源节点添加到优先队列
        priorityQueue.add(new int[]{source, 0});

        // 处理节点，直到优先队列为空
        while (!priorityQueue.isEmpty()) {
            // 取出距离最小的节点
            int[] current = priorityQueue.poll();
            int currentNode = current[0];
            int currentDistance = current[1];

            // 如果当前距离已经大于已知的最短距离，则跳过（避免重复计算）
            if (currentDistance > distances[currentNode]) {
                continue;
            }

            // 遍历当前节点的所有相邻节点
            for (Edge edge : graph.get(currentNode)) {
                int neighbor = edge.targetNode;
                int weight = edge.weight;

                // 计算从源节点到相邻节点的新距离
                int newDistance = currentDistance + weight;

                // 如果新距离小于已知的最短距离，则更新最短距离
                if (newDistance < distances[neighbor]) {
                    distances[neighbor] = newDistance;
                    // 将相邻节点及其新距离加入优先队列
                    priorityQueue.add(new int[]{neighbor, newDistance});
                }
            }
        }

        return distances; // 返回从源节点到每个节点的最短距离
    }

    // 主函数，用于测试Dijkstra算法
    public static void main(String[] args) {
        // 图的定义，使用邻接表表示
        int n = 6; // 节点数

        // 每个节点的相邻节点及边的权重
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 添加边，格式为：源节点 -> 目标节点，权重
        graph.get(0).add(new Edge(1, 1)); // S -> A, 权重 1
        graph.get(0).add(new Edge(2, 2)); // S -> B, 权重 2
        graph.get(1).add(new Edge(3, 4)); // A -> E, 权重 4
        graph.get(2).add(new Edge(4, 2)); // B -> D, 权重 2
        graph.get(4).add(new Edge(5, 2)); // D -> T, 权重 2
        graph.get(3).add(new Edge(5, 4)); // E -> T, 权重 4

        // 执行Dijkstra算法，源节点为0（即S）
        int[] distances = dijkstra(graph, 0);

        // 输出结果：从源节点S到每个节点的最短距离
        System.out.println("Node\tDistance from Source");
        for (int i = 0; i < distances.length; i++) {
            System.out.println(i + "\t\t" + distances[i]);
        }
    }
}

A搜索算法

像出行路线规划、游戏寻路，这些真实软件开发中的问题，一般情况下，我们都不需要非得求最优解（也就是最短路径 -Dijkstra 最短路径算法）。在权衡路线规划质量和执行效率的情况下，我们只需要寻求一个次优解就足够了。那如何快速找出一条接近于最短路线的次优路线呢？

image.png

在 Dijkstra 算法的实现思路中，我们用一个优先级队列，来记录已经遍历到的顶点以及这个顶点与起点的路径长度。顶点与起点路径长度越小，就越先被从优先级队列中取出来扩展，从图中举的例子可以看出，尽管我们找的是从 s 到 t 的路线，但是最先被搜索到的顶点依次是 1，2，3。通过肉眼来观察，这个搜索方向跟我们期望的路线方向（s 到 t 是从西向东）是反着的，路线搜索的方向明显“跑偏”了。

之所以会“跑偏”，那是因为我们是按照顶点与起点的路径长度的大小，来安排出队列顺序的。与起点越近的顶点，就会越早出队列。我们并没有考虑到这个顶点到终点的距离，但是，从这个长度，我们是未知的。可以用其他估计值（曼哈顿距离）来代替。

顶点与起点之间的路径长度 g(i)
顶点跟终点之间的直线距离即曼哈顿距离h(i)
顶点到终点的路径长度估计值 f(i)

原来只是单纯地通过顶点与起点之间的路径长度 g(i)，来判断谁先出队列，现在有了顶点到终点的路径长度估计值，我们通过两者之和 f(i)=g(i)+h(i)，来判断哪个顶点该最先出队列。综合两部分，我们就能有效避免刚刚讲的“跑偏”。这里 f(i) 的专业叫法是估价函数（evaluation function）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 public static int[] aStar(List<List<Edge>> graph, int source, int target, int[] heuristic) {
    // 节点数量
    int nodeCount = graph.size();

    // 存储从源节点到每个节点的最短距离
    int[] distances = new int[nodeCount];
    // 初始化所有节点的最短距离为无穷大，源节点距离为0
    Arrays.fill(distances, Integer.MAX_VALUE);
    distances[source] = 0;

    // 优先队列，存储节点及其当前的估计距离（g(n) + h(n)），按照总估计距离升序排列
    PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(pair -> pair[1]));
    // 将源节点添加到优先队列，初始估计距离为启发式值h(source)
    priorityQueue.add(new int[]{source, heuristic[source]});

    // 处理节点，直到优先队列为空
    while (!priorityQueue.isEmpty()) {
        // 取出估计距离最小的节点
        int[] current = priorityQueue.poll();
        int currentNode = current[0];
        int currentDistance = distances[currentNode];

        // 如果当前节点是目标节点，直接返回
        if (currentNode == target) {
            return distances;
        }

        // 遍历当前节点的所有相邻节点
        for (Edge edge : graph.get(currentNode)) {
            int neighbor = edge.targetNode;
            int weight = edge.weight;

            // 计算从源节点到相邻节点的新距离g(n)
            int newDistance = currentDistance + weight;

            // 如果新距离小于已知的最短距离，则更新最短距离
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                // 估计从相邻节点到目标节点的距离h(neighbor)
                int estimatedDistance = newDistance + heuristic[neighbor];
                // 将相邻节点及其估计距离加入优先队列
                priorityQueue.add(new int[]{neighbor, estimatedDistance});
            }
        }
    }

    return distances; // 返回从源节点到每个节点的最短距离（或目标节点）
}

A* 算法是对 Dijkstra 算法的优化和改造。A* 算法利用贪心算法的思路，利用估价函数，每次都找 f 值（加入曼哈顿距离）最小的顶点出队列，一旦搜索到终点就不在继续考察其他顶点和路线了。所以，它并没有考察所有的路线，也就不可能找出最短路径了。

位图BitMap-布隆过滤器

假设一个 URL 的平均长度是 64 字节，那单纯存储这 10 亿个 URL，需要大约 60GB 的内存空间。因为散列表必须维持较小的装载因子，才能保证不会出现过多的散列冲突，导致操作的性能下降。而且，用链表法解决冲突的散列表，还会存储链表指针。所以，如果将这 10 亿个 URL 构建成散列表，那需要的内存空间会远大于 60GB，有可能会超过 100GB。

当然，对于一个大型的搜索引擎来说，即便是 100GB 的内存要求，其实也不算太高，我们可以采用分治的思想，用多台机器（比如 20 台内存是 8GB 的机器）来存储这 10 亿网页链接。这种分治的处理思路，我们讲过很多次了，这里就不详细说了。

对于爬虫的 URL 去重这个问题，刚刚讲到的分治加散列表的思路，已经是可以实实在在工作的了。不过，作为一个有追求的工程师，我们应该考虑，在添加、查询数据的效率以及内存消耗方面，我们是否还有进一步的优化空间呢？

bitmap位图

在 Java 中，int 占 4 字节，1 字节 = 8位（1 byte = 8 bit），如果我们用这个 32 个 bit 位的每一位的值来表示一个数的话是不是就可以表示 32 个数字，也就是说 32 个数字只需要一个 int 所占的空间大小就可以了，那就可以缩小空间 32 倍。

1 Byte = 8 Bit，1 KB = 1024 Byte，1 MB = 1024 KB，1GB = 1024 MB

举个例子：假设网站每天独立访问的用户有 1 千万，如果每天用集合类型和 BitMap 分别存储活跃用户：

集合类型：假如用户 id 是 int 型，4 字节，32 位，则集合类型占据的空间为 40M；

BitMap：.如果按位存储，1千万个数就是 1 千万位，占据的空间为 1.25M。

布隆过滤器

本质上布隆过滤器是一种基于位图的概率型数据结构，判断一个元素是否在集合中。布隆过滤器适用于需要判断是否存在但允许一定误判的场景，如网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等。

当一个元素加入布隆过滤器中的时候，会进行如下操作：
使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。 根据得到的哈希值，在位数组中把对应下标的值置为 1。

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：
对给定元素再次进行相同的哈希计算；
得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中(注意：由于hash冲突问题，所谓的存在只能是可能存在)，如果存在一个值不为 1，说明该元素不在布隆过滤器中。
image.png

在Java中可以通过一些第三方库，如 Google 的 Guava 或者 Redis 的布隆过滤器来实现布隆过滤器。下面介绍如何使用 Guava 库来实现布隆过滤器。

1
2
3
4
5
<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>31.0.1-jre</version> <!-- 确保版本号是最新的 -->
</dependency>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package com.example;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample {

    public static void main(String[] args) {
        // 创建一个布隆过滤器，期望插入 500 个整数，错误率为 1%
        BloomFilter<Integer> bloomFilter = BloomFilter.create(
                Funnels.integerFunnel(), // 使用 Integer 类型的 funnel
                500, // 期望插入的元素数量
                0.01 // 错误率 1%
        );

        // 向布隆过滤器中添加一些元素
        for (int i = 0; i < 500; i++) {
            bloomFilter.put(i);
        }

        // 判断元素是否存在
        System.out.println(bloomFilter.mightContain(100)); // true，100 已经被添加过
        System.out.println(bloomFilter.mightContain(1000)); // false，1000 没有被添加过

        // 验证假阳性概率
        int falsePositives = 0;
        int totalChecks = 10000;
        for (int i = 500; i < 10000; i++) {
            if (bloomFilter.mightContain(i)) {
                falsePositives++;
            }
        }
        System.out.println("falsePositives = " + falsePositives);
        System.out.println("假阳性率: " + (falsePositives / (double) totalChecks));
//        true
//        false
//        falsePositives = 107
//        假阳性率: 0.0107
    }
}

特点

1.布隆过滤器说某个元素存在，小概率会误判，不一定存在；

2.布隆过滤器说某个元素不在，那么这个元素一定不在；

3.布隆过滤器不支持删除。（不包含变种）

使用场景

布隆过滤器非常适合用于以下场景：

  • 大数据场景：当内存空间有限、且对误判率的容忍度较高时，布隆过滤器是很好的选择。
  • 缓存穿透：布隆过滤器可以用来预过滤查询，避免对数据库的频繁无效查询。

具体详见[[布隆过滤器和布谷鸟过滤器]]

朴素贝叶斯（Naive Bayes）算法

朴素贝叶斯（Naive Bayes）算法是一类简单但强大的概率分类算法，基于贝叶斯定理，广泛应用于文本分类、垃圾邮件检测、情感分析等任务。

贝叶斯定理描述了在已知某一事件发生后，如何根据新的证据来更新该事件发生的概率：

image.png

朴素的含义是指对条件独立性的假设，即假设所有特征之间是相互独立的，这使得算法大大简化了计算复杂度。

使用场景

朴素贝叶斯算法主要应用于以下几类问题：

  • 文本分类：用于垃圾邮件检测、新闻分类、情感分析等问题。由于文本特征（词语）可以看作独立的，该算法表现良好。
  • 文档过滤：在信息检索中对相关或不相关的文档进行分类。
  • 推荐系统：在某些应用场景中，可以结合贝叶斯概率模型，提供个性化推荐。
  • 医疗诊断：在一些简单的医疗问题中，通过患者的症状数据，可以预测疾病的类型。

朴素贝叶斯算法解决的问题

朴素贝叶斯算法解决的是分类问题，即给定一组特征，预测样本所属的类别。其特别适合多分类问题（multi-class classification）。例如：

  • 垃圾邮件检测：通过分析邮件的内容，计算邮件中不同词语出现的概率，来判断该邮件是否为垃圾邮件。
  • 情感分析：基于社交媒体的文本，分析用户对某些话题的情感倾向，如正面、负面或中性。

示例：垃圾邮件检测

假设我们有一个包含以下特征的邮件：{“免费”， “中奖”，“马上领取”}。我们已经对垃圾邮件和正常邮件中的词频做了统计：

  • 词“免费”出现在垃圾邮件的概率为0.7，正常邮件为0.1；
  • 词“中奖”出现在垃圾邮件的概率为0.6，正常邮件为0.05；
  • 词“马上领取”出现在垃圾邮件的概率为0.9，正常邮件为0.2。

根据这些统计结果，朴素贝叶斯可以计算该邮件为垃圾邮件的概率，给出最终的分类结果。

假设先验概率 P(垃圾邮件)=0.5 和P(正常邮件)=0.5
P(词汇特征∣垃圾邮件)=0.7×0.6×0.9=0.378
P(词汇特征∣正常邮件)=0.1×0.05×0.2=0.001

P(词汇特征)=P(词汇特征∣垃圾邮件)P(垃圾邮件)+P(词汇特征∣正常邮件)P(正常邮件)
P(词汇特征)=0.378×0.5+0.001×0.5=0.189+0.0005=0.1895

P(垃圾邮件∣词汇特征)=0.378×0.5/0.1895​=0.189/0.1895​≈0.997
邮件为垃圾邮件的概率约为 0.997，即 99.7%。

基础的推荐算法

基于相似用户做推荐

我们可以通过用户的行为，来定义这个喜爱程度。我们给每个行为定义一个得分，得分越高表示喜爱程度越高。
image.png
image.png

相似度度量，我们可以使用另外一个距离，那就是欧几里得距离（Euclidean distance）。欧几里得距离是用来计算两个向量之间的距离的。

image.png

image.png

我们把每个用户对所有歌曲的喜爱程度，都用一个向量表示。我们计算出两个向量之间的欧几里得距离，作为两个用户的口味相似程度的度量。从图中的计算可以看出，小明与你的欧几里得距离距离最小，也就是说，你俩在高维空间中靠得最近，所以，我们就断定，小明跟你的口味最相似。

基于相似物品做推荐

刚刚我们讲了基于相似用户的歌曲推荐方法，但是，如果用户是一个新用户，我们还没有收集到足够多的行为数据，这个时候该如何推荐呢？我们现在再来看另外一种推荐方法，基于相似歌曲的推荐方法，也就是说，如果某首歌曲跟你喜爱的歌曲相似，我们就把它推荐给你。
image.png

歌曲之间的相似度。欧几里得距离越小，表示两个歌曲越相似。然后，我们就在用户已经听过的歌曲中，找出他喜爱程度较高的歌曲。然后，我们找出跟这些歌曲相似度很高的其他歌曲，推荐给他。

B+树

介绍

假设要解决的问题，只包含这样两个常用的需求：

  • 根据某个值查找数据，比如 select * from user where id=1234；

  • 根据区间值来查找某些数据，比如 select * from user where id > 1234 and id < 2345。

除了这些功能性需求之外，在性能方面，我们希望查询数据的效率尽可能的高，不要消耗太多的内存空间。
散列表。散列表的查询性能很好，时间复杂度是 O(1)。但是，散列表不能支持按照区间快速查找数据。所以，散列表不能满足我们的需求。
平衡二叉查找树。尽管平衡二叉查找树查询的性能也很高，时间复杂度是 O(logn)。而且，对树进行中序遍历，我们还可以得到一个从小到大有序的数据序列，但这仍然不足以支持按照区间快速查找数据。
跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是 O(logn)。并且，跳表也支持按照区间快速地查找数据。我们只需要定位到区间起点值对应在链表中的结点，然后从这个结点开始，顺序遍历链表，直到区间终点对应的结点为止，这期间遍历得到的数据就是满足区间值的数据。
image.png
数据库索引所用到的数据结构 B+ 树跟跳表非常相似。不过，它是通过二叉查找树演化过来的。
树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。
image.png

数据库索引存储在硬盘中，而非内存中。（通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。）每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。所以减少磁盘 IO 操作，也就是，尽量降低树的高度。

如果我们把索引构建成 m 叉树，高度是不是比二叉树要小呢？如图所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他结点存储在磁盘中），如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100，那对一亿个数据构建索引，树的高度也只是 4，可以把第一层索引放在内存，这样只要 3 次磁盘 IO 就能获取到数据。磁盘 IO 变少了，查找数据的效率也就提高了。
image.png

image.png

对于相同个数的数据构建 m 叉树索引，m 叉树中的 m 越大，那树的高度就越小，那 m 叉树中的 m 是不是越大越好呢？到底多大才最合适呢？

不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconf PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。

尽管索引可以提高数据库的查询效率，但是，索引有利也有弊。在写入和删除数据的时候，为尽可能的读取页大小的内容，索引也会更新（分裂和合并），占用部分资源。

特点

  • 每个节点中子节点的个数不能超过 m，也不能小于 m/2；

  • 根节点的子节点个数可以不超过 m/2，这是一个例外；

  • m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；

  • 通过链表将叶子节点串联在一起，这样可以方便按区间查找；

  • 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。

B 树跟 B+ 树的不同点主要集中在这几个地方：

  • B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；

  • B 树中的叶子节点并不需要链表来串联。

索引的设计

构建索引常用的数据结构

实际上，常用来构建索引的数据结构，就是我们之前讲过的几种支持动态数据集合的数据结构。比如，散列表、红黑树、跳表、B+ 树。除此之外，位图、布隆过滤器可以作为辅助索引，有序数组可以用来对静态数据构建索引。

散列表增删改查操作的性能非常好，时间复杂度是 O(1)。一些键值数据库，比如 Redis、Memcache，就是使用散列表来构建索引的。这类索引，一般都构建在内存中。

红黑树作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是 O(logn)，也非常适合用来构建内存索引。Ext 文件系统中，对磁盘块的索引，用的就是红黑树。

B+ 树比起红黑树来说，更加适合构建存储在磁盘中的索引。B+ 树是一个多叉树，所以，对相同个数的数据构建索引，B+ 树的高度要低于红黑树。当借助索引查询数据的时候，读取 B+ 树索引，需要的磁盘 IO 次数非常更少。所以，大部分关系型数据库的索引，比如 MySQL、Oracle，都是用 B+ 树来实现的。

跳表也支持快速添加、删除、查找数据。而且，我们通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis 中的有序集合，就是用跳表来构建的。

布隆过滤器有一定的判错率。但是，我们可以规避它的短处，发挥它的长处。尽管对于判定存在的数据，有可能并不存在，但是对于判定不存在的数据，那肯定就不存在。而且，布隆过滤器还有一个更大的特点，那就是内存占用非常少。我们可以针对数据，构建一个布隆过滤器，并且存储在内存中。当要查询数据的时候，我们可以先通过布隆过滤器，判定是否存在。如果通过布隆过滤器判定数据不存在，那我们就没有必要读取磁盘中的索引了。对于数据不存在的情况，数据查询就更加快速了。

布隆过滤器有一定的判错率。但是，我们可以规避它的短处，发挥它的长处。尽管对于判定存在的数据，有可能并不存在，但是对于判定不存在的数据，那肯定就不存在。而且，布隆过滤器还有一个更大的特点，那就是内存占用非常少。我们可以针对数据，构建一个布隆过滤器，并且存储在内存中。当要查询数据的时候，我们可以先通过布隆过滤器，判定是否存在。如果通过布隆过滤器判定数据不存在，那我们就没有必要读取磁盘中的索引了。对于数据不存在的情况，数据查询就更加快速了。

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

对于索引设计需求，我们一般可以从功能性需求和非功能性需求两方面来分析

功能性需求

数据是格式化数据还是非格式化数据？要构建索引的原始数据，类型有很多。我把它分为两类，一类是结构化数据，比如，MySQL 中的数据；另一类是非结构化数据，比如搜索引擎中网页。对于非结构化数据，我们一般需要做预处理，提取出查询关键词，对关键词构建索引。

数据是静态数据还是动态数据？如果原始数据是一组静态数据，也就是说，不会有数据的增加、删除、更新操作，所以，我们在构建索引的时候，只需要考虑查询效率就可以了。不过，大部分情况下，我们都是对动态数据构建索引，也就是说，我们不仅要考虑到索引的查询效率，在原始数据更新的同时，我们还需要动态地更新索引。

索引存储在内存还是硬盘？如果索引存储在内存中，那查询的速度肯定要比存储在磁盘中的高。但是，如果原始数据量很大的情况下，因为内存有限，我们可能就不得不将索引存储在磁盘中了。实际上，还有第三种情况，那就是一部分存储在内存，一部分存储在磁盘，这样就可以兼顾内存消耗和查询效率。

单值查找还是区间查找？

单关键词查找还是多关键词组合查找？比如，搜索引擎中构建的索引，既要支持一个关键词的查找，比如“数据结构”，也要支持组合关键词查找，比如“数据结构 AND 算法”。对于单关键词的查找，索引构建起来相对简单些。对于多关键词查询来说，要分多种情况。像 MySQL 这种结构化数据的查询需求，我们可以实现针对多个关键词的组合，建立索引；对于像搜索引擎这样的非结构数据的查询需求，我们可以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。

非功能性需求

不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。如果存储在内存中，索引对占用存储空间的限制就会非常苛刻。毕竟内存空间非常有限，一个中间件启动后就占用几个 GB 的内存，开发者显然是无法接受的。如果存储在硬盘中，那索引对占用存储空间的限制，稍微会放宽一些。但是，我们也不能掉以轻心。因为，有时候，索引对存储空间的消耗会超过原始数据。

在考虑索引查询效率的同时，我们还要考虑索引的维护成本。索引的目的是提高查询效率，但是，基于动态数据集合构建的索引，我们还要考虑到，索引的维护成本。因为在原始数据动态增删改的同时，我们也需要动态的更新索引。而索引的更新势必会影响到增删改操作的性能。