哈希表哈希表（Hashtable，也叫哈希表），是一种根据键（Key）直接访问内存存储位置的数据结构。也就是说，它通过计算键值上的函数来访问记录，该函数将所需的查询数据映射到表中的某个位置，从而加快查找速度。这种映射函数称为哈希函数，存储记录的数组称为哈希表。我们从上图开始分析，有一个集合U，分别是1000、10、152、9733、1555、997、1168，右边是一个有10个slot的列表（哈希表）。我们需要把集合U中的整数存储到这个列表中，存储在哪些槽中？这个问题需要通过哈希函数来解决。我的存储方式是取10的余数，我们看这张图1000%10=0，10%10=0，那么1000和10这两个整数就会存储在0号槽中。152%10=2，然后存入slot2。9733%10=3存入slot3。集合U可能会出现在哈希表中key哈希函数是你设计的一种方法，通过一些计算将集合U中的key值存储在一个哈希表中，比如例子中的余数哈希表，它存储计算出的密钥。那么我们是然后看看我们一般是怎么获取到这个值的？比如我们存一个key为1000，value为'张三'--->{key:1000,value:'张三'}从我们上面的解释来看，是不是应该存到1000%10这个槽中呢？.当我们想通过key查找值张三时，是否可以直接在key%10的槽中查找呢？在这里你可以停下来思考。哈希的一些术语（大家可以简单看一下）哈希表中所有可能的键称为全集U和M表示槽的个数给定一个键，哈希函数计算它应该出现在哪个槽中，上面的例子哈希函数h=k%M，哈希函数h是keyk到slot的映射。1000和10都存储在这个编号为0的槽中。这种情况称为冲突。看到这里，不知道大家对什么是哈希函数有一个大概的了解了。通过例子，通过你的思考，你可以回过头来阅读文章开头的哈希表的定义。如果你能读懂它，那么我想你应该明白了。常用的hash函数处理整数h=>k%M（也就是我们上面举的例子）处理字符串：functionh_str(str,M){return[...str].reduce((hash,c)=>{hash=(31*hash+c.charCodeAt(0))%M},0)}hash算法不是这里的重点，也没有深入研究。这里主要是了解哈希表是什么数据结构，它有什么优点，它到底有什么作用。而哈希函数只是通过某种算法将键映射到列表中。搭建哈希表通过上面的讲解，我们这里来做一个简单的哈希表。哈希表由M个槽组成。有一个散列函数和一个将键值添加到散列表的添加方法。有一个删除方法可以删除。有一种查找的方法，根据key找到对应的value初始化-初始化哈希表有多少个slots-用数组创建M个slotsclassHashTable{constructor(num=1000){this.M=num;this.slots=newArray(num);}}哈希函数是处理字符串的哈希函数。这里之所以用字符串，是因为值也可以转成字符串，比较通用。首先，将传递的键值转换为字符串。将字符串转为数组，例如'abc'=>[...'abc']=>['a','b','c']分别计算每个字符的charCodeAt，取余数Mas为了对应槽的个数，你一共只有10个槽，你的值%10肯定会落在0-9槽中h(str){str=str+'';返回[...str]。reduce((hash,c)=>{hash=(331*hash+c.charCodeAt())%this.M;returnhash;},0)}添加并调用hash函数得到对应的存储地址（即也就是，我们之间类似slot）因为一个slot可能存储多个值，所以需要用一个二维数组来表示。比如我们计算出来的slot的编号是0，也就是slot[0]，那么我们应该去slot[0][0]，如果后面进来同样编号为0的slot，就存入??slot[0][1]添加（键，值）{consth=this.h（键）;//判断这个slot是否为二维数组，如果不是，创建一个二维数组if(!this.slots[h]){this.slots[h]=[];}//将值添加到相应的插槽中this.slots[h].push(值);}通过hash算法删除，通过过滤找到要删除的slotdelete(key){consth=this.h(key);this.slots[h]=this.slots[h].filter(item=>item.key!==key);}通过hash算法找到对应的slot使用find函数找到相同key的值并返回对应的值search(key){consth=this.h（键）；constlist=this.slots[h];constdata=list.find(x=>x.key===key);返回数据？数据值：空；列表的数据结构已经完成。事实上，我们每次学习数据结构或算法时，都不会照搬实现的代码。我们需要学习的是思想，比如哈希表是做什么的？它是一种通过key可以快速找到对应value的存储方式。那么我们就会想，如果我们设计的槽少一些，在同一个槽中存放大量的数据，那么这个哈希表的查找速度肯定会更快。打折，应该用什么方法解决这种情况，或者是否换成其他数据结构。补充一个小知识点。v8引擎中的数组arr=[1,2,3,4,5]或newArray(100)。我们都知道它开辟了一个连续的空间用于存储，而arr=[],arr[100000]=10这种操作就是使用的hash，因为如果这种操作连续开辟100万个空间来存储一个值，显然是浪费空间。后续可能会介绍二叉树。另外，大家可以指出文章中有什么错误或者写得不好的地方。我会继续写一些关于前端的技术文章。喜欢的话可以关注一下，点个赞哦。谢谢
