什么是数据结构与算法

数组与链表的应用

数组的内存模型

int[] data = new int[5];

通过上面这段声明，计算机会在内存中分配一段连续的内存空间给这个 data 数组。

获取数组元素的方式是按照以下的公式进行获取的：

base_address + index（索引）× data_size（数据类型大小）

data 这个数组被分配到的起始地址是 0x80000000，是因为 int 类型数据占据了 4 个字节的空间，如果我们要访问第 5 个元素 data[4] 的时候，按照上面的公式，只需要取得 0x80000000 + 4 × 4 = 0x80000010 这个地址的内容就可以了。随机访问的背后原理其实也就是利用了这个公式达到了同等的时间访问到一组数据中的任意元素。

public void add(int index, E element) {
    ...
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    ...
}

add 函数调用了一个 System.arraycopy 的函数进行内存操作

如果我们调用了 add(1, 4) 函数，也就是在 index 为 1 的地方插入 4 这个元素，在 add 的函数中则会执行 System.arraycopy(elementData, 1, elementData, 2, 6 - 1) 语句，它的意思是将从 elementData 数组 index 为 1 的地址开始，复制往后的 5 个元素到 elementData 数组 index 为 2 的地址位置

这里涉及到了每个元素的复制，平均下来的时间复杂度相当于 O(n)。

public void remove(int index) {
    ...
    fastRemove(es, index);
    ...
}
 
private void fastRemove(Object[] es, int i) {
    ...
    System.arraycopy(es, i + 1, es, i, newSize - i);
    ...
}

如果我们调用了 remove(1) 函数，将从 elementData 数组 index 为 2 的地址开始，复制后面的 2 个元素到 elementData 数组 index 为 1 的地址位置

访问数组元素的时间复杂度是 O(1)。

插入和删除数组元素的时间复杂度为 O(n)。

位图数组在Redis中的应用

位数组（Bit Array）

一个 int 类型有 32 个比特位

可以把数组中一个 int 类型的元素当作是可以表达布尔状态的 32 个比特位元素。这种将每个元素中的每一个比特位都作为状态信息存储的数组称之为位数组（Bit Array）或者位图（Bit Map）。

拥有两个元素的 int 数组的内存模型

一般来说因为位数组的元素只保存“0”或者“1”两种状态，所以对于位数组的操作有以下几种：

获取某个位置的比特位状态；

设置某个位置的比特位，也就是将那个位置的比特位设置为“1”；

清除某个位置的比特位，也就是将那个位置的比特位设置为“0”。

Bitmap Redis 里面的一个数据结构

Bitmap 的本质其实是在 Redis 里面通过一个 Strings 类型来表示的。在 Redis 中，Strings 的最大长度可以是 512MB。

操作命令有以下几种：BITCOUNT、BITFIELD、BITOP、GETBIT、SETBIT。

如果想知道同时在 2019 年 11 和 12 月学习这个专栏的用户有多少，可以做怎样的优化呢？

我们可以用 Redis 里的 BITCOUNT、SETBIT 和 BITOP 来完成。BITCOUNT 这个命令其实是可以计算一个位数组里有多少比特位是为“1”的，而 BITOP 可以针对位数组进行“与”、“或”、“非”、“异或”这样的操作。

首先针对 11 月学习的用户和 12 月学习的用户，我们可以为它们创建单独的位数组，例如，logins:2019:11 和 logins:2019:12。在 11 月，每当有用户登录学习时，程序会自动调用“SETBIT logins:2019:11 user_id 1”，同理，对于 12 月登录学习的用户，我们也可以调用“SETBIT logins:2019:12 user_id 1”。SETBIT命令可以将user_id在位数组中相应的位设为“1”。

当要获得在这两个月内同时都学习了这个专栏的用户数时，可以调用“BITOP AND logins:2019:11-12 logins:2019:11 logins:2019:12”。将 logins:2019:11 和 logins:2019:12 这两个位数组做位运算中的与操作，将结果存放在“logins:2019:11-12”这个位数组中。最后调用“BITCOUNT logins:2019:11-12”来得到结果。

链表基础原理

链表（Linked List）

在计算机里，这种不保存在连续存储空间中，而每一个元素里都保存了到下一个元素的地址的数据结构，我们称之为链表（Linked List）。链表上的每一个元素又可以称它为节点（Node），而链表中第一个元素，称它为头节点（Head Node），最后一个元素称它为尾节点（Tail Node）。

与数组不同的是，我们无法使用一个固定的公式来直接算出某一个特定元素的地址，从而得到那个元素的值。要找到链表中的第 N 个元素的值，我们必须要从第一个元素开始，一个一个地遍历 N 次才能找到第 N 个元素，这种访问方式，我们就称之为顺序访问（Sequential Access）。

增加一个元素 只需要新创建一个链表的节点，然后将尾节点中保存地址的值更新成新的节点地址便可

数组的空间利用率相当于本来需要的大小除以创建出来数组的大小

链表的空间利用率上相当于值的大小除以值的大小和节点地址大小的和 当我们所保存的值的大小越大的时候，空间利用率也会越高。

访问数组元素的时间复杂度是 O(1)

访问链表元素的时间复杂度是 O(n)

插入操作 数组平均的时间复杂度都是 O(N)

​ 链表最优为O(1)（插入尾结点） 时间复杂度是 O(N) （插入中间节点）

**单向链表 **Singly Linked List

所有的链表节点中都只保存了指向下一个节点地址的信息

双向链表Doubly Linked List

在一个节点中保存了我们需要的数据也保存了连向下一个和上一个节点地址信息的链表

循环链表Circular Linked List

将尾节点指向下一个节点地址的信息更新成指向头节点的话，这样整个链表就形成了一个环

链表在Apache Kafaka中的应用

如何重新设计定时器算法

可以把定时器的概念抽象成 4 个部分：

1、初始化定时器，规定定时器经过了多少单位时间之后超时，并且在超时之后执行特定的程序；

2、删除定时器，终止一个特定的定时器；

