算法基础 - 10. 高级数据结构 - 《算法》

1. 位图
2. B+ 树
3. A* 搜索算法

1. 位图

爬虫爬取网页的时候，为了避免重复爬取相同的网页，可以记录已经爬取的网页链接（也就是 URL），在爬取一个新的网页之前，我们拿它的链接，在已经爬取的网页链接列表中搜索，此时可以使用位图加上布隆过滤器来节省内存
假如要爬取 10 亿个网页，为了判重，我们把这 10 亿网页链接存储在散列表中
1. 假设一个 URL 的平均长度是 64 字节，那单纯存储这 10 亿个 URL，需要大约 60GB 的内存空间，因为散列表必须维持较小的装载因子，才能保证不会出现过多的散列冲突，导致操作的性能下降。而且，用链表法解决冲突的散列表，还会存储链表指针。所以，如果将这 10 亿个 URL 构建成散列表，那需要的内存空间会远大于 60GB，有可能会超过 100GB
2. 虽然散列表中添加、查找数据的时间复杂度已经是 O(1)，但是实际并不能反应具体的代码执行时间，因为系数可能比较大，在基于链表的方法来解决冲突问题的时候，当定位当具体的某个链表的时候还需要依次比对每个链表中的 URL。这个操作是比较耗时的
  1. 链表中的结点在内存中不是连续存储的，所以不能一下子加载到 CPU 缓存中，没法很好地利用到 CPU 高速缓存，所以数据访问性能方面会打折扣
  2. 链表中的每个数据都是 URL，而 URL 不是简单的数字，是平均长度为 64 字节的字符串。也就是说，我们要让待判重的 URL，跟链表中的每个 URL，做字符串匹配。显然，这样一个字符串匹配操作，比起单纯的数字比对，要慢很多
位图：当我们有 1 千万个整数，整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢
1. 此时可以使用一种比较“特殊”的散列表，也就是位图。我们申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组。我们将这 1 千万个整数作为数组下标，将对应的数组值设置成 true。
  1. 比如，整数 5 对应下标为 5 的数组值设置为 true，也就是 array[5]=true
  2. 我们查询某个整数 K 是否在这 1 千万个整数中的时候，我们只需要将对应的数组值 array[K]取出来，看是否等于 true。如果等于 true，那说明 1 千万整数中包含这个整数 K；相反，就表示不包含这个整数 K
  3. 此时数字范围在 1 到 1 亿之间，只需要 1 亿个二进制位，也就是 12MB 左右的存储空间就够了 ```java // 使用 char 格式的数组来模拟位图 public class BitMap { // Java中char类型占16bit，也即是2个字节 private char[] bytes; private int nbits;
public BitMap(int nbits) { this.nbits = nbits; this.bytes = new char[nbits/16+1]; }

public void set(int k) { if (k > nbits) return; int byteIndex = k / 16; int bitIndex = k % 16; bytes[byteIndex] |= (1 << bitIndex); }

public boolean get(int k) { if (k > nbits) return false; int byteIndex = k / 16; int bitIndex = k % 16; return (bytes[byteIndex] & (1 << bitIndex)) != 0; } } ```
布隆过滤器：对于位图来说，假如存在 1 千万个范围在 1 到 100 亿的数据，此时就需要 1个 G 以上的内存了，这个时候就可以使用布隆过滤器了
1. 布隆过滤器的做法是，我们仍然使用一个 1 亿个二进制大小的位图，然后通过哈希函数，对数字进行处理，让它落在这 1 到 1 亿范围内。比如我们把哈希函数设计成 f(x)=x%n。其中，x 表示数字，n 表示位图的大小（1 亿），也就是，对数字跟位图的大小进行取模求余
2. 为了降低哈希冲突的概率，可以设计多个哈希函数，对同一个数字进行哈希求值，这样得到多个不同的哈希值，此时分别记作X1，X2，X3，…，XK。我们把这 K 个数字作为位图中的下标，将对应的 BitMap[X1]，BitMap[X2]，BitMap[X3]，…，BitMap[XK]都设置成 true，也就是说，我们用 K 个二进制位，来表示一个数字的存在
3. 当要查询的时候，使用通用的多个哈希函数，进行哈希计算，对得到的多个位置都为 true 的时候，则认为数字存在，否则说明数字不存在（当然多个位置都为 true 的时候，不能百分百保证数字一定存在）
4. 布隆过滤器的误判有一个特点，那就是，它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。不过，只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。
5. 尽管布隆过滤器会存在误判，但是，这并不影响它发挥大作用。很多场景对误判有一定的容忍度。比如爬虫判重这个问题，即便一个没有被爬取过的网页，被误判为已经被爬取，对于搜索引擎来说，也并不是什么大事情，是可以容忍的
  1. 我们用布隆过滤器来记录已经爬取过的网页链接，假设需要判重的网页有 10 亿，那我们可以用一个 10 倍大小的位图来存储，也就是 100 亿个二进制位，换算成字节，那就是大约 1.2GB。之前我们用散列表判重，需要至少 100GB 的空间。相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多。
  2. 布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的。
    1. 而在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的。
    2. 我们知道 CPU 计算可能是要比内存访问更快速的，所以，理论上讲，布隆过滤器的判重方式，更加快速
