数据结构与算法

1.概念

数据结构

个人理解：存储组织数据的方式，方便管理使用

例如：一个庞大的图书馆中存放了大量的书籍，我们不仅仅要把书放进入，还应该在合适的时候能够取出来。

图书摆放要使得两个相关操作方便实现：

操作 1：新书怎么插入？
操作 2：怎么找到某本指定的书？

图书各种摆放方式：

方法 1：随便放
- 操作 1：哪里有空位放哪里。
- 操作 2：找某本书，累死。
方法 2：按照书名的拼音字母顺序排放
- 操作 1：新进一本《阿 Q 正传》，按照字母顺序找到位置，插入。
- 操作 2：二分查找法。
方法 3：把书架划分成几块区域，按照类别存放，类别中按照字母顺序
- 操作 1：先定类别，二分查找确定位置，移出空位。
- 操作 2：先定类别，再二分查找。

结论：

解决问题方法的效率，根据数据的组织方式有关。
计算机中存储的数据量相对于图书馆的书籍来说数据量更大，数据更加多。
以什么样的方式，来存储和组织我们的数据才能在使用数据时更加方便呢?
这就是数据结构需要考虑的问题。

常见的数据结构

数组（Aarray）
栈（Stack）
链表（Linked List）
图（Graph）
散列表（Hash）
队列（Queue）
树（Tree）
堆（Heap）

注意：数据结构与算法与语言无关，常见的编程语言都有直接或间接的使用上述常见的数据结构。

算法（Algorithm）的定义

一个有限指令集，每条指令的描述不依赖于语言。
接收一些输入（有些情况下不需要输入）。
产生输出。
一定在有限步骤之后终止。

算法通俗理解

Algorithm 这个单词本意就是解决问题的办法/步骤逻辑。
数据结构的实现，离不开算法。

算法案例

假如上海和杭州之间有一条高架线，高架线长度是 1,000,000 米，有一天高架线中有其中一米出现了故障，请你想出一种算法，可以快速定位到处问题的地方。

线性查找
- 从上海的起点开始一米一米的排查，最终一定能找到出问题的线段。
- 但是如果线段在另一头，我们需要排查 1,000,000 次，这是最坏的情况，平均需要 500,000 次。
二分查找
- 从中间位置开始排查，看一下问题出在上海到中间位置，还是中间到杭州的位置。
- 查找对应的问题后，再从中间位置分开，重新锁定一般的路程。
- 最坏的情况，需要多少次可以排查完呢? 最坏的情况是 20 次就可以找到出问题的地方。
- 怎么计算出来的呢? log(1000000, 2)，以 2 位底，1000000 的对数 ≈ 20。

结论：你会发现，解决问题的办法有很多，但是好的算法对比于差的算法，效率天壤之别。

时间复杂度

一个函数，用O()表示如果O(1)、O(n)、O(logN)、O(n^2)…

定性描述该算法的运行时间（大概）

空间复杂度

一个函数，用O()表示，比如O(1)、O(n)、O(n^2)…

算法在运行中临时占用储存空间大小的量度

2.数据结构

2.1数组（array)

几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。

数组是一个线性结构，可以在数组的任意位置插入和删除元素。固定，要扩容数组

数组通常情况下用于存储一系列同一种数据类型的值。但在 JavaScript 里，数组中可以保存不同类型的值。但我们还是要遵守最佳实践，别这么做（大多数语言都没这个能力）。

原生的数组插入删除数据等比较慢，比如7要插进1和2中间时，6要一个个往后靠，效率很慢

遍历很快，通过下标直接找到元素

2.2栈

数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。但是有时候，我们为了实现某些功能，必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。

栈（stack）是种运算受限的线性表：

LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间。类似于自动餐托盘，最后放上的托盘，往往先把拿出去使用。
其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

如下图所示：

栈的特点：先进后出，后进先出。

程序中的栈结构

函数调用栈：A(B(C(D())))：即 A 函数中调用 B，B 调用 C，C 调用 D；在 A 执行的过程中会将 A 压入栈，随后 B 执行时 B 也被压入栈，函数 C 和 D 执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D（栈顶）；函数 D 执行完之后，会弹出栈被释放，弹出栈的顺序为 D->C->B->A;
递归：为什么没有停止条件的递归会造成栈溢出？比如函数 A 为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数 A 压入栈，最后造成栈溢出（Queue Overfloat）。

练习

题目：有 6 个元素 6，5，4，3，2，1 按顺序进栈，问下列哪一个不是合法的出栈顺序？

A：5 4 3 6 1 2 （√）
B：4 5 3 2 1 6 （√）
C：3 4 6 5 2 1 （×）
D：2 3 4 1 5 6 （√）

题目所说的按顺序进栈指的不是一次性全部进栈，而是有进有出，进栈顺序为 6 -> 5 -> 4 -> 3 -> 2 -> 1。

解析：

A 答案：65 进栈，5 出栈，4 进栈出栈，3 进栈出栈，6 出栈，21 进栈，1 出栈，2 出栈（整体入栈顺序符合 654321）。
B 答案：654 进栈，4 出栈，5 出栈，3 进栈出栈，2 进栈出栈，1 进栈出栈，6 出栈（整体的入栈顺序符合 654321）。
C 答案：6543 进栈，3 出栈，4 出栈，之后应该 5 出栈而不是 6，所以错误。
D 答案：65432 进栈，2 出栈，3 出栈，4 出栈，1 进栈出栈，5 出栈，6 出栈。符合入栈顺序。

栈结构实现

栈常见的操作

push() 添加一个新元素到栈顶位置。
pop() 移除栈顶的元素，同时返回被移除的元素。
peek() 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。
isEmpty() 如果栈里没有任何元素就返回 true，否则返回 false。
size() 返回栈里的元素个数。这个方法和数组的 length 属性类似。
toString() 将栈结构的内容以字符串的形式返回。

JavaScript 代码实现栈结构

