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

2018.06.02 16:20 algorithms Linux

散列函数

散列函数就是一种映射，是从关键字到存储地址的映射。通常，包含散列函数的算法的算法复杂度都为 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选的不好，很容易产生同义词。

参考链接

— EOF —