数据结构与算法哈希表基础(实现哈希表的构造和查找算法)
简单案例
如何存储50000个单词？
方案一： 数组
缺点是得到一个单词（比如java），想知道这个单词的位置十分困难，查找效率非常低下。
方案二： 链表
参考数组的查找难度，链表自不必说。
关于数组与链表的相关概念，可以参考【数据结构与算法】数组与链表
方案三：
将单词转成数组的下标，那么之后想要查找某个单词的信息就只要直接通过下标值来访问到对应的元素信息。
比如现在有java，python，go，swift这几个单词，将其分别转成对应的数组下标。如：
java -> 1000 python -> 2000 go -> 3333 swift -> 4000 复制代码
如此转换，当需要查找单词python的时候，就能直接知道其下标值为2000，进一步访问到想要的元素。
哈希表
哈希表就是上述方案三的具体实现，下面是哈希表的定义：
哈希表又叫散列表；是根据键（Key）而直接访问在内存存储位置的数据结构。 它通过计算出一个键值的函数，将所需查询的数据映射到表中某一个位置来让人访问。
哈希表的结构就是数组，因为它用的是数组支持按照下标随机访问数据的特性，但它的不同之处，在于对下标值的转换，这种转换是通过哈希函数来进行的，这个转换的过程就是哈希化，存放记录的数组就是哈希表。
因此，哈希表通常基于数组实现的，但是对于数组而言有较大的优势：
可以提供非常快速的
插入、删除、查找操作。查询、插入和删除的时间复杂度为O(1)。（如果在哈希冲突的概率升高的情况下，时间复杂度将会增加）
哈希函数
哈希函数又叫散列函数、散列算法，简单点来说，就是用于计算对应关键字（Key）的哈希值的方法。
基本的哈希函数需要满足以下几个要求：
1.计算得到的哈希值是一个非负整数（因为数组下标是从0开始的，所以哈希函数生成的哈希值也要是非负整数。）
2.同一哈希函数下，如果输入的两个key相同，那么生成的两个哈希值也相同
3.同一哈希函数下，如果输入的两个key不同，那么生成的两个哈希值也不同（最好是两个key之间哪怕相差很小，所生成的哈希值也是差别非常大的）
当然，优秀的哈希函数需要兼具以下几点：
1.快速的计算
哈希表的优势在于效率，需要通过快速的计算来获取元素对应的哈希值。提高效率的一个方法就是尽量少的乘法和除法运算。
2.均匀的分布
尽可能地将元素映射到不同的位置，减少哈希冲突，让元素在哈希表中均匀分布，一般来说：哈希值越长的哈希算法，哈希冲突的概率越低。
3.难以反推原始数据
这点主要是对于用于安全加密的哈希算法来说的，防止原始数据的泄露。
可以通过下图来展示案例中方案三的实现以及哈希表的生成
方便复制，hashFun函数代码：
function hashFun (str, size) { var hashCode = 0 for (var i = 0; i < str.length; i++) { hashCode = 37 * hashCode + str.charCodeAt(i) } var index = hashCode % size return index } 复制代码哈希冲突
哈希表是通过哈希函数来进行对Key值的转换来获取对应数组中存储下标的值，但是哪怕再好的哈希函数也不能避免输入两个不同的Key但是生成相同哈希值的情况，这种情况就叫做哈希冲突。
比如上面的hashFun函数，当执行hashFun('react', 7)和hasFun('go', 7)时，其返回值都为2，这就造成了哈希冲突。
解决哈希冲突常用的方法有以下几种：开放寻址法、链地址法、双重散列
开放寻址法
思想： 如果出现了哈希冲突，就重新探测一个空闲位置，将元素插入。
其中一个比较简单的探测方法就是线性探测。所谓线性探测，就是当某个数据（Key）经过哈希化之后，存储位置已经被占用了，那我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
除了数据的插入之外，数据的查找与删除也有其特别的地方：
查找
按照线性探测的寻找插入位置的逻辑，将单词'go'和'react'分别存在数组下标为2和3的位置，当需要查找单词'react'的时候，通过hashFun所得到的数组下标值为2，但是实际上'react'存储的位置为数组下标值3的位置。
在实际查找时，如果下标值为2的位置不是'react'，那么就要再查找下一个位置，直到查到单词'react'或者下一个位置的数据为空为止。
删除
一般来说，删除数据只要将需要删除的数据置为空就行了，但是对于这里的删除，为了查找的操作不出问题，需要在删除的时候增加一个删除标记（假设标记为deleted）。
因为在查找时，如果通过线性探测的方法，找到一个空的位置，我们就可以认定该哈希表中不存在这个数据，但是如果这个位置是后来删除的，并且为空，就会导致查找操作出现问题。
假如上述单词'go'，'react'，'vue'分别存在数组下标为2，3，4的位置，当我删除'react'，即将下标为3的位置置为空，那么当我要查找单词'vue'时，就会因为找到下标为3的位置的值是空的原因，从而返回'vue'这个值不存在的结果，导致查找操作出现问题。
所以在删除单词'react'的时候，需要给位置3增加一个deleted删除标记，从而使其继续向下查找单词'vue'。
线性探测存在的问题
线性探测存在一个比较严重的问题，就是聚集。
假如当前已经将单词'go'，'react'，'vue'存到数组2，3，4的位置，我再存一个单词'less'，其哈希值为3，但是数组中3的位置已经存在'react'，4的位置也有'vue'，那么'less'就只能存到数组下标为5的位置，这样就导致我在查找'less'的时候，明明知道其下标为2，但是还是需要向下查找3个位置才能找到它。
所以当插入的数据越来越多时，哈希冲突发生的可能性会越来越大，空闲的位置也会越来越少，线性探测的时间会越来越久，极端情况下查找的时间复杂度为O(n)，从而影响哈希表的性能。
其他探测方法： 对开放寻址法，除了线性探测之外还有其他两种探测方法：二次探测、再哈希法
二次探测
线性探测的探测步长是1，也就是说在进行查找、插入、删除操作的时，每次在当前位置没有找到对应元素的时候，就对数组下标+1的位置进行查找。
而二次探测就是对这个探测步长做了优化，比如从下标值x开始，线性探测的探测过程是x+1，x+2，x+3，而二次探测就是x+1²，x+2²，x+3²。这样就可以一次性探测比较长的距离，一定程度上优化了线性探测。
再哈希法
再哈希法其实也是对探测步长进行的一次优化，它的做法就是把关键字用另一个哈希函数再进行一次哈希化，而这次哈希化的结果作为这次的探测步长。并且对于指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用的步长也不同。
第二次哈希化需要具备以下特点：
和第一个哈希函数不同
不能输出为0（输出为0的话每次探测都是原地踏步，算法就进入了死循环）
一般可以采用以下公式来计算所需要探测的步长：
步长 = constant - (key % constant)，其中constant为质数，且小于数组的容量，key是关键字。这样做的好处是探测步长不可能为0。
特别的是，再哈希法需要哈希表的容量也是一个质数，那这是为什么呢？
因为如果哈希表的容量不是质数，假设它为10，那么根据步长公式，当key为0，步长为5的时候，它的探测路线就是0，5，0，5，0，5如此循环，永远只会去尝试这两个位置。
而如果哈希表的容量是13，当key为0，步长为5的时候，它的探测路线就是0，5，10，2，7，12，4，9，1，6，11，3，就能够查找到哈希表中每一个位置。
这里在key为0，步长为5的时候，其实是根据0，5，10，15，20，25....来查找的，但是跟哈希表的长度之间有一个取模操作，就变成了0，5，10，2，7.....11，3。
装载因子
装载因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值；装载因子越大，说明哈希表中空位越少，冲突越多，哈希表的性能会下降。
装载因子的计算公式为： 装载因子 = 元素填充个数 / 哈希表的长度
开放寻址法注意点： 上述开放寻址法所使用的各种探测问题，都是在其探测步长上做文章。存储和查找都是按照其对应的探测方法进行。（PS：是存储和查找，之前误以为是查找按照对应的探测方法进行，而存储是线性探测的方式存，这个理解有问题）
链地址法（链表法、拉链法）
所谓链地址法，就是在数组每个单元中存储一个链表（也可以是数组），一旦发现重复的的元素，就将这个元素插入到链表（数组）的首端或者末端。
图中数组的每一项可称之为桶（bucket）或者槽（slot），其分别对应一条链表（或一个数组）。
双重散列
双重散列就是使用多个哈希函数来对需要插入的元素的下标值进行计算，先使用第一个哈希函数hashFun1，如果计算得到的对应数组中的位置已被占用，那么就是用hashFun2计算得到一个新的存储位置，直到找到空闲的存储位置。
哈希表扩容
在装载因子过大时，哈希表的性能就会有所下降，这时候就要对哈希表进行扩容。
扩容方式：
直接申请容量为原来两倍的内存空间，然后将所有数据重新通过哈希函数计算并插入到新的哈希表中。
申请完内存空间之后，将扩容操作穿插在插入操作的过程中，分批完成。即当有新数据要插入时，就将新数据插入新的哈希表中，并且从老的哈希表中拿出一个数据放入到新哈希表中。如此重复上面的过程，就能够将老的哈希表中的数据一点一点搬移到新哈希表中。这样做可以解决一次性扩容所带来的耗时过多的情况。
JS实现哈希表
实现要点：
通过链地址法解决冲突（用数组实现存储）
装载因子大于0.75时进行扩容
哈希函数使用上文的hashFun
function HashTable () { this.storage = [] // 数组，存放相关元素 this.count = 0 // 当前已存储元素个数 this.limit = 7 // 哈希表总长度 // loadFactor // 哈希函数 HashTable.prototype.hashFun = function (str, size) { var hashCode = 0 for (var i = 0; i < str.length; i++) { hashCode = 37 * hashCode + str.charCodeAt(i) } var index = hashCode % size return index } // 哈希表的插入和修改是同一个函数，如果原来不存在该key，就是插入操作，如果存在key，就是修改操作。 HashTable.prototype.put = function (key, value) { // 根据key获取index索引值 var index = this.hashFun(key, this.limit) // 根据index取出对应的桶（bucket） var bucket = this.storage[index] // 判断该bucket是否为null，如果是null，就创建一个bucket if (bucket == null) { bucket = [] this.storage[index] = bucket } // 判断是修改数据还是插入数据 for (var i = 0; i < bucket.length; i++) { var item = bucket[i] // item的格式是[key, value]，因此取key值使用item[0]，对比是否存在key，如果存在，就修改对应的value，即item[1] if (item[0] === key) { item[1] = value return } } // 进行添加操作 bucket.push([key, value]) this.count++ // 判断是否需要进行扩容操作 if (this.count > this.limit * 0.75) { this.resize(this.limit * 2) } } // 获取操作 HashTable.prototype.get = function (key) { // 先根据key获取对应的索引值 var index = this.hashFun(key, this.limit) // 再根据索引值获取bucket的值 var bucket = this.storage[index] // 判断bucket是否为null，如果是null，说明key不存在，返回null if (bucket === null) return null // bucket存在，通过for循环查找value的值是否存在 for (var i = 0; i < bucket.length; i++) { var item = bucket[i] // item的格式是[key, value]，因此取key值使用item[0]，对比是否存在key，如果存在，就返回对应的value if (item[0] === key) { return item[1] } } // 不存在对应的key，说明元素不存在，返回null return null } // 删除操作 HashTable.prototype.delete = function (key) { // 先根据key获取对应的索引值 var index = this.hashFun(key, this.limit) // 再根据索引值获取bucket的值 var bucket = this.storage[index] // 判断bucket是否为null，如果是null，说明key不存在，返回null if (bucket === null) return null // bucket存在，通过for循环查找value的值是否存在 for (var i = 0; i < bucket.length; i++) { var item = bucket[i] // item的格式是[key, value]，因此取key值使用item[0]，对比是否存在key，如果存在，就删除对应的value if (item[0] === key) { bucket.splice(i, 1) this.count-- return item[1] } } // 不存在对应的key，说明元素不存在，返回null return null } // 判断哈希表是否为空 HashTable.prototype.isEmpty = function () { return this.count === 0 } // 获取哈希表元素的个数 HashTable.prototype.size = function () { return this.count } // 哈希表扩容，这里使用将所有数据一次性重新计算后插入到新哈希表中的方法来实现 Hashtable.prototype.resize = function (newLimit) { // 保存原来的内容 var oldStorage = this.storage // 重置所有属性 this.storage = [] this.count = 0 this.limit = newLimit // 遍历oldStorage中所有的bucket for (var i = 0; i < oldStorage.length; i++) { // 取出对应的bucket var bucket = oldStorage[i] // 判断bucket是否为null，是null的话就跳过这次循环进行下一次循环 if (bucket === null) continue // bucket中有数据，那么取出数据，重新插入 for (var j = 0; j < bucket.length; j++) { var item = bucket[j] this.put(item[0], item[1]) } } } } 复制代码代码中获取bucket这部分内容可以稍作封装优化。
小小总结
哈希表跟数组的存储方式类似，只不过数组的下标是根据0，1，2...依次存储的，但是哈希表是需要通过哈希函数将对应的Key转换成对应数组下标来存储。
因为通过哈希函数转换的数组下标会重复，所以会造成哈希冲突，解决冲突的方法有：
开放寻址法、链地址法、双重散列哈希函数的设计是哈希表实现非常重要的一步，它需要满足以下几个点：
难以反向推倒
对数据输入非常敏感，两个数据之间相差很小但最后得到的哈希值需要大不相同
尽可能减小哈希冲突的概率
计算效率要尽量高效
伪原创工具 SEO网站优化 https://www.237it.com/
作者：囫囵吞桃
链接：https://juejin.cn/post/7035564773848645668