3、定时器超时进程，定时器在超时之后所执行的特定程序；

4、定时器检测进程，假设定时器里的时间最小颗粒度为 T 时间，则每经过 T 时间之后都会执行这个进程来查看是否定时器超时，并将其移除。

维护有序定时器列表

我们可以维护一个定时器列表，每次插入一个新的定时器时，并不是将它插入到链表的结尾，而是从头遍历一遍链表，将定时器的超时时间按从小到大的顺序插入到定时器列表中。每次插入新定时器时，并不是保存超时时间，而是根据当前系统时间和超时时间算出一个绝对时间出来。例如，当前的系统时间为 NowTime，超时时间为 2T，那这个绝对时间就为 NowTime + 2T。

假设原来的有序定时器列表如下图所示：

当我们要插入一个新的定时器，超时的绝对时间算出为 25 Dec 2019 9:23:34，这时候我们会按照超时时间从小到大的顺序，将定时器插入到定时器列表的开头，如下图所示：

维护一个有序的定时器列表的好处是，每次执行定时器检测进程的时间复杂度为 O(1)，因为每次定时器检测进程只需要判断当前系统时间是否是在链表第一个节点时间之后了，如果是则执行定时器超时进程并删除定时器，如果不是则结束定时器检测进程。

这种方法的好处是执行定时器检测进程和删除定时器的时间复杂度为 O(1)，但因为要按照时间从小到大排列定时器，每次插入的时候都需要遍历一次定时器列表，所以插入定时器的时间复杂度为 O(N)。

维护定时器“时间轮”

“时间轮”（Timing-wheel ）在概念上是一个用数组并且数组元素为链表的数据结构来维护的定时器列表，常常伴随着溢出列表（Overflow List）来维护那些无法在数组范围内表达的定时器。“时间轮”有非常多的变种，今天我来解释一下最基本的“时间轮”实现方式。

首先基本的“时间轮”会将定时器的超时时间划分到不同的周期（Cycle）中去，数组的大小决定了一个周期的大小。例如，一个“时间轮”数组的大小为 8，那这个“时间轮”周期的大小就为 8T。同时，我们维护一个最基本的“时间轮”还需要维护以下几个变量：

“时间轮”的周期数，用 S 来表示；

“时间轮”的周期大小，用 N 来表示；

“时间轮”数组现在所指向的索引，用 i 来表示。

现在的时间我们可以用 S×N + i 来表示，每次我们执行完一次定时器检测进程之后，都会将 i 加 1。当 i 等于 N 的时候，我们将 S 加 1，并且将 i 归零。因为“时间轮”里面的数组索引会一直在 0 到 N－1 中循环，所以我们可以将数组想象成是一个环，例如一个“时间轮”的周期大小为 8 的数组，可以想象成如下图所示的环：

​

那么我们假设现在的时间是 S×N + 2，表示这个“时间轮”的当前周期为 S，数组索引为 2，同时假设这个“时间轮”已经维护了一部分定时器链表，如下图所示：

​ 如果我们想新插入一个超时时间为 T 的新定时器进这个时间轮，因为 T 小于这个“时间轮”周期的大小 8T，所以表示这个定时器可以被插入到当前的“时间轮”中，插入的位置为当前索引为 1 + 2 % 8 = 3 ，插入新定时器后的“时间轮”如下图所示：

​

如果我们现在又想新插入一个超时时间为 9T 的新定时器进这个“时间轮”，因为 9T 大于或等于这个“时间轮”周期的大小 8T，所以表示这个定时器暂时无法被插入到当前的周期中，我们必须将这个新的定时器放进溢出列表里。溢出列表存放着新定时器还需要等待多少周期才能进入到当前“时间轮”中，我们按照下面公式来计算还需等待的周期和插入的位置：

还需等待的周期：9T / 8T = 1
新定时器插入时的索引位置：(9T + 2T) % 8T = 3

还需等待的周期：9T / 8T = 1
新定时器插入时的索引位置：(9T + 2T) % 8T = 3
我们算出了等待周期和新插入数组的索引位置之后，就可以更新溢出列表，如下图所示：

​

在“时间轮”的算法中，定时器检测进程只需要判断“时间轮”数组现在所指向的索引里的链表为不为空，如果为空则不执行任何操作，如果不为空则对于这个数组元素链表里的所有定时器执行定时器超时进程。而每当“时间轮”的周期数加 1 的时候，系统都会遍历一遍溢出列表里的定时器是否满足当前周期数，如果满足的话，则将这个位置的溢出列表全部移到“时间轮”相对应的索引位置中。

在这种基本“时间轮”的算法里，定时器检测进程的时间复杂度为 O(1)，而插入新定时器的时间复杂度取决于超时时间，因为插入的新定时器有可能会被放入溢出列表中从而需要遍历一遍溢出列表以便将新定时器放入到相对应周期的位置。

“时间轮”变种算法

基本的“时间轮”插入操作因为维护了一个溢出列表导致定时器的插入操作无法做到 O(1) 的时间复杂度，所以为了 O(1) 时间复杂度的插入操作，一种变种的“时间轮”算法就被提出了。

在这个变种的“时间轮”算法里，我们加了一个 MaxInterval 的限制，这个 MaxInterval 其实也就是我们定义出的“时间轮”数组的大小。假设“时间轮”数组的大小为 N，对于任何需要新加入的定时器，如果超时时间小于 N 的话，则被允许加入到“时间轮”中，否则将不被允许加入。

这种“时间轮”变种算法，执行定时器检测进程还有插入和删除定时器的操作时间复杂度都只有 O(1)。

Apache Kafka 的 Purgatory 组件

Apache Kafka 是一个开源的消息系统项目，主要用于提供一个实时处理消息事件的服务。与计算机网络里面的 TCP 协议需要用到大量定时器来判断是否需要重新发送丢失的网络包一样，在 Kafka 里面，因为它所提供的服务需要判断所发送出去的消息事件是否被订阅消息的用户接收到，Kafka 也需要用到大量的定时器来判断发出的消息是否超时然后重发消息。