6. 当布隆过滤器中，数据个数与位图大小的比例超过某个阈值的时候，我们就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中。但是，如果我们要判断某个数据是否在布隆过滤器中已经存在，我们就需要查看多个位图，相应的执行效率就降低了一些
  2. B+ 树
MySql 的索引实现的底层算法，一般的索引为了适应 SQL 查询，需要支持如下操作
1. 根据某个指定值查找数据
2. 根据区间值来查找数据
3. 查找数据的时候正序或逆序获取数据
正常情况下，想要支持以上特性，可以使用 跳表 来支持（其实 B+树 和跳表非常类似），但是 跳表 在数据存储方面不太适合数据库（适用于内存，因此 redis 使用它作为 SortedMap 的底层数据结构）
B+树 和 跳表 非常相似，但是是由二叉查找树改造而来的
1. 为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的（此时很像一个跳表）
3. 对于大批量数据来说，索引会非常大，因此索引基本上都是存储在硬盘上的，对于二叉树来说，数据量很大的适合，每次向下查询都是一次 IO 操作，因此效率相对比较差，此时树的高度就等于每次查询数据时磁盘 IO 操作的次数。
4. 此时可以将索引构造成 m 叉树，那么高度相比二叉树会小很多
  1. 对于一亿个数据构建索引，只要 m = 100 的时候，高度也就只是 3，最多只要 3 次磁盘 IO 就能读取到数据
5. 不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作
对于 B+树 来说，每次更新或删除节点的时候都需要额外考虑下 B+树 的更新，这也是添加数据库索引后，更新数据会变慢的原因所在
1. 对于一个 B+ 树来说，m 值是根据页的大小事先计算好的，也就是说，每个节点最多只能有 m 个子节点
2. 当插入新的节点导致索引中某些节点的子节点个数超过 m，这个节点的大小超过了一个页的大小的时候，需要将这个节点分裂成两个节点，此时它的父节点个数也有可能会超过 m 个（加一了），因此需要向上级联判断。
3. 当然，删除数据的时候，可以设置一个阈值，（一般为 m / 2），当小于这个阈值的时候，会将其和相邻的兄弟节点合并
  1. 如果合并的大小超过 m 的时候，此时可以再次分裂节点
B+树 的特点：
1. 每个节点中子节点的个数不能超过 m，也不能小于 m/2；
2. 根节点的子节点个数可以不超过 m/2，这是一个例外；
3. m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
4. 通过链表将叶子节点串联在一起，这样可以方便按区间查找（为了方法逆序查询，可以是一个双向链表）；
5. 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中（Mysql 查询的时候会将部分已经查询的非叶子节点存储在缓存里面）。
B树 实际上是低级版本的 B+ 树，和 B+树 主要有以下几个不同点
1. B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；
2. B 树中的叶子节点并不需要链表来串联。
B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树（B-树就是 B树，英文翻译的问题，它的翻译是 B-Tree）中间的 - 不是减的意思，只是一个连接符 ```java /**
- 这是B+树非叶子节点的定义。 *
- 假设keywords=[3, 5, 8, 10]
- 4个键值将数据分为5个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
- 5个区间分别对应：children[0]…children[4] *
- m值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
- PAGE_SIZE = (m-1)4[keywordss大小]+m8[children大小] */ public class BPlusTreeNode { public static int m = 5; // 5叉树 public int[] keywords = new int[m-1]; // 键值，用来划分数据区间 public BPlusTreeNode[] children = new BPlusTreeNode[m];//保存子节点指针 }

/**

这是B+树中叶子节点的定义。 *
B+树中的叶子节点跟内部节点是不一样的,
叶子节点存储的是值，而非区间。
这个定义里，每个叶子节点存储3个数据行的键值及地址信息。 *
k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
PAGE_SIZE = k4[keyw..大小]+k8[dataAd..大小]+8[prev大小]+8[next大小] */ public class BPlusTreeLeafNode { public static int k = 3; public int[] keywords = new int[k]; // 数据的键值 public long[] dataAddress = new long[k]; // 数据地址

public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点 public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点 } ```

