前端学习数据结构与算法系列(四)：哈希、堆和二叉查找树

本文由图雀社区认证作者 神奇的程序员 写作而成，图雀社区将连载其前端学习数据结构与算法系列，点击阅读原文查看作者的掘金链接，感谢作者的优质输出，让我们的技术世界变得更加美好?

哈希的概念

哈希是由键 (key) 和值 (value) 组成的数据。

存储数据

例如，将图中所示数据，存储到哈希表中：

1. 准备数组：声明长度为5的数组：

1. 尝试把Joe存进去：

1. 使用哈希函数 (Hash) 计算 Joe 的值，即字符串 "Joe" 的哈希值。得到的结果是 4928：

1. 将得到的哈希值处以数组的长度 5，求得其余数。这样的操作叫 "mod运算"。此处mod的运算结果为 3：

1. 将 Joe 进行 mod 运算的值作为数组下标，放进数组里：

1. 重复上述步骤，即可往哈希表中添加数据、

存储冲突

当元素进行 mod 运算后，可能会与其他元素的 mod 值一样，此时数组中已经有其他元素占了这个下标位置，这种存储位置重复了的情况便叫做 冲突，我们来看个例子：

使用链表解决冲突问题

遇到存储冲突问题时，可使用 链表[1] 在已有数据的后面继续存储新的数据，也称之为链地址法。

例如，Nell 的 mod 结果为1，此时下标为1的地址中已经有了Sue元素，此时使用链表在Sue后面添加Nell即可。

查询数据

将要查询的key使用哈希函数计算出哈希值，进行mod运算，得出的结果即当前要查询key在数组[2]中的的下标，通过下标访问即可获取存储的元素，取出对应的值。

例如要查询Dan的值

1. 对Dan进行mod运算得出值为4，则得之Dan在数组的下标是4

1. 取出Dan对应的value值为M

数组中的链表数据查询

将需要查找的key进行mod运算，得到结果后，发现对应下标下的key不一致，然后对不一致的key的链表进行线性查找，得出查找的key，取出value值。

例如，需要查询Ally键对应的value值：

1. 求出Ally的哈希值，对哈希值进行mod运算，得出值为3：

1. 对下标为3元素的连败哦进行线性查找，找到Ally元素：

哈希表的优点

在哈希表中，可以利用哈希函数快速访问到数组中的目标元素。如果发生哈希冲突，就是用链表进行存储。这样一来，不管数据量多少，我们都能够灵活应对。

哈希表的缺点

如果数组空间太小，使用哈希表的时候很容易发生冲突，线性查找的使用频率也会更高，反过来，如果数组的空间太大，就会造成内存的浪费。因此，使用哈希表时，数组空间大小的指定非常重要。

更多解决冲突的方法

开放地址法

这种方法是指当冲突发生时，立刻计算出一个候补地址(数组上的位置)并将数据存去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通 过多次使用哈希函数或 “线性探测法” 等方法计算候补地址。

堆的概念

堆是一种图的数据结构，被用于实现“优先队列”。

优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点(node)”，数据就存储在这些节点中。

堆的特点

如下图所示，每个节点由两个子节点，用线条连接即为堆：

1. 结点内的数字就是存储的数据
2. 堆中的每个结点最多有两个子节点
3. 树的形状取决于数据的个数
4. 节点的排列顺序为从上到下，同一行里则为从左到右
5. 堆的父节点必须小于子结点

堆的数据存储

在堆中存储数据时必须遵守这样一条规则：子结点必定大于父节点

1. 顶端的结点为根节点存储的数据为堆中的最小值
2. 新数据增加时会被放在堆的最底部靠左的位置
3. 堆的底部没有多余空间时，会另起一行把数据加在这一行的最左端

例如，将数字5添加到堆中：

1. 结点6有个空位置，将数字5加在结点6中

1. 数字5结点的父结点大于本身，故调换位置

1. 交换完毕后数字5结点的父节点小于本身，所以不再交换，往堆中插入数据5的操作结束

堆的数据获取