而这个任务就落在了 Purgatory 组件上。在旧版本的 Purgatory 组件里，维护定时器的任务采用的是 Java 的 DelayQueue 类来实现的。DelayQueue 本质上是一个堆（Heap）数据结构，现在我们可以把这种实现方式看作是维护有序定时器列表的一种变种。这种操作的一个缺点是当有大量频繁的插入操作时，系统的性能将会降低。

因为 Kafka 中所有的最大消息超时时间都已经被写在了配置文件里，也就是说我们可以提前知道一个定时器的 MaxInterval，所以新版本的 Purgatory 组件则采用的了我们上面所提到的变种“时间轮”算法，将插入定时器的操作性能大大提升。根据 Kafka 所提供的检测结果，采用 DelayQueue 时所能处理的最大吞吐率为 25000 RPS，采用了变种“时间轮”算法之后，最大吞吐率则达到了 105000 RPS。

---

哈希表的应用

哈希函数的本质及生成方式

哈希表

涉及两个重要算法：哈希函数和解决哈希碰撞的算法

哈希表与哈希函数

其本质上是一个数组

如果要访问一个数组中某个特定的元素，那么需要知道这个元素的索引。例如，我们可以用数组来记录自己好友的电话号码，索引 0 指向的元素记录着 A 的电话号码，索引 1 指向的元素记录着 B 的电话号码，以此类推。

而当这个数组非常大的时候，全凭记忆去记住哪个索引记录着哪个好友的号码是非常困难的。这时候如果有一个函数，可以将我们好友的姓名作为一个输入，然后输出这个好友的号码在数组中对应的索引，是不是就方便了很多呢？这样的一种函数，其实就是哈希函数。

将任意长度的一个对象映射到一个固定长度的值上，而这个值我们可以称作是哈希值（Hash Value）。

哈希函数一般会有以下三个特性：

• 任何对象作为哈希函数的输入都可以得到一个相应的哈希值；

• 两个相同的对象作为哈希函数的输入，它们总会得到一样的哈希值；

• 两个不同的对象作为哈希函数的输入，它们不一定会得到不同的哈希值。

按照 Java String 类里的哈希函数公式（即下面的公式）来计算出不同字符串的哈希值。

String 类里的哈希函数是通过 hashCode 函数来实现的，这里假设哈希函数的字符串输入为 s，所有的字符串都会通过以下公式来生成一个哈希值：

如果我们输入“ABC”这个字符串（按ASCII表），那根据上面的哈希函数公式，它的哈希值则为：

“Aa” 的哈希值为：

"Aa" = 'A' * 31 + 'a' = 65 * 31 + 97 = 2112

“BB” 的哈希值为：

"BB" = 'B' * 31 + 'B' = 66 * 31 + 66 = 2112

不同的两个字符串其实是会输出相同的哈希值出来的，这时候就会造成 —–哈希碰撞

（ hashCode 的算法里都是加法，但是算出来的哈希值有可能会是一个负数）

在计算机里，一个 32 位 int 类型的整数里最高位如果是 0 则表示这个数是非负数，如果是 1 则表示是负数。

如果当字符串通过计算算出的哈希值大于 2~32-1 时，也就是大于 32 位整数所能表达的最大正整数了，则会造成溢出，此时哈希值就变为负数了

hashCode 函数中的“魔数”（Magic Number）31

Java Openjdk-jdk11 中 String.java 的源码:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return

可以看到，String 类的 hashCode 函数依赖于 StringLatin1 和 StringUTF16 类的具体实现。而 StringLatin1 类中的 hashCode 函数和 StringUTF16 类中的 hashCode 函数所表达的算法其实是一致的。

StringLatin1 类中的 hashCode 函数如下面所示：

public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h

StringUTF16 类中的 hashCode 函数如下面所示：

public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
        h = 31 * h + getChar(value, i);
    }
    return h

一个好的哈希函数算法都希望尽可能地减少生成出来的哈希值会造成哈希碰撞的情况。

Goodrich 和 Tamassia 这两位计算机科学家曾经做过一个实验，他们对超过 50000 个英文单词进行了哈希值运算，并使用常数 31、33、37、39 和 41 作为乘数因子，每个常数所算出的哈希值碰撞的次数都小于 7 个。

从数学的角度来说，选择一个质数（Prime Number）作为乘数因子可以让哈希碰撞减少。

我们可以看到在上面的两个 hashCode 源码中，都有着一条 31 * h 的语句，这条语句在 JVM 中其实都可以被自动优化成“(h << 5) - h”这样一条位运算加上一个减法指令，而不必执行乘法指令了，这样可以大大提高运算哈希函数的效率。

区块链挖矿的本质

如果告诉你一个哈希值，即便给出了哈希函数的公式也很难算得出原来的输入到底是什么。、

例如，还是按照上面 String 类的 hashCode 函数的计算公式：

如果告诉了你哈希值是 123456789 这个值，那输入的字符串是什么呢？

我们想要知道答案的话，只能采用暴力破解法，也就是一个一个的字符串去尝试，直到尝试出这个哈希值为止。

对于区块链挖矿来说，这个“矿”其实就是一个字符串。“矿工”，也就是进行运算的计算机，必须在规定的时间内找到一个字符串，使得在进行了哈希函数运算之后得到一个满足要求的值。

我们以比特币为例，它采用了 SHA256 的哈希函数来进行运算，无论输入的是什么，SHA256 哈希函数的哈希值永远都会是一个 256 位的值。

而比特币的奖励机制简单来说是通过每 10 分钟放出一个哈希值，让“矿工们”利用 SHA256(SHA256(x)) 这样两次的哈希运算，来找出满足一定规则的字符串出来。

比方说，比特币会要求找出通过上面 SHA256(SHA256(x)) 计算之后的哈希值，这个 256 位的哈希值中的前 50 位都必须为 0 ，谁先找到满足这个要求的输入值 x，就等于“挖矿”成功，给予奖励一个比特币。我们知道，即便知道了哈希值，也很难算出这个 x 是什么，所以只能一个一个地去尝试。而市面上所说的挖矿机，其原理是希望能提高运算的速度，让“矿工”尽快地找到这个 x 出来。