// 栈结构的封装
class Map {
  constructor() {
    this.items = [];
  }

  // push(item) 压栈操作，往栈里面添加元素
  push(item) {
    this.items.push(item);
  }

  // pop() 出栈操作，从栈中取出元素，并返回取出的那个元素
  pop() {
    return this.items.pop();
  }

  // peek() 查看栈顶元素
  peek() {
    return this.items[this.items.length - 1];
  }

  // isEmpty() 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // size() 获取栈中元素个数
  size() {
    return this.items.length;
  }

  // toString() 返回以字符串形式的栈内元素数据
  toString() {
    let result = "";
    for (let item of this.items) {
      result += item + " ";
    }
    return result;
  }
}

2.3队列

认识队列

队列（Queue）是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)

受限之处：

只允许在表的前端（front）进行删除操作。
只允许在表的后端（rear）进行插入操作。

生活中类似队列结构的场景：

排队，比如在电影院，商场，甚至是厕所排队。
优先排队的人，优先处理。 (买票、结账、WC)。

队列在程序中的应用

打印队列：计算机打印多个文件的时候，需要排队打印。
线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待 CPU 处理。

2.3 链表

链表和数组

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。

数组

存储多个元素，数组（或列表）可能是最常用的数据结构。
几乎每一种编程语言都有默认实现数组结构，提供了一个便利的 [] 语法来访问数组元素。
数组缺点：

数组的创建需要申请一段连续的内存空间(一整块内存)，并且大小是固定的，当前数组不能满足容量需求时，需要扩容。 (一般情况下是申请一个更大的数组，比如 2 倍，然后将原数组中的元素复制过去)

在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。

链表

存储多个元素，另外一个选择就是使用链表。
不同于数组，链表中的元素在内存中不必是连续的空间。
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。
链表优点：

内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。

链表不必在创建时就确定大小，并且大小可以无限延伸下去。

链表在插入和删除数据时，时间复杂度可以达到 O(1)，相对数组效率高很多。
链表缺点：

访问任何一个位置的元素时，需要从头开始访问。(无法跳过第一个元素访问任何一个元素)

无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。

虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。

单向链表类似于火车，有一个火车头，火车头会连接一个节点，节点上有乘客，并且这个节点会连接下一个节点，以此类推。

链表的火车结构
链表的数据结构

head 属性指向链表的第一个节点。链表中的最后一个节点指向 null。当链表中一个节点也没有的时候，head 直接指向 null。
给火车加上数据后的结构

链表中的常见操作

append(element) 向链表尾部添加一个新的项。
insert(position, element) 向链表的特定位置插入一个新的项。
get(position) 获取对应位置的元素。
indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回-1。
update(position, element) 修改某个位置的元素。
removeAt(position) 从链表的特定位置移除一项。
remove(element) 从链表中移除一项。
isEmpty() 如果链表中不包含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
size() 返回链表包含的元素个数，与数组的 length 属性类似。
toString() 由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

单向链表

只能从头遍历到尾或者从尾遍历到头（一般从头到尾）。
链表相连的过程是单向的，实现原理是上一个节点中有指向下一个节点的引用。
单向链表有一个比较明显的缺点：可以轻松到达下一个节点，但回到前一个节点很难，在实际开发中, 经常会遇到需要回到上一个节点的情况。

双向链表

既可以从头遍历到尾，也可以从尾遍历到头。
链表相连的过程是双向的。实现原理是一个节点既有向前连接的引用，也有一个向后连接的引用。
双向链表可以有效的解决单向链表存在的问题。
双向链表缺点：
- 每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些。
- 相对于单向链表，所占内存空间更大一些。
- 但是，相对于双向链表的便利性而言，这些缺点微不足道。

双向链表结构

双向链表不仅有 head 指针指向第一个节点，而且有 tail 指针指向最后一个节点。
每一个节点由三部分组成：item 储存数据、prev 指向前一个节点、next 指向后一个节点。
双向链表的第一个节点的 prev 指向 null。
双向链表的最后一个节点的 next 指向 null。

双向链表常见的操作

append(element) 向链表尾部追加一个新元素。
insert(position, element) 向链表的指定位置插入一个新元素。
getElement(position) 获取指定位置的元素。
indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
update(position, element) 修改指定位置上的元素。
removeAt(position) 从链表中的删除指定位置的元素。
remove(element) 从链表删除指定的元素。
isEmpty() 如果链表中不包含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
size() 返回链表包含的元素个数，与数组的 length 属性类似。
toString() 由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
forwardString() 返回正向遍历节点字符串形式。
backwordString() 返回反向遍历的节点的字符串形式。

2.4集合

几乎每种编程语言中，都有集合结构。集合比较常见的实现方式是哈希表，这里使用 JavaScript 的 Object 进行封装。

集合特点

集合通常是由一组无序的、不能重复的元素构成。
数学中常指的集合中的元素是可以重复的，但是计算机中集合的元素不能重复。
集合是特殊的数组。
- 特殊之处在于里面的元素没有顺序，也不能重复。
- 没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份。

封装集合

ES6 中的 Set 就是一个集合类，这里我们重新封装一个 Set 类，了解集合的底层实现。

集合常见的操作

add(value) 向集合添加一个新的项。
remove(value) 从集合移除一个值。
has(value) 如果值在集合中，返回 true，否则返回 false。
clear() 移除集合中的所有项。
size() 返回集合所包含元素的数量。与数组的 length 属性类似。
values() 返回一个包含集合中所有值的数组。
还有其他的方法，用的不多，这里不做封装。

集合转数组 […new Set()]，集合key和value是一样的

2.5字典

字典特点

字典存储的是键值对，主要特点是一一对应。
比如保存一个人的信息
- 数组形式：[19,"Tom", 1.65]，可通过下标值取出信息。
- 字典形式：{"age": 19, "name": "Tom", "height": 165}，可以通过 key 取出 value。
此外，在字典中 key 是不能重复且无序的，而 Value 可以重复。

字典和映射的关系

