本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其前端学习数据结构与算法系列 ,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美好?
哈希的概念 哈希是由键 (key) 和值 (value) 组成的数据。
存储数据 例如,将图中所示数据,存储到哈希表中:
准备数组:声明长度为5的数组: 尝试把Joe存进去: 使用哈希函数 (Hash) 计算 Joe 的值,即字符串 "Joe" 的哈希值。得到的结果是 4928: 将得到的哈希值处以数组的长度 5,求得其余数。这样的操作叫 "mod运算"。此处mod的运算结果为 3: 将 Joe 进行 mod 运算的值作为数组下标,放进数组里: 重复上述步骤,即可往哈希表中添加数据、 存储冲突 当元素进行 mod 运算后,可能会与其他元素的 mod 值一样,此时数组中已经有其他元素占了这个下标位置,这种存储位置重复了的情况便叫做 冲突 ,我们来看个例子:
使用链表解决冲突问题 遇到存储冲突问题时,可使用 链表 [1] 在已有数据的后面继续存储新的数据,也称之为链地址法 。
例如,Nell 的 mod 结果为1,此时下标为1的地址中已经有了Sue元素,此时使用链表在Sue后面添加Nell即可。
查询数据 将要查询的key使用哈希函数计算出哈希值,进行mod运算,得出的结果即当前要查询key在数组 [2] 中的的下标,通过下标访问即可获取存储的元素,取出对应的值。
例如要查询Dan的值
对Dan进行mod运算得出值为4,则得之Dan在数组的下标是4 取出Dan对应的value值为M 数组中的链表数据查询 将需要查找的key进行mod运算,得到结果后,发现对应下标下的key不一致,然后对不一致的key的链表进行线性查找,得出查找的key,取出value值。
例如,需要查询Ally键对应的value值:
求出Ally的哈希值,对哈希值进行mod运算,得出值为3: 对下标为3元素的连败哦进行线性查找,找到Ally元素: 哈希表的优点 在哈希表中,可以利用哈希函数快速访问到数组中的目标元素。如果发生哈希冲突,就是用链表进行存储。这样一来,不管数据量多少,我们都能够灵活应对。
哈希表的缺点 如果数组空间太小,使用哈希表的时候很容易发生冲突,线性查找的使用频率也会更高,反过来,如果数组的空间太大,就会造成内存的浪费。因此,使用哈希表时,数组空间大小的指定非常重要。
更多解决冲突的方法 开放地址法
这种方法是指当冲突发生时,立刻计算出一个候补地址(数组上的位置)并将数据存去。如果仍然有冲突,便继续计算下一个候补地址,直到有空地址为止。可以通 过多次使用哈希函数或 “线性探测法” 等方法计算候补地址。
堆的概念 堆是一种图的数据结构,被用于实现“优先队列”。
优先队列是一种数据结构,可以自由添加数据,但取出数据时要从最小值开始按顺序取出。在堆的树形结构中,各个顶点被称为“结点(node)”,数据就存储在这些节点中。
堆的特点 如下图所示,每个节点由两个子节点,用线条连接即为堆:
结点内的数字就是存储的数据 堆中的每个结点最多有两个子节点 树的形状取决于数据的个数 节点的排列顺序为从上到下,同一行里则为从左到右 堆的父节点必须小于子结点 堆的数据存储 在堆中存储数据时必须遵守这样一条规则:子结点必定大于父节点
顶端的结点为根节点存储的数据为堆中的最小值 新数据增加时会被放在堆的最底部靠左的位置 堆的底部没有多余空间时,会另起一行把数据加在这一行的最左端 例如,将数字5添加到堆中:
结点6有个空位置,将数字5加在结点6中 数字5结点的父结点大于本身,故调换位置 交换完毕后数字5结点的父节点小于本身,所以不再交换,往堆中插入数据5的操作结束 堆的数据获取 从堆中获取数据时,需要从最上面的数据开始取,取完数据后,堆需要进行重新排序,将最后的数据移到取出的结点位置。
如图所示,取出堆中的数字1:
1被取出后,结构需要重新调整 将最后的数字6结点移到最顶部 如果子结点的数字小于父节点,就将父节点与其左右两个子节点中较小的一个进行交换 数字6结点的子结点3和5,3为较小者。故与3进行位置调换 交换后,数字6结点的两个子节点4和8,4为较小者。故与4进行位置交换 交换后,数字6结点无子节点。故交换完毕,从堆中取出数据的操作完成 二叉查找树的概念 二叉查找树是一种数据结构,采用了图的树形结构,数据存储于二叉查找树的各个结点中。
二叉查找树又叫 二叉搜索树 或 二叉排序树 。
如图所示,即为一个二叉查找树的示例:
二叉查找树的特点 同堆一样,每个节点最多有两个子结点 每个结点的值均大于其左子树上任意一个结点的值 每个结点的值均小于其右子树上任意一个结点的值 查询二叉树中最小值要从顶端开始找他的左子树 查询二叉树中最大值要从顶端开始找他的右子树 添加数据 首先从二叉查找树的顶端结点开始寻找数字的位置 将想要添加的结点的值与该结点的值进行比较 若要添加的结点值小于当前结点值则往左移否则右移 左移或右移后与其子结点继续比较,重复步骤3进行判断左移还是右移 当判断至当前结点的子结点不存在则数据插入完毕 示例1 将数字1插入一个二查找树中:
将插入的数据与树的顶端结点进行比较,1<15数据左移 左移后,与15的子结点9进行比较,1<9数据左移 左移后,与9的子结点3进行比较,1<3数据左移,由于3没有子结点了,所以将1作为新结点添加到左下方 至此,1的添加操作就完成了 示例2 将数字4插入一个二叉查找树中。
与示例1步骤一样,与二叉树顶端的结点进行比较,由于4<15,数据左移 将插入的结点与15的子结点9进行比价,4<9,数据左移 将插入的结点与9的子结点3进行比较,4>3,数据右移 将插入的结点与3的子结点8进行比较,4>8,数据左移,8没有子结点,所以将4作为新结点添加到左下方 至此,4的添加操作完成 删除数据 删除结点时,判断要删除的结点是否有子结点,若子结点不存在则直接删除 若要删除的结点只有一个子结点,则先删除目标结点,然后将子结点移到被删除结点的位置上即可 若删除的结点有多个子结点,则先删除目标结点,然后在被删除结点的左子树中寻找最大结点,最后将最大结点移到被删除结点的位置上,若要移动的结点还有子结点,则递归前面的操作。 存在多个子结点时,也可在被删除结点的右子树中寻找最小结点,将其移至被删除结点的位置。 示例1 删除数字28的结点
先判断28所在结点是否有子结点 28结点无子结点直接删除 示例2 删除结点8
结点8有一个子结点,则先删除目标结点8 移动目标结点的子结点4移到被删除结点的位置上 示例3 删除结点9
删除目标结点 在被删除结点的左子树中寻找最大结点 找到最大结点为4,将其移至被删除结点的位置 查询数据 首先,从二叉树的顶端结点开始往下查找。 与添加数据时一样,将要查找的结点和树中的结点进行比较,小于该结点则往左移,否则往右移 示例 查找树中的结点12
从二叉查找树的顶端结点开始往下查找,将要查询的结点12与顶端的结点15进行比较,12<15,数据左移 左移后,将要查询的结点12与结点15的子结点4进行比较,5<12,数据右移 右移后,找到结点12,查询结束 写在最后 * 文中使用的图片源自《我的第一本算法书》,如若侵权,请联系图雀社区公众号小编,作者立即删除相关图片。