数据结构

1. 链表

什么是链表？

链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer).

从本质上来讲,链表与数组的确有相似之处,他们的相同点是都是线性数据结构,这与树和图不同,而它们的不同之处在于数组是一块连续的内存,而链表可以不是连续内存,链表的节点与节点之间通过指针来联系.

当然,链表也有不同的形态,主要分为三种:单向链表、双向链表、循环链表.

1.1 单向链表

单向链表的节点通常由两个部分构成,一个是节点储存的 值val,另一个就是节点的 指针next。

链表与数组类似,也可以进行查找、插入、删除、读取等操作,但是由于链表与数组的特性不同,导致不同操作的复杂度也不同.

1.1.1 查找性能

单向链表的查找操作通常是这样的:

• 从头节点进入,开始比对节点的值,如果不同则通过指针进入下一个节点。
• 重复上面的动作,直到找到相同的值,或者节点的指针指向null。

链表的查找性能与数组一样,都是时间复杂度为O(n).

1.1.2 插入删除性能

链表与数组最大的不同就在于删除、插入的性能优势,由于链表是非连续的内存,所以不用像数组一样在插入、删除操作的时候需要进行大面积的成员位移，比如在a、b节点之间插入一个新节点c，链表只需要:

• a断开指向b的指针，将指针指向c。
• c节点将指针指向b，完毕。

这个插入操作仅仅需要移动一下指针即可，插入、删除的时间复杂度只有O(1)。

链表的插入操作如下:

链表的删除操作如下:

1.1.3 读取性能

链表相比之下也有劣势，那就是读取操作远不如数组，数组的读取操作之所以高效，是因为它是一块连续内存，数组的读取可以通过寻址公式快速定位，而链表由于非连续内存，所以必须通过指针一个一个节点遍历.

比如，对于一个数组，我们要读取第三个成员，我们仅需要使用arr[2]就能快速获取成员，而链表则需要从头部节点进入，在通过指针进入后续节点才能读取.

1.1.4 应用场景

由于双向链表的存在，单向链表的应用场景比较少，因为很多场景双向链表更可以出色地完成。但是单向链表并非无用武之地，在以下场景中依然会有单向链表的身影:

1. 撤销功能,这种操作最多见于各种文本、图形编辑器中,撤销重做在编辑器场景下属于家常便饭,单向链表由于良好的删除特性在这个场景很适用
2. 实现图、hashMap等一些高级数据结构

1.2双向链表

我们上文已经提到,单向链表的应用场景并不多,而真正在生产环境中被广泛运用的正是双向链表。

双向链表与单向链表相比有何特殊之处?

我们看到双向链表多了一个新的指针 prev指向节点的前一个节点，当然由于多了一个指针，所以双向链表要更占内存。 别小看双向链表多了一个前置指针，在很多场景里由于多了这个指针，它的效率更高，也更加实用。

比如编辑器的 撤销/重做操作，双向链表就更加适用，由于拥有前后指针，用户可以自由得进行前后操作，如果这个是一个单向链表，那么用户需要遍历链表这时的时间复杂度是O(n)。

1.3 循环链表

循环链表，顾名思义，他就是将单向链表的尾部指针指向了链表头节点:

循环链表一个应用场景就是操作系统的分时问题，比如有一台计算机，但是有多个用户使用，CPU要处理多个用户的请求很可能会出现抢占资源的情况，这个时候计算机会采取分时策略来保证每个用户的使用体验。

1.4 Golang中链表实现

在Golang中有内置的链表实现，该实现位于 SDK 的 container/list 包。

2. 堆

堆就是用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

堆的常用方法：

• 构建优先队列
• 支持堆排序
• 快速找出一个集合中的最小值（或者最大值）

2.1 堆属性

堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。

在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。

例子：

这是一个最大堆，，因为每一个父节点的值都比其子节点要大。10 比 7 和 2 都大。7 比 5 和 1都大。

根据这一属性，那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆，根节点中的元素总是树中的最小值。堆属性非常有用，因为堆常常被当做优先队列使用，因为可以快速地访问到“最重要”的元素。

注意

堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。--唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

2.2 堆和普通树的区别

堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：

• 节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
• 内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。
• 平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。
• 搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

2. 栈

栈（Stack）又叫堆栈，是限定只能在一端进行插入和删除操作的线性表，并且满足后进先出（LIFO）的特点，即最后插入的最先被读取。我们把允许插入和删除的一端叫做栈顶，另一个端叫做栈底，不含任何数据的栈叫做空栈。

栈的概念比较简单，理解起来也不复杂，下面给出一个图示，帮助你形象了解栈的操作流程：

我们将插入操作叫做进栈，读取（删除）操作叫做出栈。