有些编程语言中称这种映射关系为字典，如 Swift 中的 Dictonary，Python 中的 dict。
有些编程语言中称这种映射关系为 Map，比如 Java 中的 HashMap 和 TreeMap 等。

字典常见的操作

set(key,value) 向字典中添加新元素。
remove(key) 通过使用键值来从字典中移除键值对应的数据值。
has(key) 如果某个键值存在于这个字典中，则返回 true，反之则返回 false。
get(key) 通过键值查找特定的数值并返回。
clear() 将这个字典中的所有元素全部删除。
size() 返回字典所包含元素的数量。与数组的 length 属性类似。
keys() 将字典所包含的所有键名以数组形式返回。
values() 将字典所包含的所有数值以数组形式返回。

2.6哈希表

认识哈希表

哈希表是一种非常重要的数据结构，几乎所有的编程语言都直接或者间接应用这种数据结构。

哈希表通常是基于数组实现的，但是相对于数组，它存在更多优势：

哈希表可以提供非常快速的 插入-删除-查找 操作。
无论多少数据，插入和删除值都只需接近常量的时间，即 O(1) 的时间复杂度。实际上，只需要几个机器指令即可完成。
哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。
哈希表相对于树来说编码要简单得多。

哈希表同样存在不足之处：

哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。
通常情况下，哈希表中的 key 是不允许重复的，不能放置相同的 key，用于保存不同的元素。

哈希表是什么？

哈希表并不好理解，不像数组、链表和树等可通过图形的形式表示其结构和原理。
哈希表的结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取 HashCode。

通过以下案例了解哈希表：

案例一：公司想要存储 1000 个人的信息，每一个工号对应一个员工的信息。若使用数组，增删数据时比较麻烦；使用链表，获取数据时比较麻烦。有没有一种数据结构，能把某一员工的姓名转换为它对应的工号，再根据工号查找该员工的完整信息呢？没错此时就可以使用哈希表的哈希函数来实现。
案例二：存储联系人和对应的电话号码：当要查找张三（比如）的号码时，若使用数组：由于不知道存储张三数据对象的下标值，所以查找起来十分麻烦，使用链表时也同样麻烦。而使用哈希表就能通过哈希函数把张三这个名称转换为它对应的下标值，再通过下标值查找效率就非常高了。

也就是说：哈希表最后还是基于数据来实现的，只不过哈希表能够通过哈希函数把字符串转化为对应的下标值，建立字符串和下标值的映射关系。

认识哈希化

为了把字符串转化为对应的下标值，需要有一套编码系统，为了方便理解我们创建这样一套编码系统：比如 a 为 1，b 为 2，c 为 3，以此类推 z 为 26，空格为 27（不考虑大写情况）。

有了编码系统后，将字母转化为数字也有很多种方案：

方案一：数字相加。

例如 cats 转化为数字：3 + 1 + 20 + 19 = 43，那么就把 43 作为 cats 单词的下标值储存在数组中；

但是这种方式会存在这样的问题：很多的单词按照该方式转化为数字后都是 43，比如 was。而在数组中一个下标值只能储存一个数据，所以该方式不合理。

方案二：幂的连乘。

我们平时使用的大于 10 的数字，就是用幂的连乘来表示它的唯一性的。比如： 6543 = 6 * 10^3 + 5 * 10^2 + 4 * 10 + 3；这样单词也可以用该种方式来表示：cats = 3 * 27^3 + 1 * 27^2 + 20 * 27 + 17 = 60337。

虽然该方式可以保证字符的唯一性，但是如果是较长的字符（如 aaaaaaaaaa）所表示的数字就非常大，此时要求很大容量的数组，然而其中却有许多下标值指向的是无效的数据（比如不存在 zxcvvv 这样的单词），造成了数组空间的浪费。

两种方案总结：

第一种方案（让数字相加求和）产生的数组下标太少。
第二种方案（与 27 的幂相乘求和）产生的数组下标又太多。

现在需要一种压缩方法，把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。可以通过取余操作来实现。虽然取余操作得到的结构也有可能重复，但是可以通过其他方式解决。

哈希表的一些概念

哈希化

将大数字转化成数组范围内下标的过程，称之为哈希化。
哈希函数

我们通常会将单词转化成大数字，把大数字进行哈希化的代码实现放在一个函数中，该函数就称为哈希函数。
哈希表

对最终数据插入的数组进行整个结构的封装，得到的就是哈希表。

地址的冲突

在实际中，经过哈希函数哈希化过后得到的下标值可能有重复，这种情况称为冲突，冲突是不可避免的，我们只能解决冲突。

解决冲突常见的两种方案：链地址法（拉链法）和开放地址法。

链地址法（拉链法）

如下图所示，我们将每一个数字都对 10 进行取余操作，则余数的范围 0~9 作为数组的下标值。并且，数组每一个下标值对应的位置存储的不再是一个数字了，而是存储由经过取余操作后得到相同余数的数字组成的数组或链表。

这样可以根据下标值获取到整个数组或链表，之后继续在数组或链表中查找就可以了。而且，产生冲突的元素一般不会太多。

总结：链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据，而是一条链条，这条链条常使用的数据结构为数组或链表，两种数据结构查找的效率相当（因为链条的元素一般不会太多）。

开放地址法

开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项。

根据探测空白单元格位置方式的不同，可分为三种方法：

线性探测
二次探测
再哈希法

线性探测

当插入 13 时：

经过哈希化（对 10 取余）之后得到的下标值 index=3，但是该位置已经放置了数据 33。而线性探测就是从 index 位置+1 开始向后一个一个来查找合适的位置来放置 13，所谓合适的位置指的是空的位置，如上图中 index=4 的位置就是合适的位置。

