门户网站和社交网络的区别,做网站的财务需求,在线图片编辑尺寸,网站开发攻克时间【数据结构与算法——TypeScript】
哈希表(HashTable)
哈希表介绍和特性 哈希表是一种非常重要的数据结构#xff0c;但是很多学习编程的人一直搞不懂哈希表到底是如何实现的。 在这一章节中#xff0c;我门就一点点来实现一个自己的哈希表。通过实现来理解哈希表背后的原理…【数据结构与算法——TypeScript】
哈希表(HashTable)
哈希表介绍和特性 哈希表是一种非常重要的数据结构但是很多学习编程的人一直搞不懂哈希表到底是如何实现的。 在这一章节中我门就一点点来实现一个自己的哈希表。通过实现来理解哈希表背后的原理和它的优势。 几乎所有的编程语言都有直接或者间接的应用这种数据结构。 哈希表通常是基于数组进行实现的但是相对于数组它也很多的优势 口 它可以提供非常快速的插入-甽除-查找操作口 无论多少数据插入和删除值都接近常量的时间即O(1)的时间与杂度。实际上只需要几个机器指令即可完成口 哈希表的速度比树还要快基本可以瞬间查找到想要的元素口 哈希表相对于树来说编码要容易很多 哈希表相对于数组的一些不足 口 哈希表中的数据是没有顺序的所以不能以一种固定的方式(出如从小到大)来遍力其中的元素没有特妹处理情况下口 通常情况下哈希表中的key是不允许重复的不能放置相同的key用于保存不同的元素。
哈希表到底是什么呢
口 我们只是说了一下它的优势似乎还是没有说它到底长什么样子口 这也是哈希表不好理解的地方不像数组和链表甚至是树一样直接画出你就知道它的结构甚至是原理了。口 ❤️ 它的结构就是数组但是它神奇的地方在于对数组下标值的一种变换 这种变换我们可以使用哈希函数通过哈希函数可以获取到 HashCode.口 不着急我们慢慢来认识它到底是什么。 我们通过二个案例案例需要你挑选某种数据结构而你会发现最好的 选择就是哈希表
口 案例一公司使用一种数据结构来保存所有员工口 案例二使用一种数据结构存储单词信息比如有50000个单词。找到单词后每个单词有自己的翻译读音应用等等 案例一公司员工存储 案例介绍 口 假如一家公司有1000个员工现在我们需要将这些员工的信息使用某种数据结构来保存起来口 你会采用什么数据结构呢 ✅ 方案一数组 口 一种方案是按照顺序将所有的员工依次存入一个长度为1000的数组中。口 每个员工的信息都保存在数组的某个位置上。口 但是我们要查看某个具体员工的信息怎么办呢一个个找吗不太好找。口 数组最大的优势是什么通过下标值去获取信息。口 所以为了可以通过数组快速定位到某个员工最好给员工信息中添加一个员工編号(工号) 而编号对应的就是员工的下标值。口 当查找某个员工的信息时通过员工编号可以快速定位到员工的信息位置 ✅ 方案二链表 口 链表对应插入和删除数据有一定的优势。口 但是对于获取员工的信息每次都必须从头遍历到尾这种方式显然不是特别适合我们这里。 ✅ 最终方案 口 这样看最终方案似乎就是数组了 但是数组还是有缺点什么缺点呢口 但是如果我们只知道员工的姓名 比如why但是不知道why的员工編号你怎么办呢只能线性查找效率非常的低能不能有一种办法让why的名字和它的员工编号产生直接的关系呢 也就是通过why这个名字我们就能获取到它的素引值而再通过索引值我就能获取到why的信息呢口 这样的方案已经存在了就是使用哈希函数让某个key的信息和索引值对应起来。 案例二50000个单词的存储 案例介绍 口 使用一种数据结构存储单词信息比如有50000个单词.口 找到单词后每个单词有自己的翻译读音应用等等 ✅ 方案一数组 口 这个案例更加明显能感受到数组的缺陷口 拿到一个单词 lridescent我想知道这个单词的翻译/读音/应用。口 怎么可以从数组中查到这个单词的位置呢口 线性查找50000次比较口 如果你使用数组来实现这个功能效率会非常非常低而且你一定没有学习过数据结构。 ✅ 方案二链表 口 不需要考虑了吧 ✅ 方案三有没有一种方案可以将单词转成数组的下标值呢 口 如果单词转成数组的下标那么以后我们要查找某个单词的信息直接按照下标值一步即可访问到想要的元素
❤️ 字母转数字的方案
似乎所有的案例都指向了一目标将字符串转成下标值 但是怎样才能将一个字符串转成数组的下标值呢 口 单词/字符串转下标值其实就是字母/文字转数字 口 怎么转 现在我们需要设计一种方案可以将单词转成适当的下标值 口 其实计算机中有很多的编码方案就是用数字代皆单词的字符。就是字符编码。常见的字符编码口 比如ASCII编码a是97b是98依次类推122代表z口 我们也可以设计一个自己的编码系统比如a是1b是2c是3依 次类推z是26。口 当然我们可以加上空格用0代替就是27个字符不考虑大写问题口 但是有了编码系统后一个单词如何转成数字呢 ✅ 方案一数字相加 口 一种转换单词的简单方案就是把单词每个字符的编码求和。口 例如单词cats转成数字31201943.那么43就作为cats单词的下标存在数组中。【问题】按照这种方案有一个很明显的问题就是很多单词最终的下标可能都是43。 口 比如was/tin/give/tend/moan/tick等等。口 我们知道数组中一个下标值位置只能存储一个数据如果存入后来的数据必然会造成数据的獲盖。一个下标存储这么多单词显然是不合理的。口 虽然后面的方案也会出现但是要尽虽避免。 ✅ 方案二幂的连乘 口 现在我们想通过一种算法让cats转成数字后不那么普通。口 数字相加的方案就有些过于普通了。口 有一种方案就是使用幂的连乘什么是幂的连乘呢 其实我们平时使用的大于10的数字可以用一种系的连乘来表示它的唯一性 比如7654 7 *103 6 * 102 5 * 10 4 口 我们的单词也可以使用这种方案来表示 比如 cats 3273127220*2717 60337 这样得到的数字可以基本保证它的唯一性不会和别的单词重复。 【问题】如果一个单词是 zzzzzzzzzz(一般英文单词不会超过10个宇符)。那么得到的数字超过7000000000000。 口 数组可以表示这么大的下标值吗口 而且就算能创建这么大的数组事实上有很多是无效的单词。口 创建这么大的数组是没有意义的 两种方案总结: 第一种方案(将数字相加求和)产生的数组下标太少第二种方案(与27的幂相乘求和)产生的数组下标太多
数据的哈希化过程
下标的压缩算法 现在需要一种压缩方法把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。 ◼ 对于英文词典多大的数组才合适呢 如果只有50000个单词可能会定义一个长度为50000的数组。但是实际情况中往往需要更大的空间来存储这些单词。 因为我们不能保证单词会映射到每一个位置。 比如两倍的大小100000。 如何压缩呢 现在就找一种方法把0到超过7000000000000的范围压缩为从0到100000。有一种简单的方法就是使用取余操作符它的作用是得到一个数被另外一个数整除后的余数。 ✅ 取余操作的实现 为了看到这个方法如何工作我们先来看一个小点的数字范围压缩到一个小点的空间中。 假设把从0~199的数字比如使用largeNumber代表压缩为从0到9的数字比如使用smallRange代表。➡️ 下标值的结果index largeNumber % smallRange当一个数被10整除时余数一定在0~9之间;比如13%103157%107。当然这中间还是会有重复不过重复的数量明显变小了。因为我们的数组是100000而只有50000个单词。就好比你在0~199中间选取5个数字放在这个长度为10的数组中也会重复但是重复的概率非常小。(后面我们会讲到真的发生重复了应该怎么解决)
哈希表的一些概念 认识了上面的内容相信你应该懂了哈希表的原理了我们来看看几个概念 哈希化将大数字转化成数组范围内下标的过程我们就称之为哈希化。 哈希函数通常我们会将单词转成大数字大数字在进行哈希化的代码实现放在一个函数中这个函数我们称为哈希函数。 哈希表最终将数据插入到的这个数组对整个结构的封装我们就称之为是一个哈希表。 但是我们还有问题需要解决 虽然我们在一个100000的数组中放50000个单词已经足够。但是通过哈希化后的下标值依然可能会重复如何解决这种重复的问题呢
地址冲突解决方案
什么是冲突?
◼ 尽管50000个单词我们使用了100000个位置来存储并且通过一种相对比较好的哈希函数来完成。但是依然有可能会发生冲突。 比如 melioration 这个单词通过哈希函数得到它数组的下标值后发现那个位置上已经存在一个单词demystify因为它经过哈希化后和melioration得到的下标实现相同的。 ◼ 这种情况我们成为冲突。◼ 虽然我们不希望这种情况发生当然更希望每个下标对应一个数据项但是通常这是不可能的。◼ 冲突不可避免我们只能解决冲突。 : 就像之前0~199的数字选取5个放在长度为10的单元格中 如果我们随机选出来的是3382114590那么最终它们的位置会是3-2-1-5-0没有发生冲突。但是如果其中有一个33还有一个73呢还是发生了冲突。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wMwdr2p6-1691473209048)(/Volumes/web/数据结构与算法ts/画图/哈希表/取余操作.png “发生冲突”)] ◼ 我们需要针对 这种冲突 提出一些解决方案 虽然冲突的可能性比较小你依然需要考虑到这种情况以便发生的时候进行对应的处理代码。 ◼ 如何解决这种冲突呢常见的情况有两种方案。 ❤️ 链地址法。❤️ 开放地址法。
链地址法 链地址法是一种比较常见的解决冲突的方案。(也称为拉链法) 其实如果你理解了为什么产生冲突看到图后就可以立马理解链地址法是什么含义了。
链地址法解析 图片解析 从图片中我们可以看出链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据而是一个链条。这个链条使用什么数据结构呢常见的是数组或者链表。比如是链表也就是每个数组单元中存储着一个链表。一旦发现重复将重复的元素插入到链表的首端或者末端即可。当查询时先根据哈希化后的下标值找到对应的位置再取出链表依次查询找寻找的数据。 数组还是链表呢 数组或者链表在这里其实都可以效率上也差不多。因为根据哈希化的index找出这个数组或者链表时通常就会使用线性查找这个时候数组和链表的效率是差不多的。当然在某些实现中会将新插入的数据放在数组或者链表的最前面因为觉得新插入的数据用于取出的可能性更大。这种情况最好采用链表因为数组在首位插入数据是需要所有其他项后移的链表就没有这样的问题。当然我觉得出于这个也看业务需求不见得新的数据就访问次数会更多比如我们微信新添加的好友可能是刚认识的联系的频率不见得比我们的老朋友更多甚至新加的只是聊一两句。所以这里个人觉得选择数组或者链表都是可以的。
开放地址法 开放地址法的主要工作方式是寻找空白的单元格来添加重复的数据。 我们还是通过图片来了解开放地址法的工作方式。
开放地址法解析 问题: 新插入32放在什么位置呢? 开放地址解决方法: 新插入的 32 本来应该插入到82的位置,但是该位置已经包含数据我们发现 3 和 5 还有 9 的位置是没有任何内容的这个时候就可以寻找到对应的空白位置来放这个数据但是到底使用哪一个位置呢? 这就又需要分情况了 图片解析 从图片的文字中我们可以了解到 开放地址法其实就是要寻找空白的位置来放置冲突的数据项。 但是探索这个位置的方式不同有三种方法 ✅ 线性探测✅ 二次探测✅ 再哈希法
线性探测 ◼ 线性探测非常好理解线性的查找空白的单元。 ◼ 插入的32 经过哈希化得到的index2但是在插入的时候发现该位置已经有了82。怎么办呢线性探测就是从index位置1开始一点点查找合适的位置来放置32什么是合适的位置呢空的位置就是合适的位置在我们上面的例子中就是index3的位置这个时候32就会放在该位置。 ◼ 查询32呢 查询32和插入32比较相似。首先经过哈希化得到index2比如2的位置结果和查询的数值是否相同相同那么就直接返回。不相同呢线性查找从index位置1开始查找和32一样的。这里有一个特别需要注意的地方如果32的位置我们之前没有插入是否将整个哈希表查询一遍来确定32存不存在吗当然不是查询过程有一个约定就是查询到空位置就停止。因为查询到这里有空位置32之前不可能跳过空位置去其他的位置。 线性探测的问题 ◼ 删除32呢 删除操作和插入查询比较类似但是也有一个特别注意点。注意删除操作一个数据项时不可以将这个位置下标的内容设置为null为什么呢因为将它设置为null可能会影响我们之后查询其他操作所以通常删除一个位置的数据项时我们可以将它进行特殊处理(比如设置为-1)。当我们之后看到-1位置的数据项时就知道查询时要继续查询但是插入时这个位置可以放置数据。 线性探测的问题 线性探测有一个比较严重的问题就是聚集。什么是聚集呢比如我在没有任何数据的时候插入的是22-23-24-25-26那么意味着下标值2-3-4-5-6的位置都有元素。这种一连串填充单元就叫做聚集。聚集会影响哈希表的性能无论是插入/查询/删除都会影响。比如我们插入一个32会发现连续的单元都不允许我们放置数据并且在这个过程中我们需要探索多次。二次探测可以解决一部分这个问题我们一起来看一看。
二次探测
我们刚才谈到线性探测存在的问题 如果之前的数据是连续插入的那么新插入的一个数据可能需要探测很长的距离。 ✓ 二次探测在线性探测的基础上进行了优化 二次探测主要优化的是探测时的步长什么意思呢线性探测我们可以看成是步长为1的探测比如从下标值x开始那么线性测试就是x1x2x3依次探测。二次探测对步长做了优化比如从下标值x开始x1²x2²x3²。这样就可以一次性探测比较长的距离比避免那些聚集带来的影响。 二次探测的问题 但是二次探测依然存在问题比如我们连续插入的是32-112-82-2-192那么它们依次累加的时候步长的相同的。也就是这种情况下会造成步长不一样的一种聚集。还是会影响效率。(当然这种可能性相对于连续的数字会小一些)怎么根本解决这个问题呢让每个人的步长不一样一起来看看再哈希法吧。
再哈希法
▪️ 为了消除线性探测和二次探测中无论步长1还是步长平法中存在的问题, 还有一种最常用的解决方案: 再哈希法. 再哈希法: 二次探测的算法产生的探测序列步长是固定的: 1, 4, 9, 16, 依次类推.现在需要一种方法: 产生一种依赖关键字的探测序列, 而不是每个关键字都一样.那么, 不同的关键字即使映射到相同的数组下标, 也可以使用不同的探测序列.再哈希法的做法就是: 把关键字用另外一个哈希函数, 再做一次哈希化, 用这次哈希化的结果作为步长.对于指定的关键字,步长在整个探测中是不变的, 不过不同的关键字使用不同的步长. 第二次哈希化需要具备如下特点: 和第一个哈希函数不同. (不要再使用上一次的哈希函数了, 不然结果还是原来的位置)不能输出为0(否则, 将没有步长. 每次探测都是原地踏步, 算法就进入了死循环) 其实, 我们不用费脑细胞来设计了, 计算机专家已经设计出一种工作很好的哈希函数: stepSize constant - (key % constant)其中constant是质数, 且小于数组的容量.例如: stepSize 5 - (key % 5), 满足需求, 并且结果不可能为0.
哈希化的效率
哈希表中执行插入和搜索操作效率是非常高的 如果没有产生冲突那么效率就会更高。 如果发生冲突存取时间就依赖后来的探测长度。 平均探测长度以及平均存取时间取决于填装因子随着填装因子变大探测长度也越来越长。 随着填装因子变大效率下降的情况在不同开放地址法方案中比链地址法更严重所以我们来对比一下他们的效率再决定我们选取的方案。 ◼ 在分析效率之前我们先了解一个概念装填因子 装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值。 装填因子 总数据项 / 哈希表长度。 开放地址法的装填因子最大是多少呢1因为它必须寻找到空白的单元才能将元素放入。 链地址法的装填因子呢可以大于1因为拉链法可以无限的延伸下去只要你愿意。(当然后面效率就变低了)
线性探测效率 下面的等式显示了线性探测时探测序列§和填装因子(L)的关系 ◼ 公式来自于Knuth(算法分析领域的专家现代计算机的先驱人物)这些公式的推导自己去看了一下确实有些繁琐这里不再 给出推导过程仅仅说明它的效率。 线性探测效率 ◼ 图片解析 ◼ 当填装因子是1/2时成功的搜索需要1.5次比较不成功的搜索需要2.5次◼ 当填装因子为2/3时分别需要2.0次和5.0次比较◼ 如果填装因子更大比较次数会非常大。◼ 应该使填装因子保持在2/3以下最好在1/2以下另一方面填装因子越低对于给定数量的数据项就需要越多的空间。◼ 实际情况中最好的填装因子取决于存储效率和速度之间的平衡随着填装因子变小存储效率下降而速度上升。
二次探测和再哈希化性能 ◼ 二次探测和再哈希法的性能相当。它们的性能比线性探测略好。 ◼ 图片解析 ◼ 当填装因子是0.5时成功和不成的查找平均需要2次比较◼ 当填装因子为2/3时分别需要2.37和3.0次比较◼ 当填装因子为0.8时分别需要2.9和5.0次◼ 因此对于较高的填装因子对比线性探测二次探测和再哈希法还是可以忍受的。
链地址法性能 ◼ 链地址法的效率分析有些不同一般来说比开放地址法简单。我们来分析一下这个公式应该是怎么样的。 假如哈希表包含arraySize个数据项每个数据项有一个链表在表中一共包含N个数据项。 那么平均起来每个链表有多少个数据项呢非常简单N / arraySize。 有没有发现这个公式有点眼熟其实就是装填因子。 ◼ OK那么我们现在就可以求出查找成功和不成功的次数了 成功可能只需要查找链表的一半即可1 loadFactor/2 不成功呢可能需要将整个链表查询完才知道不成功1 loadFactor。 ◼ 经过上面的比较我们可以发现链地址法相对来说效率是好于开放地址法的。 ◼ 所以在真实开发中使用链地址法的情况较多 因为它不会因为添加了某元素后性能急剧下降。 比如在Java的HashMap中使用的就是链地址法。
哈希函数代码实现
哈希函数 好的哈希函数应该尽可能让计算的过程变得简单提高计算的效率。 哈希表的主要优点是它的速度所以在速度上不能满足那么就达不到设计的目的了。提高速度的一个办法就是让哈希函数中尽量少的有乘法和除法。因为它们的性能是比较低的。 设计好的哈希函数应该具备哪些优点呢 ✅ 快速的计算 ✓ 哈希表的优势就在于效率所以快速获取到对应的hashCode非常重要。✓ 我们需要通过快速的计算来获取到元素对应的hashCode ✅ 均匀的分布 ✓ 哈希表中无论是链地址法还是开放地址法当多个元素映射到同一个位置的时候都会影响效率。✓ 所以优秀的哈希函数应该尽可能将元素映射到不同的位置让元素在哈希表中均匀的分布。
快速计算 - 霍纳法则
◼ 在前面我们计算哈希值的时候使用的方式: ➡️ cats 327³127²20*2717 60337◼ 这种方式是直观的计算结果那么这种计算方式会进行几次乘法几次加法呢 当然我们可能不止4项可能有更多项 我们抽象一下这个表达式其实是一个多项式 a(n)xna(n-1)x(n-1)…a(1)xa(0) ◼ 现在问题就变成了多项式有多少次乘法和加法 乘法次数n(n1)…1n(n1)/2 加法次数n次 O(N²)
❤️ ◼ 多项式的优化❤️ 霍纳法则 解决这类求值问题的高效算法–霍纳法则。在中国霍纳法则也被称为秦九韶算法。 ◼ 通过如下变换我们可以得到一种快得多的算法即 Pn(x)anxna(n1)x^(n-1)…a1xa0((…(((anxan1)xan2)xan3)…)xa1)xa0 这种求值的方式我们称为霍纳法则。 当x4时,2x4 - 3x3 5x2 x - 7 的值? 先将其转换为的形式 x(x(x(2x - 3 ) 5 ) 1 ) -7 系数2-351-7x422x2-3 54x55254x251 1014x101-7397 ◼ 变换后我们需要多少次乘法多少次加法呢 乘法次数N次 加法次数N次。 ◼ 如果使用大O表示时间复杂度的话我们直接从O(N²)降到了O(N)。
均匀分布
◼ 均匀的分布 在设计哈希表时我们已经有办法处理映射到相同下标值的情况链地址法或者开放地址法。 但是无论哪种方案为了提供效率最好的情况还是让数据在哈希表中均匀分布。 因此我们需要在使用常量的地方尽量使用质数。 哪些地方我们会使用到常量呢 ◼ 质数的使用 哈希表的长度。 N次幂的底数(我们之前使用的是27) ◼ 为什么他们使用质数会让哈希表分布更加均匀呢 质数和其他数相乘的结果相比于其他数字更容易产生唯一性的结果减少哈希冲突。 Java中的N次幂的底数选择的是31是经过长期观察分布结果得出的
N次幂的底数
◼ 这里采用质数的原因是为了产生的数据不按照某种规律递增。 比如我们这里有一组数据是按照4进行递增的0 4 8 12 16将其映射到长度为8的哈希表中。 它们的位置是多少呢0 - 4 - 0 - 4依次类推。 如果我们哈希表本身不是质数而我们递增的数量可以使用质数比如5那么 0 5 10 15 20 它们的位置是多少呢0 - 5 - 2 - 7 - 4依次类推。也可以尽量让数据均匀的分布。 我们之前使用的是27这次可以使用一个接近的数比如31/37/41等等。一个比较常用的数是31或37。 ◼ 总之质数是一个非常神奇的数字。◼ 这里建议两处都使用质数 哈希表中数组的长度。 N次幂的底数。
哈希函数的实现 /*** 哈希函数,将key映射成index* param key 转换的key* param max 数组的长度(最大的数值)* returns 索引值*/function hashFunc(key: string, max: number): number {// 1.计算 hashCode: cats 60337 (27为底)let hascode 0;const length key.length;for (let i 0; i length; i) {// 霍纳法则hascode 31 * hascode key.charCodeAt(i);}// 2.计算索引const index hascode % max;return index;}console.log(hashFunc(abc, 7));console.log(hashFunc(nba, 7));console.log(hashFunc(cbd, 7));console.log(hashFunc(mba, 7));console.log(hashFunc(dfc, 7));console.log(hashFunc(rft, 7));哈希表创建和操作 创建哈希表 我们这里采用链地址法来实现哈希表 实现的哈希表(基于storage的数组)每个index对应的是一个数组(bucket)。(当然基于链表也可以。) bucket中存放什么呢我们最好将key和value都放进去我们继续使用一个数组。(其实其他语言使用元组更好) 最终我们的哈希表的数据格式是这样[[ [kv][kv][kv] ] [ [kv][kv] ][ [kv] ] ] 代码解析 我们定义了三个属性 storage作为我们的数组数组中存放相关的元素。 count表示当前已经存在了多少数据。 limit用于标记数组中一共可以存放多少个元素。 class HashTableT any {// 创建一个数组,用来存储链地址法中的链(数组)private storage: [string, T][][] [];// 数组长度private length: number 7;// 记录已经存放元素的个数private count: number 0;}插入/修改数据put 哈希表的插入和修改操作是同一个函数 因为当使用者传入一个KeyValue时 如果原来不存该key那么就是插入操作。 如果已经存在该key那么就是修改操作。 代码解析 步骤1根据传入的key获取对应的hashCode也就是数组的index 步骤2从哈希表的index位置中取出桶(另外一个数组) 步骤3查看上一步的bucket是否为null 为null表示之前在该位置没有放置过任何的内容那么就新建一个数组[] 步骤4查看是否之前已经放置过key对应的value 如果放置过那么就是依次替换操作而不是插入新的数据。 我们使用一个变量override来记录是否是修改操作 步骤5如果不是修改操作那么插入新的数据。 在bucket中push新的[keyvalue]即可。 注意这里需要将count1因为数据增加了一项。 put的流程图 获取数据 get 获取数据 根据key获取对应的value 代码解析 步骤1根据key获取hashCode(也就是index) 步骤2根据index取出bucket。 步骤3因为如果bucket都是null那么说明这个位置之前并没有插入过数据。 步骤4有了bucket就遍历并且如果找到就将对应的value返回即可。 步骤5没有找到返回null // 获取数据 根据key获取对应的valueget(key: string): T | undefined {// 1. 根据key获取索引值const index this.hashFunc(key, this.length);// 2. 获取bucketconst bucket this.storage[index];if (!bucket) return undefined;// 3. 对比bucket 遍历for (let i 0; i bucket.length; i) {const tuple bucket[i];const tupleKey tuple[0];const tupleVal tuple[1];if (key tupleKey) {return tupleVal;}}return undefined;}删除数据 删除数据 我们根据对应的key删除对应的key/value ◼ 代码解析 思路和获取数据相似 delete(key: string): T | undefined {// 1. 根据key获取索引值const index this.hashFunc(key, this.length);// 2. 获取bucketconst bucket this.storage[index];if (!bucket) return undefined;// 3. 对比bucket 遍历for (let i 0; i bucket.length; i) {const tuple bucket[i];const tupleKey tuple[0];const tupleVal tuple[1];if (key tupleKey) {bucket.splice(i, 1);this.count--;return tupleVal;}}return undefined;}哈希表的自动扩容
哈希表扩容的思想
❓为什么需要扩容 目前我们是将所有的数据项放在长度为7的数组中的。 因为我们使用的是链地址法loadFactor可以大于1所以这个哈希表可以无限制的插入新数据。 但是随着数据量的增多每一个index对应的****bucket会越来越长也就造成效率的降低。 所以在合适的情况对数组进行扩容比如扩容两倍。 ❓❓如何进行扩容 扩容可以简单的将容量增大两倍(不是质数吗质数的问题后面再讨论) 但是这种情况下所有的数据项一定要同时进行修改(重新调用哈希函数来获取到不同的位置) 比如hashCode12的数据项在length8的时候index4。在长度为16的时候呢index12。 这是一个耗时的过程但是如果数组需要扩容那么这个过程是必要的。 -❓❓ 什么情况下扩容呢 比较常见的情况是loadFactor0.75的时候进行扩容。 比如Java的哈希表就是在装填因子大于0.75的时候对哈希表进行扩容。
扩容函数
代码解析 步骤1先将之前数组保存起来因为我们待会儿会将storeage [] 步骤2之前的属性值需要重置。 步骤3遍历所有的数据项重新插入到哈希表中。 ❓在什么时候调用扩容方法呢 在每次添加完新的数据时都进行判断。(也就是put方法中) 修改容量 // 修改容量private resize(newLimit: number) {// 设置新的长度this.length newLimit;// 获取原来所有数据,并且重新放入新的容量数组中// 对数据进行初始化const oldStorage this.storage;this.storage [];this.count 0;// 获取原来的数据,放入新的数组中oldStorage.forEach((bucket) {if (!bucket) return;for (let i 0; i bucket.length; i) {const tuple bucket[i];this.put(tuple[0], tuple[1]);}});}扩容 // 扩容:发现loadFactor0.75const loadFactor this.count / this.length;if (loadFactor 0.75) {this.resize(this.length * 2);}缩容 // 缩容:发现loadFactor 0.25const loadFactor this.count / this.length;if (loadFactor 0.25 this.length 7) {this.resize(Math.floor(this.length / 2));} 容量质数
◼ 我们前面提到过容量最好是质数。 虽然在链地址法中将容量设置为质数没有在开放地址法中重要 但是其实链地址法中质数作为容量也更利于数据的均匀分布。所以我们还是完成一下这个步骤。 ◼ 我们这里先讨论一个常见的面试题判断一个数是质数。◼ 质数的特点 质数也称为素数。 质数表示大于1的自然数中只能被1和自己整除的数。 ◼ OK了解了这个特点应该不难写出它的算法 更高效的质数判断 对于每个数n其实并不需要从2判断到n-1 一个数若可以进行因数分解那么分解时得到的两个数一定是一个小于等于sqrt(n)一个大于等于sqrt(n)。 ✓ 注意 sqrt是square root的缩写表示平方根 比如16可以被分别。那么是2*82小于sqrt(16)也就是48大于4。而4*4都是等于sqrt(n) 所以其实我们遍历到等于sqrt(n)即可 /*** 根据传入的数字,判断是否是一个质数* param num 传入要判断的数字* returns 是否是质数*/export function isPrime(num: number): boolean {const sqrt Math.sqrt(num);for (let i 2; i sqrt; i) {if (num % i 0) return false;}return true;}扩容的质数
首先将初始的limit为8改成7 ◼ 前面我们有对容量进行扩展方式是原来的容量 x 2 比如之前的容量是7那么扩容后就是14。14还是一个质数吗 显然不是所以我们还需要一个方法来实现一个新的容量为质数的算法。◼ 那么我们可以封装获取新的容量的代码(质数) isPrime(num: number): boolean {const sqrt Math.sqrt(num);for (let i 2; i sqrt; i) {if (num % i 0) return false;}return true;}private getNextPrime(num: number) {// 判断容量是否为质数let newPrime num;while (!this.isPrime(newPrime)) {newPrime;}return newPrime;}// 修改容量private resize(newLimit: number) {// 设置新的长度let newPrime this.getNextPrime(newLimit);if (newPrime 7) newPrime 7;this.length newPrime;// 获取原来所有数据,并且重新放入新的容量数组中// 对数据进行初始化const oldStorage this.storage;this.storage [];this.count 0;// 获取原来的数据,放入新的数组中oldStorage.forEach((bucket) {if (!bucket) return;for (let i 0; i bucket.length; i) {const tuple bucket[i];this.put(tuple[0], tuple[1]);}});}1 、【数据结构与算法——TypeScript】数组、栈、队列、链表 2 、【数据结构与算法——TypeScript】算法的复杂度分析、 数组和链表的对比