3. 队列

队列和栈一样，队列也是一种特殊的线性表结构，只不过队列是在一端插入，另一端删除，就跟我们平常排队一样的道理，从队尾入队，在队头出去，所以队列的特性是先入先出（FIFO），允许插入的一端叫队尾，允许删除的一端叫队头。

一张图可以形象地体现两者的差别：

和栈一样，队列也可以通过数组和链表实现，通过数组实现的叫顺序队列，通过链表实现的叫做链式队列，栈只需要一个栈顶指针就可以了，因为只允许在栈顶插入删除，但是队列需要两个指针，一个指向队头，一个指向队尾。

4. 哈希表

哈希表（HashTable，也叫散列表），是根据键名（Key）直接访问对应内存存储位置的数据结构。

其实现原理是通过哈希函数（也叫散列函数）将元素的键名映射为数组下标（转化后的值叫做哈希值或散列值），然后在对应下标位置存储记录值。当我们按照键名查询元素时，可以使用同样的哈希函数，将键名转化为数组下标，从对应的数组下标位置读取数据：

显然，哈希表使用了数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，没有数组，就没有哈希表。我们知道，数组访问元素的时间复杂度是 O(1)，所以哈希表也是一样（不考虑哈希函数的复杂度的话），因此非常高效。

此外，我们也可以看到，哈希技术既是一种存储方法，也是一种查找方法。不过，与之前介绍的查找算法不同的是哈希表的不同记录之间不存在逻辑关系，因此最适合求解的问题是查找与给定值相等的记录，而不适合做范围查询。

5. 大数据

5.1 如何从大量的url中找出相同的url?

• 难度系数: ★ ★ ★ ★ ☆

• 被考查系数: ★ ★ ★ ★ ☆

• 题目描述: 给定 a、b 两个文件，各存放 50 亿个 url，每个 url各占 64 个字节，内存限制是4G请找出 a、b 两个文件中共同的 url。

• 分析解答: 由于每个 url 需要占 64 个字节，所以 50 亿个 url 占用空间的大小为 50 亿x64-5Gx64=320G 字节。由于内存大小只有 4G，因此不可能一次性把所有的 rl 都加载到内存中处理。对于这个类型的题目，一般都需要使用分治法，即把一个文件中的 url 按照某-特征分成多个文件，使得每个文件的内容都小于 4G，这样就可以把这个文件一次性读到内存中进行处理了。对于本题而言，主要的实现思路为:

  1. 遍历文件 a，对遍历到的 url 求 hash(url)%500，根据计算结果把遍历到的 url分别存储到 a0,al,a2,..,a499 (计算结果为 i的 url 存储到文件 ai 中)，这样每个文件的大小大约为 600M。当某一个文件中 url 的大小超过 2G 的时候，可以按照类似的思路把这个文件继续分为更小的子文件(例如: 如果 al 大小超过 2G，那么可以把文件继续分成 a11.a12...)。
  2. 使用同样的方法遍历文件 b，把文件 b 中的 url 分别存储到文件 b0,b1,··,b499 中
  3. 通过上面的划分，与 ai 中 url 相同的的 url 一定在 bi 中。由于 ai 与 bi 中所有的 url的大小不会超过 4G，因此可以把它们同时读入到内存中进行处理。具体思路为: 遍历文件ai，把遍历到的 url存入到 hash set 中，接着遍历文件 bi中的 url，如果这个 url在 hash set中存在，那么说明这个 url 是这两个文件共同的 url，可以把这个 url 保存到另外一个单独的文件中。当把文件 a0~a499 都遍历完成后，就找到了两个文件中共同的 url。

5.2 如何从大量数据中找出高频词？

• 难度系数: ★ ★ ★ ★ ☆

• 被考查系数: ★ ★ ★ ★ ★

• 题目描述 有一个 1G 大小的文件，文件里面每一行是一个词，每个词的大小不超过 16 个字节内存大小限制是 1M，要求返回频数最高的 100 个词。

