------HR:The first question is what you do if you have a conflict with your manager ?
------You:Hashmap ! I'll use Hashmap !
------HR:Hash ? Hash ? What ? Have you eaten so many hash browns that your brain becomes into the potato ?
哈希表的结构就是数组,但是它神奇的地方在于对下标值的一种变换，这种变换我们称之为哈希函数,通过哈希函数可以获取到HashCode
什么是哈希化?
将大数字转化成数组范围内下标的过程,我们就称之为哈希化
什么是哈希函数?
通常我们会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中,这个函数我们称为哈希函数
什么是哈希表?
最终将数据插入到的这个数组,对整个结构的封装,我们就称之为是一个哈希表
几乎所有的编程语言都有直接或者间接的应用这种数据结构
哈希表通常是基于数组进行实现的,但是相对于数组,它也很多的优势:
它可以提供非常快速的插入-删除-查找操作
无论多少数据，插入和删除值需要接近常量的时间:即O(1)的时间级.实际上，只需要几个机器指令即可完成
哈希表的速度比树还要快,基本可以瞬间查找到想要的元素
哈希表相对于树来说编码要容易很多
哈希表相对于数组的一些不足:
哈希表中的数据是没有顺序的,所以不能以一种固定的方式(比如从小到大)来遍历其中的元素
通常情况下,哈希表中的key是不允许重复的,不能放置相同的key,用于保存不同的元素
解决冲突的两种方案
链地址法:
链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据,而是一个链条
链条一般使用数组和链表这两种数据结构
比如是链表,也就是每个数组单元中存储着一个链表,一旦发现重复,将重复的元素插入到链表的首端或者末端即可
当查询时,先根据哈希化后的下标值找到对应的位置，再取出链表,依次查询找寻找的数据
使用数组或链表在这里效率都差不多
开放地址法:
线性的查找空白的单元
线性探测:
线性探测就是从index位置+1开始一点点找到合适的位置(空的位置)来放置.查询时从index位置开始进行查找,直到查询到空位置停止.删除时不能讲这个位置的下标设置为null,一般设置为-1,这样看到-1知道查询时继续查询,但插入时这里可以插入
线性探测的问题:
会产生聚集问题.聚集就是一连串的填充单元.聚集会影响哈希表的性能,插入查询删除都会影响,二次探测可以解决部分这个问题
二次探测:
优化了线性探测的步长,比如从下标值x开始,x + 1^2,x + 2^2等,这样可以一次性探测比较长的距离,避免一些线性探测存在的问题
二次探测的问题:
会造成步长不一样的聚集,还是会影响到哈希表的效率.再哈希法可以解决这个问题
再哈希法:
把关键字用另外一个哈希函数,再做一次哈希化,用这次哈希化的结果作为步长,对于指定的关键字,步长再整个探测中是不变的,不过不同的关键字使用不同的步长
第二次哈希化需要与第一个哈希函数不同,且不能输出为0
第二次哈希函数:
stepSize = constant - (key % constant)
其中constant是质数,且小于数组容量
如:stepSize = 5 - (key % 5)
方法选择:
一般开发使用链地址法,它不会因为添加了某元素后性能急剧下降,比如java的Hashmap就用的链地址法
优秀的哈希函数
1.计算速度快,尽量少有乘法和除法,因为他们性能比较低
2.均匀分布,尽可能的将元素映射到不同位置,让元素在哈希表中均匀分布
快速计算:霍纳法则(秦九韶算法)
p(x) = (...(anx + an-1)x + ...)x + a0
例2x^4 - 3x^5 + 5x^2 + x -7转换为
x(x(x(2x - 3) + 5) + 1) -7
这样写只需要N次乘法和N次加法,时间复杂度为O(N)
均匀分布:
使用常量时尽可能使用质数
如:哈希表的长度,N次幂的底数
哈希表长度使用质数不会产生循环,也会让数据在哈希表中更均匀分布.当然在链地址法中质数没那么重要,在java中设置为2^N次幂
注意:
java中使用位运算方式提高HashMap效率,但js中位运算有bug,详情参见js浮点数精度问题(众所周知的0.1 + 0.2 !== 0.3),所以js中用取模.
哈希表容量尽量用质数
// 设计哈希函数
// 1.将字符串转成比较大的数字:hashCode
// 2.将大的数字hashCode压缩到数组范围之内
function hashFn(str, size) {
// 1.定义hashCode变量
let hashCode = 0;
// 2.霍纳算法,来计算hashCode的值
for (let i = 0; i < str.length; i++) {
/* 选择质数 31 41也可以,但用的最多的还是37
这一步相当于霍纳算法的anx + an-1
str.charCodeAt()来获取字符串中某个字符的Unicode编码 */
hashCode = 37 * hashCode + str.charCodeAt(i);
}
// 3.取余操作
const index = hashCode % size;
return index;
}
// 测试哈希函数
alert(hashFn('abc', 7)); // 4
alert(hashFn('cba', 7)); // 3
alert(hashFn('nba', 7)); // 5
alert(hashFn('mba', 7)); // 1