当查询 13 时：
- 首先 13 经过哈希化得到 index=3，如果 index=3 的位置存放的数据与需要查询的数据 13 相同，就直接返回；不相同时，则线性查找，从 index+1 位置开始一个一个位置地查找数据 13。
- 查询过程中不会遍历整个哈希表，只要查询到空位置，就停止，因为插入 13 时不会跳过空位置去插入其他位置。
当删除 13 时：
- 删除操作和上述两种情况类似，但需要注意的是，删除一个数据项时，不能将该位置下标的内容设置为 null，否则会影响到之后其他的查询操作，因为一遇到为 null 的位置就会停止查找。
- 通常删除一个位置的数据项时，我们可以将它进行特殊处理（比如设置为-1），这样在查找时遇到-1 就知道要继续查找。

线性探测存在的问题：

线性探测存在一个比较严重的问题，就是聚集。
如哈希表中还没插入任何元素时，插入 23、24、25、26、27，这就意味着下标值为 3、4、5、6、7 的位置都放置了数据，这种一连串填充单元就称为聚集。
聚集会影响哈希表的性能，无论是插入/查询/删除都会影响。
比如插入 13 时就会发现，连续的单元 3~7 都不允许插入数据，并且在插入的过程中需要经历多次这种情况。二次探测法可以解决该问题。

二次探测

上文所说的线性探测存在的问题：

如果之前的数据是连续插入的，那么新插入的一个数据可能需要探测很长的距离；

二次探测是在线性探测的基础上进行了优化：
线性探测：我们可以看成是步长为 1 的探测，比如从下表值 x 开始，那么线性探测就是按照下标值：x+1、x+2、x+3 等依次探测；
二次探测：对步长进行了优化，比如从下标值 x 开始探测：x+1^2^、x+2^2^、x+3^3^ 。这样一次性探测比较长的距离，避免了数据聚集带来的影响。
二次探测存在的问题：

当插入数据分布性较大的一组数据时，比如：13-163-63-3-213，这种情况会造成步长不一的一种聚集（虽然这种情况出现的概率较线性探测的聚集要小），同样会影响性能。

再哈希法

在开放地址法中寻找空白单元格的最好的解决方式为再哈希化。

二次探测的步长是固定的：1，4，9，16 依次类推。
现在需要一种方法：产生一种依赖关键字(数据)的探测序列，而不是每个关键字探测步长都一样。
这样，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。
再哈希法的做法为：把关键字用另一个哈希函数，再做一次哈希化，用这次哈希化的结果作为该关键字的步长。

第二次哈希化需要满足以下两点：

和第一个哈希函数不同，不然哈希化后的结果仍是原来位置；
不能输出为 0，否则每次探测都是原地踏步的死循环；

优秀的哈希函数：

stepSize = constant - （key % constant）；
其中 constant 是质数，且小于数组的容量；
例如：stepSize = 5 - （key % 5），满足需求，并且结果不可能为 0；

哈希化的效率

哈希表中执行插入和搜索操作效率是非常高的。

如果没有发生冲突，那么效率就会更高；
如果发生冲突，存取时间就依赖后来的探测长度；
平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度会越来越长。

装填因子

装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值；
装填因子 = 总数据项 / 哈希表长度；
开放地址法的装填因子最大为 1，因为只有空白的单元才能放入元素；
链地址法的装填因子可以大于 1，因为只要愿意，拉链法可以无限延伸下去；

不同探测方式性能的比较

线性探测

可以看到，随着装填因子的增大，平均探测长度呈指数形式增长，性能较差。实际情况中，最好的装填因子取决于存储效率和速度之间的平衡，随着装填因子变小，存储效率下降，而速度上升。
二次探测和再哈希化的性能

二次探测和再哈希法性能相当，它们的性能比线性探测略好。由下图可知，随着装填因子的变大，平均探测长度呈指数形式增长，需要探测的次数也呈指数形式增长，性能不高。
链地址法的性能

可以看到随着装填因子的增加，平均探测长度呈线性增长，较为平缓。在开发中使用链地址法较多，比如 Java 中的 HashMap 中使用的就是链地址法。
哈希函数

哈希表的优势在于它的速度，所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法。

性能高的哈希函数应具备以下两个优点：
- 快速的计算；
- 均匀的分布；
快速计算

霍纳法则：在中国霍纳法则也叫做秦久韶算法，具体算法为：

求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值。这种算法把求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值。
- 变换之前：
  - 乘法次数：n(n+1)/2 次；
  - 加法次数：n 次；
- 变换之后：
  - 乘法次数：n 次；
  - 加法次数：n 次；
如果使用大 O 表示时间复杂度的话，直接从变换前的 O(N^2)降到了 O(N)。

均匀分布

在设计哈希表时，我们已经有办法处理映射到相同下标值的情况：链地址法或者开放地址法。但是，为了提供效率，最好的情况还是让数据在哈希表中均匀分布。因此，我们需要在使用常量的地方，尽量使用质数。比如：哈希表的长度、N 次幂的底数等。

Java 中的 HashMap 采用的是链地址法，哈希化采用的是公式为：index = HashCode(key) & (Length-1) 即将数据化为二进制进行与运算，而不是取余运算。这样计算机直接运算二进制数据，效率更高。但是 JavaScript 在进行较大数据的与运算时会出现问题，所以我们使用 JavaScript 实现哈希化时采用取余运算。

哈希表常见操作

put(key, value) 插入或修改操作。
get(key) 获取哈希表中特定位置的元素。
remove(key) 删除哈希表中特定位置的元素。
isEmpty() 如果哈希表中不包含任何元素，返回 trun，如果哈希表长度大于 0 则返回 false。
size() 返回哈希表包含的元素个数。
resize(value) 对哈希表进行扩容操作。

2.7树

什么是树？

真实的树：

树的特点：

树一般都有一个根，连接着根的是树干；
树干会发生分叉，形成许多树枝，树枝会继续分化成更小的树枝；
树枝的最后是叶子；

现实生活中很多结构都是树的抽象，模拟的树结构相当于旋转 180° 的树。

树结构对比于数组/链表/哈希表有哪些优势呢？

数组：

