js 哈希表 01

哈希表介绍

注意：

这里的 无顺序 和 key不允许重复 是不是很熟悉？没错，就是集合和字典的特点，这就是为什么集合和字典可以基于哈希表！

什么是哈希表？

视频中讲述了三个例子，这里菜鸟就不一一列举了，主要说的就是需要一种办法：使得知道值而直接返回出对应的下标值，那么效率就会变得很高！

但是怎么将不确定的值（比如：字符串、数字等）和下标值找出对应的关系呢？

字符串转下标

方法一：数字相加

方法二：幂的连乘

总结：

第一种方案产生的下标太少，导致会有多个字符串公用一个下标；第二种方案产生的下标太多，导致浪费空间（基本上内存创造不出那么大的数组）。

所以上面两个都不能很好的解决问题！这就要引出哈希化了，什么是哈希化？

哈希化

这里应该这样理解：

类比字母放入700…00个数组范围内，但是并不是每一个位置都有正确的英文字母，正确的英文是随机出现的且只有50000个。那么现在再来看0 ~ 199，假设其实只有5个数是需要的，然后这5个数是随机的，取余之后放入的是长度为10的数组（0 ~ 9），所以余数相同概率确实很小。

理解：

1. 哈希化就是将大数（幂的连乘）转化为小数（取模/余），且减少重复（解决重复）或者不重复的一个过程
2. 哈希函数就是哈希化过程实现的一个函数代码
3. 整个函数与返回结果的封装就是一个哈希表

如何解决重复？

链地址法（拉链法）

开放地址法

线性探测

二次探测

注意：

1. 这里连续插入元素余数为2的情况，比前面插入连续的数的情况要更加少，所以该方法还是要强一点！但是还是不好！
2. 菜鸟认为的缺陷不是很准确，具体看到后面再哈希的质数重要性才知道，他是循环探测的，如果大于就再从头开始！

再哈希法

这里理解不和第一个哈希函数相同（菜鸟感觉视频有点问题）：

如果还和原来的一样，那么2-22-122结果还是都余二，那么最后还是每个都移动两格，最后就和二次探测类似了！

这里质数很关键，质数可以让分布更加均匀！

哈希化效率

开放地址法

线性探测效率

二次探测和再哈希 – 这两个差不多 > 线性

链地址法

优秀的哈希函数

优化 – 幂的连乘

注意：

计算算法复杂度 不用考虑系数 ！

优化 – 均匀分布（质数）

再哈希的质数重要性 – 哈希表长度

java中的hashmap

总结

学了这么多，其实感觉大致知道了哈希表是个什么东西以及流程！

这里会有两个问题：

1. 为什么JavaScript中进行较大的位运算时会出问题？
2. 怎么写出哈希表？