摘要：散列表散列表，也叫哈希表，是根据键而直接访问在内存存储位置的数据结构。这个映射函数称做散列函数，存放记录的数组称做散列表。
散列表
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
我们从上图开始分析
有一个集合U，里面分别是1000，10，152，9733，1555，997，1168
右侧是一个10个插槽的列表（散列表），我们需要把集合U中的整数存放到这个列表中
怎么存放，分别存在哪个槽里？这个问题就是需要通过一个散列函数来解决了。我的存放方式是取10的余数，我们对应这图来看
1000%10=0，10%10=0 那么1000和10这两个整数就会被存储到编号为0的这个槽中
152%10=2那么就存放到2的槽中
9733%10=3 存放在编号为3的槽中
通过上面简单的例子，应该会有一下几点一个大致的理解
集合U，就是可能会出现在散列表中的键
散列函数，就是你自己设计的一种如何将集合U中的键值通过某种计算存放到散列表中，如例子中的取余数
散列表，存放着通过计算后的键
那么我们在接着看一般我们会怎么去取值呢？
比如我们存储一个key为1000，value为"张三" ---> {key:1000,value:"张三"}
从我们上述的解释，它是不是应该存放在1000%10的这个插槽里。
当我们通过key想要找到value张三，是不是到key%10这个插槽里找就可以了呢？到了这里你可以停下来思考一下。
散列表中所有可能出现的键称作全集U
用M表示槽的数量
给定一个键，由散列函数计算它应该出现在哪个槽中，上面例子的散列函数h=k%M,散列函数h就是键k到槽的一个映射。
1000和10都被存到了编号0的这个槽中，这种情况称之为碰撞。
看到这里不知道你是否大致理解了散列函数是什么了没。通过例子，再通过你的思考，你可以回头在读一遍文章头部关于散列表的定义。如果你能读懂了，那么我估计你应该是懂了。
常用的散列函数处理整数 h=>k%M （也就是我们上面所举的例子）
处理字符串：
function h_str(str,M){
return [...str].reduce((hash,c)=>{
hash = (31*hash + c.charCodeAt(0)) % M
},0)
}
hash算法不是这里的重点，我也没有很深入的去研究，这里主要还是去理解散列表是个怎样的数据结构，它有哪些优点，它具体做了怎样一件事。
而hash函数它只是通过某种算法把key映射到列表中。
通过上面的解释，我们这里做一个简单的散列表
散列表的组成M个槽
有个hash函数
有一个add方法去把键值添加到散列表中
有一个delete方法去做删除
有一个search方法，根据key去找到对应的值
初始化- 初始化散列表有多少个槽 - 用一个数组来创建M个槽
class HashTable {
constructor(num=1000){
this.M = num;
this.slots = new Array(num);
}
}
散列函数
处理字符串的散列函数，这里使用字符串是因为，数值也可以传换成字符串比较通用一些
先将传递过来的key值转为字符串，为了能够严谨一些
将字符串转换为数组, 例如"abc" => [..."abc"] => ["a","b","c"]
分别对每个字符的charCodeAt进行计算，取M余数是为了刚好对应插槽的数量，你总共就10个槽,你的数值%10 肯定会落到 0-9的槽里
h(str){
str = str + "";
return [...str].reduce((hash,c)=>{
hash = (331 * hash + c.charCodeAt()) % this.M;
return hash;
},0)
}
添加
调用hash函数得到对应的存储地址(就是我们之间类比的槽)
因为一个槽中可能会存多个值，所以需要用一个二维数组去表示，比如我们计算得来的槽的编号是0，也就是slot[0]，那么我们应该往slot[0] [0]里存，后面进来的同样是编号为0的槽的话就接着往slot[0] [1]里存
add(key,value) {
const h = this.h(key);
// 判断这个槽是否是一个二维数组, 不是则创建二维数组
if(!this.slots[h]){
this.slots[h] = [];
}
// 将值添加到对应的槽中
this.slots[h].push(value);
}
删除
通过hash算法,找到所在的槽
通过过滤来删除
delete(key){
const h = this.h(key);
this.slots[h] = this.slots[h].filter(item=>item.key!==key);
}
查找
通过hash算法找到对应的槽
用find函数去找同一个key的值
返回对应的值
search(key){
const h = this.h(key);
const list = this.slots[h];
const data = list.find(x=> x.key === key);
return data ? data.value : null;
}
总结
讲到这里，散列表的数据结构已经讲完了，其实我们每学一种数据结构或算法的时候，不是去照搬实现的代码，我们要学到的是思想，比如说散列表它究竟做了什么，它是一种存储方式，可以快速的通过键去查找到对应的值。那么我们会思考，如果我们设计的槽少了，在同一个槽里存放了大量的数据，那么这个散列表它的搜索速度肯定是会大打折扣的，这种情况又应该用什么方式去解决，又或者是否用其他的数据结构的代替它。
补充一个小知识点v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。
后续后续可能会去介绍一下二叉树，另外对于文章有什么写错或者写的不好的地方大家都可以提出来。我会持续的去写关于前端的一些技术文章，如果大家喜欢的话可以关注一下，点个赞哦谢谢
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/100590.html
摘要：哈希表也是种数据结构，它可以提供快速的插入操作和查找操作。一个更好的散列函数为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数，这和计算散列值时使用的取余运算有关。散列函数将学生里的数字相加，使用函数计算出散列值。 什么是字典结构？ 字典是以键值对形式存储数据的数据结构，就像电话号码薄里的名字和电话号码那样的一一对应的关系。 javascript的Object类就是以...
摘要：我经常在业务代码中把数据处理成这种字典的数据结构获取的方法哈希表在学习了类之后，我们会学习散列表，也就是哈希表。 《Javascript数据结构和算法》笔记-「字典和散列表」 集合、字典、散列表存储的都是「不重复」的数据结构 集合：我们更关注每一个元素的值，并把其作为主要元素 字典：我们用[键,值]的形式来存储数据 散列表： 跟字典类似，也会是用[键,值]的形式来存储数据 但是「字...
摘要：简介哈希表又被称为散列表，可能是翻译的问题好多书上一会儿称散列一会儿称哈希，更有甚者煞有介事的对此进行区分。实现哈希表我们将要实现这个类分别实现插入查找删除打印等方法。 1.简介 哈希表(hash table)又被称为散列表，可能是翻译的问题好多书上一会儿称散列一会儿称哈希，更有甚者煞有介事的对此进行区分。经过简单的搜索（wiki链接）发现这两个词是一回事。由此可见学好英语是多么重要。...
摘要：散列表其实是基于数组实现的，可以说，没有数组就没有散列表。根据下图你更能理解散列表哈希函数结合上面的理解，你应该可以想到，其实散列表的关键就在于哈希函数的实现。 1. 什么是散列表？ 散列表（Hash Table）又叫做哈希表，是一种很常用的数据结构。散列表其实是基于数组实现的，可以说，没有数组就没有散列表。先来举一个简单的例子，来认识一下什么是散列表。 假如在学校的运动会上，每个运动...
摘要：小结实现了字典和哈希表感觉没有想象中那么困难，当然这还是开始。 本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算法之二叉搜索树 字典 不是新华字典哦，这里的字典也称作_映射_，是一种数据结构，跟set集合很相似的一种数据结构，都可以用来...
阅读 701·2021-09-29 09:34
阅读 2553·2019-08-30 15:53
阅读 3361·2019-08-29 17:17
阅读 760·2019-08-29 16:08
阅读 1120·2019-08-29 13:03
阅读 951·2019-08-27 10:54
阅读 687·2019-08-26 13:39
阅读 2858·2019-08-26 13:34