优点：可以通过下标值访问，效率高；
缺点：查找数据时需要先对数据进行排序，生成有序数组，才能提高查找效率；并且在插入和删除元素时，需要大量的位移操作；

链表：

优点：数据的插入和删除操作效率都很高；
缺点：查找效率低，需要从头开始依次查什么是树？

真实的树：

树的特点：
- 树一般都有一个根，连接着根的是树干；
- 树干会发生分叉，形成许多树枝，树枝会继续分化成更小的树枝；
- 树枝的最后是叶子；
现实生活中很多结构都是树的抽象，模拟的树结构相当于旋转 180° 的树。

树结构对比于数组/链表/哈希表有哪些优势呢？

数组：
- 优点：可以通过下标值访问，效率高；
- 缺点：查找数据时需要先对数据进行排序，生成有序数组，才能提高查找效率；并且在插入和删除元素时，需要大量的位移操作；
链表：
- 优点：数据的插入和删除操作效率都很高；
- 缺点：查找效率低，需要从头开始依次查找，直到找到目标数据为止；当需要在链表中间位置插入或删除数据时，插入或删除的效率都不高。
哈希表：
- 优点：哈希表的插入/查询/删除效率都非常高；
- 缺点：空间利用率不高，底层使用的数组中很多单元没有被利用；并且哈希表中的元素是无序的，不能按照固定顺序遍历哈希表中的元素；而且不能快速找出哈希表中最大值或最小值这些特殊值。
树结构：
- 优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等。
总的来说：每种数据结构都有自己特定的应用场景。

树结构：

树（Tree）：由 n（n ≥ 0）个节点构成的有限集合。当 n = 0 时，称为空树。
对于任意一棵非空树（n > 0），它具备以下性质：
- 数中有一个称为根（Root）的特殊节点，用 r 表示；
- 其余节点可分为 m（m > 0）个互不相交的有限集合 T1，T2，…，Tm，其中每个集合本身又是一棵树，称为原来树的子树（SubTree）。

树的常用术语：

节点的度（Degree）：节点的子树个数，比如节点 B 的度为 2；
树的度：树的所有节点中最大的度数，如上图树的度为 2；
叶节点（Leaf）：度为 0 的节点（也称为叶子节点），如上图的 H，I 等；
父节点（Parent）：度不为 0 的节点称为父节点，如上图节点 B 是节点 D 和 E 的父节点；
子节点（Child）：若 B 是 D 的父节点，那么 D 就是 B 的子节点；
兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点，比如上图的 B 和 C，D 和 E 互为兄弟节点；
路径和路径长度：路径指的是一个节点到另一节点的通道，路径所包含边的个数称为路径长度，比如 A->H 的路径长度为 3；
节点的层次（Level）：规定根节点在 1 层，其他任一节点的层数是其父节点的层数加 1。如 B 和 C 节点的层次为 2；
树的深度（Depth）：树种所有节点中的最大层次是这棵树的深度，如上图树的深度为 4；

树结构的表示方式

最普通的表示方法：

如图，树结构的组成方式类似于链表，都是由一个个节点连接构成。不过，根据每个父节点子节点数量的不同，每一个父节点需要的引用数量也不同。比如节点 A 需要 3 个引用，分别指向子节点 B，C，D；B 节点需要 2 个引用，分别指向子节点 E 和 F；K 节点由于没有子节点，所以不需要引用。

这种方法缺点在于我们无法确定某一结点的引用数。

儿子-兄弟表示法：

这种表示方法可以完整地记录每个节点的数据，比如：

//节点A
Node{
  //存储数据
  this.data = data
  //统一只记录左边的子节点
  this.leftChild = B
  //统一只记录右边的第一个兄弟节点
  this.rightSibling = null
}

//节点B
Node{
  this.data = data
  this.leftChild = E
  this.rightSibling = C
}

//节点F
Node{
  this.data = data
  this.leftChild = null
  this.rightSibling = null
}

这种表示法的优点在于每一个节点中引用的数量都是确定的。

儿子-兄弟表示法旋转

以下为儿子-兄弟表示法组成的树结构：

将其顺时针旋转 45° 之后：

这样就成为了一棵二叉树，由此我们可以得出结论：任何树都可以通过二叉树进行模拟。但是这样父节点不是变了吗？其实，父节点的设置只是为了方便指向子节点，在代码实现中谁是父节点并没有关系，只要能正确找到对应节点即可。

2.8二叉树

如果树中的每一个节点最多只能由两个子节点，这样的树就称为二叉树；

二叉树的组成

二叉树可以为空，也就是没有节点；
若二叉树不为空，则它由根节点和称为其左子树 TL 和右子树 TR 的两个不相交的二叉树组成；

二叉树的五种形态

上图分别表示：空的二叉树、只有一个节点的二叉树、只有左子树 TL 的二叉树、只有右子树 TR 的二叉树和有左右两个子树的二叉树。

二叉树的特性

一个二叉树的第 i 层的最大节点树为：2^(i-1)^，i >= 1；
深度为 k 的二叉树的最大节点总数为：2^k^ - 1 ，k >= 1；
对任何非空二叉树，若 n0 表示叶子节点的个数，n2表示度为 2 的非叶子节点个数，那么两者满足关系：n0 = n2 + 1；如下图所示：H，E，I，J，G 为叶子节点，总数为 5；A，B，C，F 为度为 2 的非叶子节点，总数为 4；满足 n0 = n2 + 1 的规律。

特殊的二叉树

完美二叉树

完美二叉树（Perfect Binary Tree）也成为满二叉树（Full Binary Tree），在二叉树中，除了最下一层的叶子节点外，每层节点都有 2 个子节点，这就构成了完美二叉树。

完全二叉树

完全二叉树（Complete Binary Tree）:

除了二叉树最后一层外，其他各层的节点数都达到了最大值；
并且，最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点；
完美二叉树是特殊的完全二叉树；

在上图中，由于 H 缺失了右子节点，所以它不是完全二叉树。