哈希函数在 GitHub 和比特币中的应用

哈希函数 在密码学中也起着关键性的作用

看看哈希函数是如何被应用在 GitHub 中的，以及再看看链表和哈希函数在比特币中是怎么应用的。

加密哈希函数

一个哈希函数如果能够被安全地应用在密码学中，我们称它为加密哈希函数（Cryptographic Hash Function）。“数字摘要”，它也是通过加密哈希函数，由任意长度的一个信息转换出来的一个固定长度的哈希值。

数字摘要通常是用于检验一段数据或者一个文件的完整性（Integrity）的，而验证数据文件完整性就是利用了哈希函数里的其中一个特性：“两个相同的对象作为哈希函数的输入，它们总会得到一样的哈希值”。

常见的加密哈希函数算法，有 MD（Message Digest）算法和 SHA（Secure Hash Algorithm）算法。

MD 算法可以通过输入产生一个 128 位的哈希值出来，用于确保信息传输的完整性；而在 SHA 算法中，比较常见的有 SHA-1、SHA-256 算法等，它们也是可以通过输入而产生一个 160 位或者 256 位的哈希值出来，它们与 MD 算法一样，都是用于确保信息传输的完整性

SHA-1 加密算法

Git 采用了 SHA-1 算法来对每一个文件对象都进行了一次哈希值运算，所以每一个提交的文件都会有自己的一个哈希值。在 Git 里面要找到一个文件对象其实是通过哈希值来寻找的。

运行“git commit”命令的时候，Git 会将所有的这些文件，外加一些元数据（Metadata）再做一次 SHA-1 运算来得到一个新的哈希值，这些元数据里就包括了上一次 commit 时所生成的哈希值。将上一次 commit 所产生的哈希值也包括进来主要为了防止有人恶意地去修改中间的一些 commit，这样，所有后面的 commit 就可以发现，自己所保存的上一次 commit 的哈希值和被修改过的 commit 的哈希值不一致了，也就是说中间的 commit 被人篡改了。

GitHub 面临的问题

Git 其实是通过 SHA-1 算法所产生的哈希值去找到一个文件对象的，那如果有恶意程序可以对两个不同的文件制造出相同的哈希值，也就是产生哈希碰撞，这样 Git 就无法确定到底哪一个文件才是“真的”。

真的要人为的去制造一个 SHA-1 哈希冲突攻击的话，现阶段的代价是非常昂贵的，比方说需要耗费 6500 年的单核 CPU 计算时间，或者说需要消耗 110 年的单核 GPU 计算时间

比特币的本质

它的本质思想是以区块链为基础而搭建起来的一个去中心化的记账系统。

我们平时所使用的记账系统，无论是使用实体银行卡或者是使用移动支付，其交易信息都会记录在一个统一的数据库中。而在去中心化的记账系统里，则会把这些交易信息进行加密直接存放在用户那里。

比特币将所有的交易记录都存放在了一个叫区块（Block）的数据结构里面

我们可以把这里的区块看作是链表数据结构中的一个节点。当用户需要将新的交易记录打包的时候，可以自己创建一个新的区块出来，放在整个区块链的结尾，也就相当于在一个链表的结尾插入一个新的节点

整个区块链中的第一个区块，也就是链表的头节点，叫做创世区块（Genesis Block）。

与链表数据结构使用内存地址去寻找下一个节点不同的是，区块链采用了哈希值的方式去寻找节点。

采用的是 SHA-256 这种加密哈希函数

将每一个区块都计算出一个 256 位的哈希值。在每一个新的区块中都会保存着上一个区块所计算出来的哈希值，通过这个哈希值，我们就可以找到哪一个区块是这个新区块的上一个区块。所有的区块都可以通过这种机制去寻找上一个区块，从而遍历整个区块链，直到找到创世区块为止。

当然了，不是每个人都是有“资格”去创建一个新区块的。就如上一讲中所讲述的区块链“挖矿”原理一样，只有当一个用户“挖矿”成功了，那这个用户才有资格去打包交易信息并建立一个新的区块。一个典型的比特币区块链就如下图所示：

哈希碰撞的本质及解决方式

哈希函数产生了哈希碰撞，应该如何处理？

BloomFilter

哈希碰撞的情况

哈希表的定义，在概念上**哈希表可以定义为是一个根据键（Key）而直接访问在内存中存储位置的值（Value）的数据结构 ** 键就是指哈希函数的输入 值 指我们想要保存的值

我们假设存储哈希表的底层数据结构是一个大小为 3 的数组，我们还是以保存好友电话号码为例，这个哈希表的键是我们好友的名字，哈希表的值是这个好友的电话号码。刚开始的时候，因为这个数据结构并没有存储任何信息，所以数据结构内存结构图如下图所示：

假设第一个输入的键值对是（Tom：123456），表示好友的名字叫 Tom，电话号码为 123456。我们同时假设 Tom 这个字符串在通过哈希函数之后的所产生的哈希值是 0，此时可以把 123456 这个值放在以哈希值为索引的地方，内存结构如下图所示：

紧接着，我们输入的第二个键值对是（Jack：456789），同时假设 Jack 这个字符串在通过哈希函数之后的所产生的哈希值也是 0，而因为索引为 0 的位置已经存放一个值了，也就表示这时候产生了哈希碰撞。下面我就介绍一下常用的两种解决哈希碰撞的方式。

开放寻址法（Open Addressing）

开放寻址法本质上是在数组中寻找一个还未被使用的位置，将新的值插入。这样做的好处是利用数组原本的空间而不用开辟额外的空间来保存值。最简单明了的方法就是沿着数组索引，往下一个一个地去寻找还未被使用的空间，这种方法叫做线性探测

