数据结构(五)哈希表JS实现

哈希表的特点

1.特点

• 基于数组实现
• key值不允许重复
• key，value(键 : 值)形式
• key值可以通过哈希函数转换成下标

2.优势

• 大大提高了数据存储，删除和查询的速度

• **缺点：**空间利用率不高，元素是无序的，查找最值不方便

3.实现哈希表的过程

• 哈希化：将一个大的数字压缩成小数字的过程
• 哈希函数：先将单词转换成大数字，再将大数字哈希化的过程封装进函数中，这个函数就是哈希函数
• 哈希表：最后将数据插入到数组里对应的下标(经过哈希函数转换过的数字)，再对这个数组进行特定的封装就是哈希表

哈希表存在的问题

冲突

在哈希化后不同的数据可能小概率产生相同的地址

解决方案

1.深入链地址法（拉链法）

数组中一个下标存放一个数组或链表保存哈希化后相同地址的不同元素

2.开放地址法

**数组一个地址对应一个元素，当发生冲突时，元素根据步长(不同的探测方法拥有不同的步长)插入到冲突地址之后对应的位置，如果加上步长后还发生了冲突，继续增加直到找到为空的位置

• 线性探测

  ​ 步长为1

  ​ 问题：容易发生聚集（一连串地址相邻）会对插入，查询，删除造成一定影响

• 二次探测

  ​ 步长为1^1,22,3^3…,在线性探测的基础上有一点优化，增加了步长的距离

  ​ **问题：**尽管增加了步长的大小，但还是会形成远距离的聚集

• 再哈希法

  ​ 对关键字使用另一个哈希函数再做一次哈希化，步长是根据关键字形成的不同关键字形成不同步长，StepSize = const - （key % const ）步长不能为0， const为常量并且要取质数

3.两种方式效率的比较

比较效率就是比较一次成功需要的探测次数
计算两种方式的效率需要用到填装因子即表示添加的元素占哈希表总长度的百分比，最大等于1

• 填装因子 = 现有数据项个数 / 哈希表长度
• 链地址法 > 再哈希法 > 二次探测 >线性探测

两种方式的效率都会随着填装因子的增大而不断降低，因为链地址法是线性增加，而开放地址法效率降低是指数级增加的，所以我们一般使用链地址法

提升哈希函数的效率

1.快速计算-霍纳法则

将字符串转换成数字过程中的多项式累加减化其中的乘法和除法，时间复杂度为由O(N^2) - >O(N)

2.均匀分布

将各元素均匀分布在哈希表上，有利于查询，插入，删除的效率，在用到常数的地方使用质数，如再哈希法计算步长的公式里，霍纳法则X的取值，数组容量

为什么扩容

因为随着数据越来越多填充因子越来越接近于1，哈希表的性能也会随之递减，所以需要扩容

怎么扩容

添加哈希表一个新的数组，初始化属性，将旧的数组根据key值填充进新的数组

最后

以上就是敏感背包为你收集整理的数据结构(五)哈希表JS实现数据结构(五)哈希表JS实现的全部内容，希望文章能够帮你解决数据结构(五)哈希表JS实现数据结构(五)哈希表JS实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。