二叉树的数据存储

常见的二叉树存储方式为数组和链表：

使用数组

完全二叉树：按从上到下，从左到右的方式存储数据。

节点	A	B	C	D	E	F	G	H	I
序号	1	2	3	4	5	6	7	8	9

使用数组存储时，取数据的时候也十分方便：左子节点的序号等于父节点序号 _ 2，右子节点的序号等于父节点序号 _ 2 + 1 。

非完全二叉树：非完全二叉树需要转换成完全二叉树才能按照上面的方案存储，这样会浪费很大的存储空间。

节点	A	B	C	^	^	F	^	^	^	^	^	^	M
序号	1	2	3	4	5	6	7	8	9	10	11	12	13

使用链表

二叉树最常见的存储方式为链表：每一个节点封装成一个 Node，Node 中包含存储的数据、左节点的引用和右节点的引用。

2.9二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称为二叉排序树和二叉查找树。

二叉搜索树是一棵二叉树，可以为空。

如果不为空，则满足以下性质：

条件 1：非空左子树的所有键值小于其根节点的键值。比如三中节点 6 的所有非空左子树的键值都小于 6；
条件 2：非空右子树的所有键值大于其根节点的键值；比如三中节点 6 的所有非空右子树的键值都大于 6；
条件 3：左、右子树本身也都是二叉搜索树；

如上图所示，树二和树三符合 3 个条件属于二叉树，树一不满足条件 3 所以不是二叉树。

总结：二叉搜索树的特点主要是较小的值总是保存在左节点上，相对较大的值总是保存在右节点上。这种特点使得二叉搜索树的查询效率非常高，这也就是二叉搜索树中“搜索”的来源。

二叉搜索树应用举例

下面是一个二叉搜索树：

若想在其中查找数据 10，只需要查找 4 次，查找效率非常高。

第 1 次：将 10 与根节点 9 进行比较，由于 10 > 9，所以 10 下一步与根节点 9 的右子节点 13 比较；
第 2 次：由于 10 < 13，所以 10 下一步与父节点 13 的左子节点 11 比较；
第 3 次：由于 10 < 11，所以 10 下一步与父节点 11 的左子节点 10 比较；
第 4 次：由于 10 = 10，最终查找到数据 10 。

同样是 15 个数据，在排序好的数组中查询数据 10，需要查询 10 次：

其实：如果是排序好的数组，可以通过二分查找：第一次找 9，第二次找 13，第三次找 15…。我们发现如果把每次二分的数据拿出来以树的形式表示的话就是二叉搜索树。这就是数组二分法查找效率之所以高的原因。

二叉搜索树的封装

二叉搜索树有四个最基本的属性：指向节点的根（root），节点中的键（key）、左指针（right）、右指针（right）。

所以，二叉搜索树中除了定义 root 属性外，还应定义一个节点内部类，里面包含每个节点中的 left、right 和 key 三个属性。

// 节点类
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

二叉搜索树的常见操作：

insert(key) 向树中插入一个新的键。
search(key) 在树中查找一个键，如果节点存在，则返回 true；如果不存在，则返回 false。
preOrderTraverse 通过先序遍历方式遍历所有节点。
inOrderTraverse 通过中序遍历方式遍历所有节点。
postOrderTraverse 通过后序遍历方式遍历所有节点。
min 返回树中最小的值/键。
max 返回树中最大的值/键。
remove(key) 从树中移除某个键。

插入数据

实现思路：

首先根据传入的 key 创建节点对象。
然后判断根节点是否存在，不存在时通过：this.root = newNode，直接把新节点作为二叉搜索树的根节点。
若存在根节点则重新定义一个内部方法 insertNode() 用于查找插入点。

insert(key) 代码实现

// insert(key) 插入数据
insert(key) {
  const newNode = new Node(key);

  if (this.root === null) {
    this.root = newNode;
  } else {
    this.insertNode(this.root, newNode);
  }

}

insertNode() 的实现思路:

根据比较传入的两个节点，一直查找新节点适合插入的位置，直到成功插入新节点为止。

当 newNode.key < node.key 向左查找:
- 情况 1：当 node 无左子节点时，直接插入：
- 情况 2：当 node 有左子节点时，递归调用 insertNode()，直到遇到无左子节点成功插入 newNode 后，不再符合该情况，也就不再调用 insertNode()，递归停止。
当 newNode.key >= node.key 向右查找，与向左查找类似：
- 情况 1：当 node 无右子节点时，直接插入：
- 情况 2：当 node 有右子节点时，依然递归调用 insertNode()，直到遇到传入 insertNode 方法的 node 无右子节点成功插入 newNode 为止。

insertNode(root, node) 代码实现

insertNode(root, node) {

  if (node.key < root.key) { // 往左边查找插入

    if (root.left === null) {
      root.left = node;
    } else {
      this.insertNode(root.left, node);
    }

  } else { // 往右边查找插入

    if (root.right === null) {
      root.right = node;
    } else {
      this.insertNode(root.right, node);
    }

  }

}

遍历数据

这里所说的树的遍历不仅仅针对二叉搜索树，而是适用于所有的二叉树。由于树结构不是线性结构，所以遍历方式有多种选择，常见的三种二叉树遍历方式为：

先序遍历；
中序遍历；
后序遍历；

还有层序遍历，使用较少。

先序遍历

先序遍历的过程为：

首先，遍历根节点；然后，遍历其左子树；最后，遍历其右子树；

如上图所示，二叉树的节点遍历顺序为：A -> B -> D -> H -> I -> E -> C -> F -> G。

代码实现：

// 先序遍历（根左右 DLR）
preorderTraversal() {
  const result = [];
  this.preorderTraversalNode(this.root, result);
  return result;
}

preorderTraversalNode(node, result) {
  if (node === null) return result;
  result.push(node.key);
  this.preorderTraversalNode(node.left, result);
  this.preorderTraversalNode(node.right, result);
}

中序遍历