• 分析解答: 由于文件大小为 1G，而内存大小只有 1M，因此不可能一次把所有的词读入到内存中处理，因此也需要采用分治的方法，把一个大的文件分解成多个小的子文件，从而保证每个文件的大小都小于 1M，进而可以直接被读取到内存中处理。具体的思路为:

  1. 遍历文件，对遍历到的每一个词，执行如下 Hash 操作: Hash(x)%2000，将结果为i的词存放到文件 ai 中，通过这个分解步骤，可以使每个子文件的大小大约为 400k，如果这个操作后某个文件的大小超过 1M 了，那么可以采用相同的方法对这个文件继续分解,直到文件的大小小于 1M 为止。
  2. 统计出每个文件中出现频率最高的 100 个词。最简单的方法为使用 map 来实现具体实现方法为，先遍历文件中的所有词，然后对于遍历到的词，如果在 map 中不存在，那么把这个词存入 map 中 (键入这个词，值为 1)，如果这个词在 map 中已经存在了，那么把这个词对应的值加 1。遍历完后可以非常容易地找出出现频率最高的 100 个词。
  3. 第(2) 步找出了每个文件出现频率最高的 100 个词，这一步可以通过维护一个小顶堆来找出所有词中出现频率最高的 100 个。具体方法为，遍历第一个文件，把第一个文件中出现频率最高的 100 个词构建成一个小顶堆 (如果第一个文件中词的个数小于 100,可以继续遍历第 2 个文件，直到构建好有 100 个结点的小顶堆为止)。继续遍历，如果遍历到的词的出现次数大于堆顶上词的出现次数，可以用新遍历到的词替换堆顶的词，然后重新调整这个堆为小顶堆。当遍历完所有文件后,这个小顶堆中的词就是出现频率最高的 100个词。当然这一步也可以采用类似归并排序的方法把所有文件中出现频率最高的 100 个词排序，最终找出出现频率最高的 100 个词。

• 引申:怎么在海量数据中找出重复次数最多的一个? 前面的算法是求解 top100，而这道题目只是求解 topl，可以使用同样的思路来求解。唯一不同的是，在求解出每个文件中出现次数最多的数据后，接下来不需要通过小顶堆来找出出现次数最多的数，只需要使用一个变量就可以完成。方法很简单，此处不再赘述。

5.3 如何找出访问百度最多的IP？

• 难度系数: ★ ★ ★ ★ ☆
• 被考查系数: ★ ★ ★ ★ ★
• 题目描述: 现有海量日志数据保存在一个超级大的文件中，该文件无法直接读入内存，要求从中提取某天访问百度次数最多的那个 IP。
• 分析解答 由于这道题只关心某一天访问百度最多的 IP，因此可以首先对文件进行一次遍历把这一天访问百度的 IP 的相关信息记录到一个单独的文件中。接下来可以用上一节介绍的方法来求解。由于求解思路是一样的，这里就不再详细介绍了。唯一需要确定的是把一个大文件分为几个小文件比较合适。以IP4 为例，由于一个IP 地址占用 32位因此最多会有 2^32=4G 种取值情况。如果使用 hash(IP)%1024，那么把海量 IP 日志分别存储到 1024 个小文件中。这样，每个小文件最多包含 4MB 个 IP 地址。如果使用 2048个小文件，那么每个文件会最多包含 2MB 个 IP 地址。因此，对于这类题目而言，首先需要确定可用内存的大小，然后确定数据的大小。由这两个参数就可以确定 hash 函数应该怎么设置才能保证每个文件的大小都不超过内存的大小，从而可以保证每个小的文件都能被一次性加载到内存中。

5. 4 如何在大量的数据中找出不重复的整数?

• 题目描述 在 2.5 亿个整数中找出不重复的整数，注意，内存不足以容纳这 2.5 亿个整数。
• 分析解答 由于这道题目与前面的题目类似，也是无法一次性把所有数据加载到内存中，因此也可以采用类似的方法求解。
  • 方法一：分冶法 采用 Hash 的方法，把这 2.5 亿个数划分到更小的文件中，从而保证每个文件的大小不超过可用的内存的大小。然后对于每个小文件而言，所有的数据可以一次性被加载到内存中，因此可以使用 hash_map 或 hash_set 来找到每个小文件中不重复的数。当处理完所有的文件后就可以找出这 2.5 亿个整数中所有的不重复的数。
  • 方法二:位图法 对于整数相关的算法的求解，位图法是一种非常实用的算法。对于本题而言，如果可用的内存空间超过 1GB 就可以使用这种方法。具体思路为: 假设整数占用 4 个字节(如果占用 8 个字节，求解思路类似，只不过需要占用更大的内存)，4 个字节也就是 32位，可以表示的整数个数为 2^32。由于本题只查找不重复的数，而不关心具体数字出现的次数，因此可以分别使用 2个 bit 来表示各个数字的状态:用 0 表示这个数字没有出现过，01表示出现过 1次，10 表示出现了多次，11 暂不使用。 根据上面的逻辑，在遍历这 2.5 亿个整数的时候，如果这个整数对应的位图中的位为 00，那么修改成 01，如果为 01 则修改为 10，如果为 10 则保持原值不变。这样当所有数据遍历完成后，可以再遍历一遍位图，位图中为 01 的对应的数字就是没有重复的数字。