继续看刚才的例子，因为索引为 0 的地址已经被使用，那我们就可以寻找下一个位置，也就是索引为 1 的地址，发现还未被使用过，所以我们就可以把 Jack 的电话号码存放在这里。因为在产生了哈希碰撞之后，我们无法确定数组里面保存的值到底是哪一个键产生的，所以必须将键也一并保存在数组中，内存结构如下图所示：

现在我们继续输入第三个键值对（Mike：000111）到哈希表中。假设 Mike 这个输入通过哈希函数产生的哈希值还是 0，按照线性探测的方法，先来看看下一个索引为 1 的地址，它已经被使用了，所以继续往下遍历到索引为 2 的地址，发现还未被使用，此时可以把 Mike 的电话号码存放在这里，内存结构如下图所示：

这时候你已经发现了，保存键值对的数组已经满了，如果再有新的元素插入的话，就无法保存新的键值对了。一般的做法是将这个数组扩容，比如，再创建一个新的数组，其大小为原来数组大小的两倍，然后把原来数组的内容复制过去，如果采用这种做法的话，这时的内存结构图如下所示：

当然了，一般哈希表并不会等到这个数组满了之后再进行扩容，其实底层数据结构会维护一个叫做负载因子（Load Factor）的数据，负载因子可以被定义为是哈希表中保存的元素个数 / 哈希表中底层数组的大小。

当这个负载因子过大时，则表示哈希表底层数组所保存的元素已经很多了，所剩下的未被使用过的数组位置会很少，同时产生哈希碰撞的概率会很高，这并不是我们想看到的。所以一般来说，在负载因子的值超过一定值的时候，底层的数组就得需要进行扩容了，像在 Java 的 JDK 中，都会把负载因子的默认值设为 0.75

每次遇到哈希碰撞的时候都只是往下一个元素地址检测是否有未被使用的位置存在，所以有可能会导致一种叫做哈希聚集（Primary Clustering）的现象。

哈希表保存的元素现在都聚集在了 0、1、2 这三个索引位置的地方，如果有新的元素需要插入，而它的哈希值为 1 的话，本来这个位置是不应该产生哈希碰撞的，但由于采用了线性探测的方法，使得这个位置被占用了，所以新插入的元素还得重新再进行一次线性探测。

对此有一些改进的算法被提出用以缓解上面所说的哈希聚集问题，比如平方探测（Quadratic Probing）和二度哈希（Double Hashing）。

• 平方探测指的是每次检查空闲位置的步数为平方的倍数。例如说，当新元素插入的键所产生的哈希值为 i，那下一次的检测位置为：i 加上 1 的平方、i 减去 1 的平方、i 加上 2 的平方、i 减去 2 的平方、…，以此类推。

• 二度哈希指的是数据结构底层会保存多个哈希函数，当使用第一个哈希函数算出的哈希值产生了哈希碰撞之后，将会使用第二个哈希函数去运算哈希值，…，以此类推。

分离链接法（Separate Chaining）

分离链接法与链表有很大的关系，它的本质是将所有的同一哈希值的键值对都保存在一个链表中，而哈希表底层的数组元素就是保存这个哈希值对应的链表。

下面我们还是假设存储哈希表的底层数据结构是一个大小为 3 的数组，还是以保存好友电话号码为例，刚开始的内存结构图如下图所示：

同样假设第一个输入的键值对是（Tom：123456），表示好友的名字为 Tom，电话号码为 123456。同时假设 Tom 这个字符串在通过哈希函数之后所产生的哈希值是 0，因为 0 这个索引位置并未使用，所以我们创建一个新的链表节点，将键值对的值保存在这个新节点中，而 0 这个索引位置的值就是指向新节点的地址，内存结构如下图所示：

紧接着，我们输入第二个键值对（Jack：456789），同时假设 Jack 这个字符串在通过哈希函数之后所产生的哈希值也是 0，而因为索引为 0 的位置已经存放一个值了，也就表示这时候产生了哈希碰撞。但是没关系，我们只需要再创建一个新的链表节点，将这个键值对的值保存在新节点中，然后将这新节点插入索引 0 位置链表的结尾，内存结构如下图所示：

采用分离链接法会使用到额外的空间来保存新插入的键值对

虽然这里举的例子采用的是链表，这在查找一个键对应的值时，有可能时间复杂度会降级为 O(N)，但很多时候我们可以进一步将存储结构优化成红黑树

在 Java JDK 中的 HashMap 类其实就是使用了分离链接法。

Bloom Filter

Bloom Filter 是一个哈希表和位数组相结合的基于概率的数据结构

它主要用于在超大的数据集合中判断一个元素是否存在这个集合中，像判断一个人是否在黑名单中一样

因为使用了位数组，所以使得 Bloom Filter 在空间利用率上非常的高效

同时它的底层原理和哈希表一致，使得它在查找的时间复杂度上也十分优秀

Bloom Filter 的原理是将一个元素通过多个哈希函数映射到位数组中

我们以黑名单为例来说明，假设哈希函数的个数为 2，也假设黑名单中只有 a 和 b 两个元素，在通过两次哈希函数映射到位数组之后，内存结构图如下图所示：

我们把元素经过两次哈希函数之后所对应的哈希值的位置设为 1，此时需要判断元素 c 是否在黑名单中，需要将 c 也进行两次哈希函数运算，得到的结果如下图所示：

你会发现 c 在经过哈希函数映射之后有一个哈希值对应的位置结果为 0，那就表示 c 这个元素一定不在黑名单中。此时我们再来还需要判断元素 d 是否在黑名单中，需要将 d 也进行两次哈希函数运算，得到的结果如下图所示：

你会发现 d 在经过哈希函数映射之后有两个哈希值所对应的位置结果都为 1，但是我们只能判断 d 这个元素有可能在黑名单中。所以这里存在一个误判率，也就是说即便经过 N 个哈希函数之后哈希值对应位置的结果都为 1 了，但这个元素不一定真的存在集合中。

误判率的公式如下：

其中，m 表示位数组里位的个数，n 表示已经存储在集合里的元素个数，k 表示哈希函数的个数。

哈希表在 Facebook 和 Pinterest 中的应用