实现思路：与先序遍历原理相同，只不过是遍历的顺序不一样了。

首先，遍历其左子树；然后，遍历根（父）节点；最后，遍历其右子树；

过程图解：

输出节点的顺序应为：3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 18 -> 20 -> 25

// 中序遍历（左根右 LDR）
inorderTraversal() {
  const result = [];
  this.inorderTraversalNode(this.root, result);
  return result;
}

inorderTraversalNode(node, result) {
  if (node === null) return result;
  this.inorderTraversalNode(node.left, result);
  result.push(node.key);
  this.inorderTraversalNode(node.right, result);
}

后序遍历

实现思路：与先序遍历原理相同，只不过是遍历的顺序不一样了。

首先，遍历其左子树；然后，遍历其右子树；最后，遍历根（父）节点；

过程图解：

输出节点的顺序应为：3 -> 6 -> 5 -> 8 -> 10 -> 9 -> 7 -> 12 -> 14 -> 13 -> 18 -> 25 -> 20 -> 15 -> 11 。

代码实现：

// 后序遍历（左右根 LRD）
postorderTraversal() {
  const result = [];
  this.postorderTraversalNode(this.root, result);
  return result;
}

postorderTraversalNode(node, result) {
  if (node === null) return result;
  this.postorderTraversalNode(node.left, result);
  this.postorderTraversalNode(node.right, result);
  result.push(node.key);
}

查找最大值或最小值

在二叉搜索树中查找最值非常简单，最小值在二叉搜索树的最左边，最大值在二叉搜索树的最右边。只需要一直向左/右查找就能得到最值，如下图所示：

代码实现：

// min() 获取二叉搜索树最小值
min() {
  if (!this.root) return null;
  let node = this.root;
  while (node.left !== null) {
    node = node.left;
  }
  return node.key;
}

// max() 获取二叉搜索树最大值
max() {
  if (!this.root) return null;
  let node = this.root;
  while (node.right !== null) {
    node = node.right;
  }
  return node.key;
}

查找特定值

查找二叉搜索树当中的特定值效率也非常高。只需要从根节点开始将需要查找节点的 key 值与之比较，若 node.key < root 则向左查找，若 node.key > root 就向右查找，直到找到或查找到 null 为止。这里可以使用递归实现，也可以采用循环来实现。

代码实现：

// search(key) 查找二叉搜索树中是否有相同的key，存在返回 true，否则返回 false
search(key) {
  return this.searchNode(this.root, key);
}

// 通过递归实现
searchNode(node, key) {
  if (node === null) return false;
  if (key < node.key) {
    return this.searchNode(node.left, key);
  } else if (key > node.key) {
    return this.searchNode(node.right, key);
  } else {
    return true;
  }
}

// 通过 while 循环实现
search2(key) {

  let node = this.root;

  while (node !== null) {
    if (key < node.key) {
      node = node.left;
    } else if (key > node.key) {
      node = node.right;
    } else {
      return true;
    }
  }

  return false;

}

实现 remove()方法

删除方法要考虑的情况比较多，是一个难点

删除思路：

先寻找要删除的节点
- 若没有找到要删除的节点，说明节点不存在，直接返回 return false 即可
- 若找到要删除的节点，我们需要先记录下节点(current)，以及删除节点的父节点(parent)，删除节点是父节点的左子树还是父节点的右子树(isLeftChild)
  - 若找到删除的节点，我们需要考虑以下 3 种情况
  - 要删除的是叶子节点
  - 要删除的节点，只有一个子节点
  - 要删除的节点，有两个子节点

寻找要删除的节点

BinarySearchTree.prototype.remove = function (key) {
  var current = this.root; // current保存要删除的节点
  var parent = null; // 保存要删除节点的父节点
  var isLeftChild = false; // 用于判断要删除的节点是父节点的左节点还是右节点

  // 寻找要删除的节点
  while (current.key != key) {
    parent = current;
    if (key < current.key) {
      isLeftChild = true;
      current = current.left;
    } else {
      isLeftChild = false;
      current = current.right;
    }
    // 若没有找到，说明不需要删除，返回false
    if (current === null) return false;
  }
};

找到了要删除的节点

当我们通过上面的代码找到了删除的节点，我们需要对以下 3 种情况进行展开

4.2.1 要删除的是叶子节点
4.2.2 要删除的节点，只有一个子节点
4.2.3 要删除的节点，有两个子节点

第二步：删除找到的指定节点，后分 3 种情况：

删除的是叶子节点；
删除的是只有一个子节点的节点；
删除的是有两个子节点的节点；

删除的是叶子节点

删除的是叶子节点分两种情况：

叶子节点也是根节点

当该叶子节点为根节点时，如下图所示，此时 current == this.root，直接通过：this.root = null，删除根节点。

叶子节点不为根节点

当该叶子节点不为根节点时也有两种情况，如下图所示

若 current = 8，可以通过：parent.left = null，删除节点 8；

若 current = 10，可以通过：parent.right = null，删除节点 10；

代码实现：

// 1、删除的是叶子节点的情况
if (currentNode.left === null && currentNode.right === null) {
  if (currentNode === this.root) {
    this.root = null;
  } else if (isLeftChild) {
    parentNode.left = null;
  } else {
    parentNode.right = null;
  }

  // 2、删除的是只有一个子节点的节点
}

删除的是只有一个子节点的节点

有六种情况：

当 current 存在左子节点时（current.right == null）：

情况 1：current 为根节点（current == this.root），如节点 11，此时通过：this.root = current.left，删除根节点 11；
情况 2：current 为父节点 parent 的左子节点（isLeftChild == true），如节点 5，此时通过：parent.left = current.left，删除节点 5；
情况 3：current 为父节点 parent 的右子节点（isLeftChild == false），如节点 9，此时通过：parent.right = current.left，删除节点 9；

当 current 存在右子节点时（current.left = null）：

