哈希算法
2019-02-15 本文已影响0人
宋雾代
什么是哈希算法
了解哈希算法需要了解以下几个概念。
散列表(hash table) 与散列函数
散列表也叫哈希表是一种数据结构,是根据Key-value而直接进行访问的数据结构。也就是说,它通过把Key值映射到表中一个位置来访问value,以加快查找的速度。这个映射函数叫做散列函数。
举个栗子:
我有一个数组记录水果的价格,数组长26。
现在有如下价格需要存储:
水果 | 价格 |
---|---|
Apple | 5.3 |
Banana | 3.7 |
Pear | 4.9 |
那我可以实现一个散列函数f(key),取水果的首字母在字母表中的顺序,放到数组对应的位置。
散列函数 | 数据存放 |
---|---|
f(Apple)=0 | 5.3存放在数组第0个 |
f(Banana)=1 | 3.7存放在数组第1个 |
f(Pear)=15 | 4.9存放在数组第15个 |
冲突、哈希碰撞
如前面所述,散列函数是把key值进行一定计算以后得到散列值,当不同的key值进行计算以后得到散列值一样的话,我们称为哈希碰撞或者冲突。
继续前面的例子,如果我们增加一种水果
水果 | 价格 |
---|---|
Apple | 5.3 |
Banana | 3.7 |
Pear | 4.9 |
Avocado | 7.7 |
按照之前的散列函数,取首字母然后看在字母表的顺序,我们得到的散列值是0,与Apple的散列值一致。而Apple已经使用了第一个格子了,这样就发生了冲突。
解决方法一般如下:
- 线性探测
- 二次探测
- 拉链法
- 双重散列
- 多重散列
以后有机会写文章展开,这里先不展开了。