均摊时间复杂度

哈希表插入和删除操作的均摊时间复杂度都属于均摊 O(1)

如果说一个数据结构的均摊时间复杂度是 X，那么这个数据结构的时间复杂度在大部分情况下都可以达到 X，只有当在极少数的情况下出现时间复杂度不是 X。

若发生哈希碰撞 ，那时间复杂度就变成了 O(N) 。造成哈希碰撞的情况是少数的，大部分时间，它的时间复杂度还是 O(1)。

缓存（Cache）缓存这个概念其实不单单只是针对于内存来说的，可以抽象地把缓存看作是一种读取速度更快的媒介。

Memcached 和 Redis 这两个框架是现在应用得最广泛的两种缓存系统，它们的底层数据结构本质都是哈希表。

Memcached 缓存

Memcache 是一种分布式的键值对存储系统，它的值可以存储多种文件格式，比如图片、视频等。Memcache 的一个很大特点就是数据完全保存在内存中，也就是说如果一台运行着 Memcache 的机器突然挂掉了，那保存在上面的数据就会全部丢失，所以我们可以把保存在 Memcache 中的数据看作是 Memcache 维护了一个超级大的哈希表数据结构，并没有任何内容保存在硬盘中。

同样的，因为每台机器的内存容量是有限的，如果存储的数据占满了一台机器的内存之后，再有新的数据想保存进 Memcache 的话，就必须把旧的数据删除掉。

哈希表在 Facebook 中的应用

Facebook 会把每个用户发布过的文字和视频、去过的地方、点过的赞、喜欢的东西等内容都保存下来，想要在一台机器上存储如此海量数据是完全不可能的，所以 Facebook 的做法是会维护为成千上万台机器运行 Memcache，不同的数据会保存在不同的 Memcache 中，这里我们可以看作是不同的数据都有不同的哈希表来维护它们。

很多数据不从数据库读取的话是拿不到最新数据的，怎么办呢 设定一个过期时间

好友生日提醒

最简单的应用就是 Facebook 里的好友生日提醒了，其做法是将用户 ID 和用户的生日日期作为键值对存放在 Memcache 中。每个用户在当天登录的时候，会先以所有的好友 ID 作为键，去 Memcache 中寻找是否有他们的数据存在，如果存在则判断当天的日期是否是好友生日的日期，然后决定是否发送生日提醒；如果不存在，则先去数据库中拿出所有好友的生日日期，然后存在 Memcache 中，最后返回给用户判断。

当然了，Facebook 的设定是允许用户修改生日日期的，这样就无法将用户的生日直接存放在 Memcache 之后就一劳永逸了，如果用户修改了自己的生日在更新数据库的同时也需要发送请求删除 Memcache 中的数据。

就是这简单的一个功能，其实每天都会对 Memcache 这个哈希表产生数十亿次操作。

通过访问直播链接来看回放

Facebook 把每一个直播的视频流数据按照每一秒钟的时间分割成一个块（Segment），每一个视频流块都会被存放在 Memcache 中。当用户读取直播视频流的时候，会以直播 ID 加上这个时间进度作为哈希表的键，来读取每一秒的直播视频。

Redis 缓存

它与 Memcache 的一个很大不同是，保存在 Redis 上的数据会每间隔一段时间写入到磁盘中，以防止当机器宕机后可以重新恢复数据。

哈希表在 Pinterest 中的应用

推荐系统的算法在很大程度上是通过读取每个用户的关系图来进行推荐的 Pinterest 将很多这些关系图都保存在了 Redis 里面，从而不必从数据库中读取内容。

---

树的应用

树的基本原理

队列和堆栈，队列是先进先出，而堆栈是先进后出

树由节点和边连接组成 是一种非线性的数据结构

没有子节点的节点也被称作**叶子节点 ** C、E、F、L、G 都是叶子节点

共享同样父节点的节点被称作兄弟节点 B、C、D 就是兄弟节点

一个节点的深度是从根节点到自己边的数量，比如 K 的深度是 2。

节点的高度是从最深的节点开始到自己边的数量，比如 B 的高度是 2。一棵树的高度也就是它根节点的高度。

树的编程实现方式

基于链表的实现一般是每一个节点类型维护一个子节点指针和一个指向兄弟节点的链表，我们把它称作左孩子兄弟链表法

class TreeNode {
      Data data;
      LinkedList siblings;
      TreeNode left_child;
}

节点 B 的 siblisings 节点是一个指向 C 接着指向 D 的链表，节点 B 的 left_child 节点则指向 E。

另一种基于数组的实现方式是每一个节点维护一个包含它所有子节点的数组，我们把它称作孩子数组法。

class TreeNode {
      Data data;
      ArrayList children;
}

树的遍历和基本算法

查找操作，也就是遍历

前序遍历、后续遍历、按层遍历。

前序遍历：先访问根节点N 递归访问N的子树

后续遍历：递归访问N的子树 后访问根节点N

按层遍历：就是从上到下、从左到右访问

为什么要优化 SQL 的执行

一个简单的 SQL 执行引擎模型是这样子的：

• 首先是 SQL 解析器（Parser），它负责把用户输入的 SQL 解析成 SQL 语法树（AST），对的，就是我们讲的树！

• 后面的 SQL 优化器（Optimizer）接受前面解析的原生语法树，对它进行优化重写语法树和执行计划。一般优化器不仅仅会看语法树，还需要结合特定的用户数据库配置，数据实际分布进行优化。

• 最后面的 SQL 执行器（Executor）才会去真正的执行优化重写的 SQL 语法树。

平衡树的性能优化

平衡树的全称是平衡二叉查找树（Balanced Binary Search Tree，简称 Balanced Tree）

二叉查找树 （Binary Search Tree，简称 BST）

• 二叉查找树是一棵二叉树，也就是说每一个节点至多有 2 个孩子，也就是 2 个子树。

• 二叉查找树的任意一个节点都比它的左子树所有节点大，同时比右子树所有节点小。

为了方便搜索节点