情况 4：current 为根节点（current == this.root），如节点 11，此时通过：this.root = current.right，删除根节点 11。
情况 5：current 为父节点 parent 的左子节点（isLeftChild == true），如节点 5，此时通过：parent.left = current.right，删除节点 5；
情况 6：current 为父节点 parent 的右子节点（isLeftChild == false），如节点 9，此时通过：parent.right = current.right，删除节点 9；

代码实现：

// 2、删除的是只有一个子节点的节点
} else if (currentNode.right === null) { // currentNode 只存在左节点
  //-- 2.1、currentNode 只存在<左节点>的情况
  //---- 2.1.1、currentNode 等于 root
  //---- 2.1.2、parentNode.left 等于 currentNode
  //---- 2.1.3、parentNode.right 等于 currentNode

  if (currentNode === this.root) {
    this.root = currentNode.left;
  } else if (isLeftChild) {
    parentNode.left = currentNode.left;
  } else {
    parentNode.right = currentNode.left;
  }

} else if (currentNode.left === null) { // currentNode 只存在右节点
  //-- 2.2、currentNode 只存在<右节点>的情况
  //---- 2.1.1 currentNode 等于 root
  //---- 2.1.1 parentNode.left 等于 currentNode
  //---- 2.1.1 parentNode.right 等于 currentNode

  if (currentNode === this.root) {
    this.root = currentNode.right;
  } else if (isLeftChild) {
    parentNode.left = currentNode.right;
  } else {
    parentNode.right = currentNode.right;
  }

删除的是有两个子节点的节点

这种情况十分复杂，首先依据以下二叉搜索树，讨论这样的问题：

删除节点 9

在保证删除节点 9 后原二叉树仍为二叉搜索树的前提下，有两种方式：

方式 1：从节点 9 的左子树中选择一合适的节点替代节点 9，可知节点 8 符合要求；
方式 2：从节点 9 的右子树中选择一合适的节点替代节点 9，可知节点 10 符合要求；

删除节点 7

在保证删除节点 7 后原二叉树仍为二叉搜索树的前提下，也有两种方式：

方式 1：从节点 7 的左子树中选择一合适的节点替代节点 7，可知节点 5 符合要求；
方式 2：从节点 7 的右子树中选择一合适的节点替代节点 7，可知节点 8 符合要求；

删除节点 15

在保证删除节点 15 后原树二叉树仍为二叉搜索树的前提下，同样有两种方式：

方式 1：从节点 15 的左子树中选择一合适的节点替代节点 15，可知节点 14 符合要求；
方式 2：从节点 15 的右子树中选择一合适的节点替代节点 15，可知节点 18 符合要求；

相信你已经发现其中的规律了！

规律总结：如果要删除的节点有两个子节点，甚至子节点还有子节点，这种情况下需要从要删除节点下面的子节点中找到一个合适的节点，来替换当前的节点。

若用 current 表示需要删除的节点，则合适的节点指的是：

current 左子树中比 current 小一点点的节点，即 current 左子树中的最大值；
current 右子树中比 current 大一点点的节点，即 current 右子树中的最小值；

前驱&后继

在二叉搜索树中，这两个特殊的节点有特殊的名字：

比 current 小一点点的节点，称为 current 节点的前驱。比如下图中的节点 5 就是节点 7 的前驱；
比 current 大一点点的节点，称为 current 节点的后继。比如下图中的节点 8 就是节点 7 的后继；

查找需要被删除的节点 current 的后继时，需要在 current 的右子树中查找最小值，即在 current 的右子树中一直向左遍历查找；

查找前驱时，则需要在 current 的左子树中查找最大值，即在 current 的左子树中一直向右遍历查找。

下面只讨论查找 current 后继的情况，查找前驱的原理相同，这里暂不讨论。

代码实现：

  // 3、删除的是有两个子节点的节点
  } else {

    // 1、找到后续节点
    let successor = this.getSuccessor(currentNode);

    // 2、判断是否为根节点
    if (currentNode === this.root) {
      this.root = successor;
    } else if (isLeftChild) {
      parentNode.left = successor;
    } else {
      parentNode.right = successor;
    }

    // 3、将后续的左节点改为被删除的左节点
    successor.left = currentNode.left;
  }
}

// 获取后续节点，即从要删除的节点的右边开始查找最小的值
getSuccessor(delNode) {

  // 定义变量，保存要找到的后续
  let successor = delNode;
  let current = delNode.right;
  let successorParent = delNode;

  // 循环查找 current 的右子树节点
  while (current !== null) {
    successorParent = successor;
    successor = current;
    current = current.left;
  }

  // 判断寻找到的后续节点是否直接就是要删除节点的 right
  if (successor !== delNode.right) {
    successorParent.left = successor.right;
    successor.right = delNode.right;
  }
  return successor;
}


// https://gaoxiaoduan.github.io/leetcode-js/data-structure/09_binary_search_tree#%E4%B8%89%E5%B9%B3%E8%A1%A1%E6%A0%91

数据结构与算法

数据结构与算法

1.概念

数据结构

常见的数据结构

算法（Algorithm）的定义

算法通俗理解

算法案例

时间复杂度

空间复杂度

2.数据结构

2.1数组（array)

2.2栈

程序中的栈结构

练习

栈常见的操作

JavaScript 代码实现栈结构

2.3队列

认识队列

受限之处：

队列在程序中的应用

2.3 链表

链表和数组

数组

链表

链表中的常见操作

单向链表

双向链表

双向链表结构

双向链表常见的操作

2.4集合

2.5字典

2.6哈希表

认识哈希表

认识哈希化

哈希表的一些概念

地址的冲突

链地址法（拉链法）

开放地址法

线性探测

二次探测

再哈希法

装填因子

不同探测方式性能的比较

哈希函数

快速计算

均匀分布

哈希表常见操作

2.7树

什么是树？

真实的树：

树的特点：

树结构对比于数组/链表/哈希表有哪些优势呢？

真实的树：

树的特点：

树结构对比于数组/链表/哈希表有哪些优势呢？

树的常用术语：