从堆中获取数据时，需要从最上面的数据开始取，取完数据后，堆需要进行重新排序，将最后的数据移到取出的结点位置。

如图所示，取出堆中的数字1：

1. 1被取出后，结构需要重新调整

1. 将最后的数字6结点移到最顶部

1. 如果子结点的数字小于父节点，就将父节点与其左右两个子节点中较小的一个进行交换

1. 数字6结点的子结点3和5，3为较小者。故与3进行位置调换

1. 交换后，数字6结点的两个子节点4和8，4为较小者。故与4进行位置交换

1. 交换后，数字6结点无子节点。故交换完毕，从堆中取出数据的操作完成

二叉查找树的概念

二叉查找树是一种数据结构，采用了图的树形结构，数据存储于二叉查找树的各个结点中。

二叉查找树又叫 二叉搜索树 或 二叉排序树。

如图所示，即为一个二叉查找树的示例：

二叉查找树的特点

1. 同堆一样，每个节点最多有两个子结点
2. 每个结点的值均大于其左子树上任意一个结点的值
3. 每个结点的值均小于其右子树上任意一个结点的值
4. 查询二叉树中最小值要从顶端开始找他的左子树
5. 查询二叉树中最大值要从顶端开始找他的右子树

添加数据

1. 首先从二叉查找树的顶端结点开始寻找数字的位置
2. 将想要添加的结点的值与该结点的值进行比较
3. 若要添加的结点值小于当前结点值则往左移否则右移
4. 左移或右移后与其子结点继续比较，重复步骤3进行判断左移还是右移
5. 当判断至当前结点的子结点不存在则数据插入完毕

示例1

将数字1插入一个二查找树中：

1. 将插入的数据与树的顶端结点进行比较,1<15数据左移

1. 左移后，与15的子结点9进行比较，1<9数据左移

1. 左移后，与9的子结点3进行比较，1<3数据左移，由于3没有子结点了，所以将1作为新结点添加到左下方

1. 至此，1的添加操作就完成了

示例2

将数字4插入一个二叉查找树中。

1. 与示例1步骤一样，与二叉树顶端的结点进行比较，由于4<15，数据左移

1. 将插入的结点与15的子结点9进行比价，4<9,数据左移

1. 将插入的结点与9的子结点3进行比较，4>3，数据右移

1. 将插入的结点与3的子结点8进行比较，4>8，数据左移，8没有子结点，所以将4作为新结点添加到左下方

1. 至此，4的添加操作完成

删除数据

1. 删除结点时，判断要删除的结点是否有子结点，若子结点不存在则直接删除
2. 若要删除的结点只有一个子结点，则先删除目标结点，然后将子结点移到被删除结点的位置上即可
3. 若删除的结点有多个子结点，则先删除目标结点，然后在被删除结点的左子树中寻找最大结点，最后将最大结点移到被删除结点的位置上，若要移动的结点还有子结点，则递归前面的操作。
4. 存在多个子结点时，也可在被删除结点的右子树中寻找最小结点，将其移至被删除结点的位置。

示例1

删除数字28的结点

1. 先判断28所在结点是否有子结点
2. 28结点无子结点直接删除

示例2

删除结点8

1. 结点8有一个子结点，则先删除目标结点8

1. 移动目标结点的子结点4移到被删除结点的位置上

示例3

删除结点9

1. 删除目标结点

1. 在被删除结点的左子树中寻找最大结点

1. 找到最大结点为4，将其移至被删除结点的位置

查询数据

1. 首先，从二叉树的顶端结点开始往下查找。
2. 与添加数据时一样，将要查找的结点和树中的结点进行比较，小于该结点则往左移，否则往右移

示例

查找树中的结点12

1. 从二叉查找树的顶端结点开始往下查找，将要查询的结点12与顶端的结点15进行比较,12<15，数据左移

1. 左移后，将要查询的结点12与结点15的子结点4进行比较，5<12,数据右移

1. 右移后，找到结点12，查询结束

写在最后

* 文中使用的图片源自《我的第一本算法书》，如若侵权，请联系图雀社区公众号小编，作者立即删除相关图片。