当我们需要查找一个节点的时候，如果这个节点小于根，那我们肯定是去左子树中继续查找，因为它不可能出现在右子树中了，右子树的所有节点必须大于根。反过来说，如果想要查找的值大于根呢？我们就只需要去右子树中查找即可。

TreeNode* Search(TreeNode* root, int key) { 
    if (root == nullptr || root->key == key) {
       return root; 
    }
     
    if (root->key < key) {
      return Search(root->right, key); 
    }
  
    return Search(root->left, key); 
}

Search() 方法的每一次调用都会在树中往下移动一层

算法时间复杂度，就是树的高度 O(h)

这棵树的高度是 O(log n)，n 是这棵树的节点数量。无论搜索哪个节点，我们最多需要运行上面的 Search() 方法 O(log n)

这样的二叉树退化成了一个一维链表，最坏情况是需要从第一个节点查找到第 n 个节点，时间复杂度就成了 O(n) 了。

平衡树

一棵树的数据结构能够维护好自己的高度和形状，让形状保持平衡的同时，高度也会得到控制

红黑树被定义成：

• 一棵二叉树，每一个节点要么是红色，要么是黑色

• 根节点一定是黑色

• 红节点不能有红孩子

• 每条从根节点到底部的路径都经过同样数量的黑节点

满足这些定义的红黑树可以被数学证明树的高度为 O(log n)

B 树：每个节点可以存储多个数值

• 所有叶子节点的深度一样

• 非叶子节点只能存储 b － 1 到 2b － 1 个值

• 根节点最多存储 2b － 1 个值

红黑树可以被理解成 order 为 4 的一种特殊 B 树，称为 2-3-4 树，之所以称为 2-3-4 树，是因为每个有子树的节点都只可能有两个，或者 3 个，或者 4 个子节点。

AVL 树 任意一个节点的左右子树高度最多相差 1。

LSM 树在 Apache HBase 等存储系统中的应用

LSM 树

。。。

---

图的应用

用图来表达更为复杂的数据关系

社交网络

交通网络

互联网网站连接

图的定义、图的方向和权重

从数学规范上来讲一个图可以被定义成一个集合 G， G = (V,A) ，其中：

• V 是图的节点集合

• A ⊆ V × V 是节点与节点之间的连接的边，边可以是有向或者是无向的

有向图

节点 C 指向节点 A，而节点 A 又指向了节点 D。微博上的关注，你可能关注了一个大 V，但是大 V 并不一定关注了你，这就是一个单向的关系，可以用有向图来建模

无向图

可以把无向的边理解成同时由两个有向边组成

比如说在微博上，如果你关注了 A，并且 A 也关注了你，我们就可以把你和 A 的关系看作是一条无向的边。

有权重的图

图和树的区别

树表达的是层级化的结构，图是用来表达网络化的结构。

树是有父节点和子节点这样的关系存在的。树有一个根节点，下面的每一棵子树都有唯一的根节点；而图则不一样，图的每一个节点都可以看作是平等的，并且节点与节点之间的连接也更为自由。在树中一个父节点只能与它的子节点相连，但不会看到父节点与孙子节点相连。但是在图中，任意节点都是可以相连的。

图的实现和内存表达

1. 邻接矩阵法

使用邻接矩阵法的基本思想是开一个超大的数组，用数组中间元素的 true / false 来表达边。具体什么意思呢？比如你有 V 个节点的图，那么就需要一个 V×V 大小的数组。

我们来看一个例子，下面这个例子中有 V0 - V4 总共 5 个节点，可以看到我们已经画出了一个 5 × 5 的二维数组 G。如果学习了之前数组章节中的二维数组，就知道可以用 G[i][j] 这样的寻址方式来找到第 i 行第 j 列的元素。在这个例子中规定，如果有从 Vi 指向 Vj 的边，那么 G[i][j] = true，反之如果没有边，则 G[i][j] = false。不如一起来看看在这个例子中有哪些数组元素会是 true。

我们首先看看 V4 指向 V2 的边，即 G[4][2] = true；接着再看看 V0 和 V2 之间的边是无向的，也就是说，我们需要 G[0][2] = true，同时 G[2][0] = true；最后看到 V3 有指向自己的边，所以 G[3][3] 也是 true，可以发现邻接矩阵法的实际上存储的是所有的边。

2. 邻接链表法

把每一个节点所指向的点给存储起来

比如还是同样一个图 V0 - V4，如果我们用邻接链表法表达的话，则需要一个含有 5 个元素的数组，用来存储这样 5 个节点；然后每个节点所指向的点都会维护在一个链表中。比如在这个例子中，V0 指向了 V1、V4、V2 三个节点，那么在内存中就会有从 0 指向 1 接着指向 2、4 类似这样的一个链表。同理我们看 V4 指向了 V0 和 V2，则在内存中就要维护一个 4→0→2 的单向链表。

邻接矩阵法因为存储在二维数组中 **随机访问快 ** 可以更快地添加和删除边 需要一个 O(V^2) 的内存空间，相对来说更适合边比较多的图

邻接链表法可以更快地操作一个节点相邻的节点，在一个稀疏的图中也就是边比较少的图中，邻接链表法的效率其实是比较高的。

有向无环图在 Spark 中的应用

Spark 分布式大规模数据处理引擎 核心 有向无环图（DAG）来优化数据处理任务

如何用有向无环图抽象表达数据处理的任务

最后一步炒的步骤依赖于切好的番茄、打好的蛋、热好的油，切好的番茄又依赖于洗好的番茄等操作。

如果用 Spark 来实现的话，在这个图里面，每一个箭头都会是一个独立的数据转换操作（Transformation）。

Spark 利用有向无环图表达数据处理后可以对数据处理流程做自动优化

图的实现方式与核心算法

图的拓扑排序

拓扑排序指的是对于一个有向无环图来说，排序所有的节点，使得对于从节点 u 到节点 v 的每个有向边 uv，u 在排序中都在 v 之前。

