《算法图解》读书笔记5-散列函数及扩展

散列函数

散列函数就是一种映射,是从关键字到存储地址的映射。通常,包含散列函数的算法的算法复杂度都为O(1),对应到Python中的数据结构就是字典,给一个key可以得到一个固定的value值。散列函数必须满足一些要求:

  • 它必须是一直的。例如,假设输入apple时得到的是4,那么每次输入apple时,都必须是4,不然这个散列函数就是无意义的;
  • 散列函数应该将不同的输入值,对应到不同的值上。(虽然不同的key对应相同的value是允许的,但最理想的情况是不同的key,对应不同的value,这种称之为完美散列

在python中创建一个散列函数(字典):

>>> book = dict()

散列函数广泛应用于网站缓存应用。比如我们常常开发网站应用时,为了提高网站访问速度,避免频繁去查询数据库获取数据,就会应用到redis作为缓存,将访问量高的网页以键值对的形式存储起来。(redis是一种key-value型的Nosql数据库)。基本上所有的大型网站都会使用缓存,缓存的数据就存储在散列表中。

散列函数扩展知识

特性

所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数。但另一方面,散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同,这种情况称为“散列碰撞(collision)”,这通常是两个不同长度的输入值,刻意计算出相同的输出值。输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。[引自wikipedia]

应用

散列函数应用很广泛,常见的有以下场景:

  • 模拟映射关系,防止重复
  • 网站缓存

  • 安全加密

  • 负载均衡

提高散列表性能

提高散列表性能需要考虑两个方面因素:

  • 较低的填装因子
  • 良好的散列函数,可以是数据均匀分布,避免冲突

填装因子

散列表的填装因子计算方法:

填装因子 = 散列表包含的元素数 / 位置总数

如果散列表使用数组来存储数据,假如一共申请了10个内存,存储了两个数据,那么这个散列表的填装因子就是0.2,如果数据填满10个,那么填装因子就是1,再如果数据量超出了10个,那么填装因子将大于1,这时候就需要在散列表中添加位置,称之为“调整长度”。降低填装因子的值,才能减小散列冲突的出现概率。一个不错的经验规则是:

一旦填装因子大于0.7,就调整散列表的长度。

常用的构造散列函数的方法

直接寻址法

取key或key的某个一次函数解作为散列地址。Hash(key) = key 或者Hash(key) = a*key + b

数字分析法

分析一组数据,比方一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体同样,这种话,出现冲突的几率就会非常大,可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大,假设用后面的数字来构成散列地址,则冲突的几率会明显减少。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

平方折中法

取key平方后的中间几位作为地址

折叠法

将key切割成位数同样的几部分,最后一部分位数能够不同,然后取这几部分的叠加和(去除进位)作为散列地址。

随机数法

选择一随机函数,取key的随机值作为散列地址,通经常使用于keyword长度不同的场合。

除留余数法

取key被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 Hash(key) = key MOD p, p<=m。不仅能够对key直接取模,也可在折叠、平方取中等运算之后取模。对p的选择非常重要,一般取素数或m,若p选的不好,很容易产生同义词。

参考链接

  • https://zh.wikipedia.org/zh-hans/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8
  • http://www.cnblogs.com/mengfanrong/p/4034950.html

— EOF —

交流

☕️赞助一杯咖啡☕️

取消

感谢支持,一起进步!

扫码支持
你的支持是对我的认可

打开 支付宝 扫一扫

Scroll to top