3. A* 搜索算法

真实的软件开发中，面对超级大的地图或海量的寻路请求，直接使用 Dijkstra 最短路径算法的执行会耗时很多，应为节点太多了，因此在权衡路线规划质量和执行效率的情况下，我们只需要寻求一个次优解就足够了
A*算法 是对 Dijkstra算法 的优化和改造
1. 正常的 Dijkstra算法 里面会对节点的每一个关联节点进行遍历然后找到路径最小的节点，实际场景中，路径最小不代表物理距离最小，有可能是相反方向的，因此 A*算法 对他的改进其实是属于一种启发式搜索算法
2. 启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。这种算法找出的路线，并不是最短路线
  1. 当遍历到某个顶点的时候，从起点走到这个顶点的路径长度是确定的，我们记作 g(i)（i 表示顶点编号）
  2. 可以通过这个顶点跟终点之间的直线距离，也就是欧几里得距离，来近似地估计这个顶点跟终点的路径长度（注意：路径长度跟直线距离是两个概念）。我们把这个距离记作 h(i)（i 表示这个顶点的编号）
    1. 这个函数专业的叫法是启发函数（heuristic function）
    2. 欧几里得距离的计算公式，会涉及比较耗时的开根号计算，所以，我们一般通过另外一个更加简单的距离计算公式，那就是曼哈顿距离（Manhattan distance）。曼哈顿距离是两点之间横纵坐标的距离之和。计算的过程只涉及加减法、符号位反转，所以比欧几里得距离更加高效。
    3. Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y)
  3. 原来只是单纯地通过顶点与起点之间的路径长度 g(i)，来判断谁先出队列，现在有了顶点到终点的路径长度估计值，我们通过两者之和 f(i)=g(i)+h(i)，来判断哪个顶点该最先出队列。
    1. 综合两部分，我们就能有效避免“跑偏”。
    2. 这里 f(i) 的专业叫法是估价函数（evaluation function）
A*算法 和 Dijkstra算法 的代码实现，主要有 3 点区别：
1. 优先级队列构建的方式不同。A* 算法是根据 f 值（ f(i)=g(i)+h(i)）来构建优先级队列，而 Dijkstra 算法是根据 dist 值（g(i)）来构建优先级队列；
2. A* 算法在更新顶点 dist 值的时候，会同步更新 f 值；
3. 循环结束的条件也不一样。Dijkstra 算法是在终点出队列的时候才结束，A* 算法是一旦遍历到终点就结束。 ```java private class Vertex { public int id; // 顶点编号ID public int dist; // 从起始顶点，到这个顶点的距离，也就是g(i) public int f; // 新增：f(i)=g(i)+h(i) public int x, y; // 新增：顶点在地图中的坐标（x, y） public Vertex(int id, int x, int y) { this.id = id; this.x = x; this.y = y; this.f = Integer.MAX_VALUE; this.dist = Integer.MAX_VALUE; } } // Graph类的成员变量，在构造函数中初始化 Vertex[] vertexes = new Vertex[this.v]; // 新增一个方法，添加顶点的坐标 public void addVetex(int id, int x, int y) { vertexes[id] = new Vertex(id, x, y) }

public void astar(int s, int t) { // 从顶点s到顶点t的路径 int[] predecessor = new int[this.v]; // 用来还原路径 // 按照vertex的f值构建的小顶堆，而不是按照dist PriorityQueue queue = new PriorityQueue(this.v); boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列 vertexes[s].dist = 0; vertexes[s].f = 0; queue.add(vertexes[s]); inqueue[s] = true; while (!queue.isEmpty()) { Vertex minVertex = queue.poll(); // 取堆顶元素并删除 for (int i = 0; i < adj[minVertex.id].size(); ++i) { Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边 Vertex nextVertex = vertexes[e.tid]; // minVertex—>nextVertex if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist,f nextVertex.dist = minVertex.dist + e.w; nextVertex.f = nextVertex.dist+hManhattan(nextVertex, vertexes[t]); predecessor[nextVertex.id] = minVertex.id; if (inqueue[nextVertex.id] == true) { queue.update(nextVertex); } else { queue.add(nextVertex); inqueue[nextVertex.id] = true; } } if (nextVertex.id == t) { // 只要到达t就可以结束while了 queue.clear(); // 清空queue，才能推出while循环 break; } } } // 输出路径 System.out.print(s); print(s, t, predecessor); // print函数请参看Dijkstra算法的实现 } ```

10. 高级数据结构

1. 位图

2. B+ 树

3. A* 搜索算法