在我们西红柿炒鸡蛋这个菜的加工过程中，要保证打鸡蛋在炒鸡蛋之前，买番茄在洗番茄之前，因为炒鸡蛋依赖于打鸡蛋，在我们的图中有打鸡蛋指向炒鸡蛋的边。

合理的拓扑排序是能够保证有依赖关系的任务能够被合理完成

先有鸡还是先有蛋 （Chicken Egg Dilemma）就是一个无法被拓扑排序的有环图，因为鸡依赖于蛋，蛋又依赖于鸡，你无法把鸡排在蛋前面，也不能把蛋排在鸡的前面。

拓扑排序的实现方式

图的入度和出度

一个有向图的入度指的是终止于一个节点的边的数量；

​ 出度指的是始于一个节点的边的数量

节点 A 的入度为 2，节点 B 的入度则为 0；而节点 B 的出度为 2，节点 D 的出度则为 0。

卡恩算法是卡恩于 1962 年提出的算法，它其实是贪婪算法的一种形式。简单来说就是，假设 L 是存放结果的列表，我们先找到那些入度为零的节点，把这些节点放到 L 中，因为这些节点没有任何的父节点；然后把与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的这些入度为零的节点来说，他们的父节点都已经在 L 中了，所以也可以放入 L。

重复上述操作，直到找不到入度为零的节点。如果此时 L 中的元素个数和节点总数相同，则说明排序完成；如果 L 中的元素个数和节点总数不同，则说明原图中存在环，无法进行拓扑排序。下面我们来看看这个算法的伪代码：

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order

图的最短路径

在一个有权重的图中，找到两个点之间权重之和最短的路径。

举例来说下，图中所有节点都是不同的城市，每一条边都是连接城市之间的道路距离。比如 1 号节点是武汉，那么我们想要快速地把医疗物资送到武汉的话，就需要找到通向武汉最短的路线。

假如我们有一大批口罩在 5 号城市，想要送往武汉的话可以选择走 5-2-1 这条路线，或者 5-3-1 这条路线，甚至 5-2-3-1 等很多路线。在这个例子中我们很容易发现，5-2-1 这条路线的总距离是 20 + 9 = 29，5-3-1 这条路线的总距离是 12+15 = 27，可见我们应该选择 5-3-1 这个路线。

怎样让计算机找到最短路径呢？这便是大名鼎鼎的 Dijkstra 算法。

---

数据结构组合引擎

缓存数据结构在 Nginx 中的应用

LRU 缓存

LRU 缓存是利用了 Least Recently Used 算法来实现的一种最最常见的缓存策略

假设有一个应用希望能够加快数据的访问速度，因此在内存中设置了缓存来进行加速，为了方便说明，我们假设内存中只能够存储 3 个数据，当有更新的数据需要保存在缓存中时，我们必须按照 LRU 算法把最老的数据剔除掉。

当访问第一个数据 A 的时候，因为缓存中还没有任何数据，所以可以直接将 A 放到缓存中。如下图所示：

紧接着应用又访问了 B 和 C，我们按照从左到右由新到旧的顺序来表示缓存中存储的数据，如下图所示：

也就是说在最左边的数据 C 是我们最新放入缓存中的数据，最右边的 A 是我们最早放入缓存中的数据。

当应用需要再次访问 A 的时候，应用不需要去硬盘中读取了，可以直接从缓存中读取，而此时的缓存如下图所示，也就是说，数据 B 变成了最早访问的数据：

此时，应用需要访问数据 D，而缓存中已经保存满了 3 个数据，我们必须将最老的数据剔除，也就是剔除掉 B。现在的缓存如下图所示：

LRU 算法 需要有以下几个操作：

• Get 操作用于获取相应的数据；

• Remove 操作将一个数据从缓存中删除；

• Set 操作用于将相应的数据存放在缓存中，如果缓存空间并未满，则将数据直接存入缓存；如果缓存空间已满，则调用 Remove 操作将最旧的数据从缓存中删除，然后再将新数据存放在缓存中。

那我们要选择哪一种数据结构来表达这个算法好呢？

因为 LRU 算法里有 Get、Set 和 Remove 操作，所以你很快就想到了哈希表这个数据结构，对于哈希表来说，这些操作的时间复杂度是 O(1)。但哈希表的缺点是无法知道数据插入的顺序，这样我们也就无法得知哪个数据是最新的、哪个数据是最旧的。

那链表也许是一个不错的选择，我们可以维护一个头节点指向缓存中最新的数据，尾节点指向缓存中最老的数据。当需要添加新数据而缓存还没有满的时候，可以直接将数据添加到链表头，但这里有一个问题，我们要如何判断这个新数据已经存在于缓存中了呢？需要遍历一遍整个链表，其所需的时间复杂度是 O(N)。

同理，Get 和 Remove 操作同样需要遍历整个链表，平均下来时间复杂度也是 O(N)。这样，我们虽然解决了维护一个从最新使用到最旧的数据问题，但是时间复杂度却提高了。

哈希表和链表的结合

哈希表的值保存了链表节点的位置。因为我们需要记录数据的使用情况，一个常见的操作是将链表中某一个节点数据移动至链表头，所以在这里采用双向链表，从而可以更方便地将链表中的数据移动至链表头。哈希表的作用是可以使查找一个数据的时间复杂度降到 O(1)。

如果应用需要访问数据 B，我们还是需要判断缓存中是否已经保存过这个数据了，通过哈希表可以发现并不存在，而缓存中的数据已经满了，所以需要剔除最旧的数据 A，也就是保存在双向链表链表尾的节点。因为维护了尾节点，我们可以在 O(1) 的时间内找到它，同时将哈希表中的数据也删除掉。现在的尾节点则指向了 D，而链表头则指向了新加入的节点 B，内存如下图所示：

这样的数据结构组合可以将所有的操作时间复杂度都优化到了 O(1)，像 Memcached 和 Nginx 这样反向代理都会使用这种 LRU 算法。

---

整理记录自 《数据结构精讲:从原理到实战》 蔡元楠|硅谷资深工程师

仅做学习参考 侵删…