什么是哈希算法|散列函数|哈希函数？

举个例子，比如这里有一万首歌，给你一首新的歌X，要求你确认这首歌是否在那一万首歌之内。

无疑，将一万首歌一个一个比对非常慢。但如果存在一种方式，能将一万首歌的每首数据浓缩到一个数字(称为哈希码)中，于是得到一万个数字，那么用同样的算法计算新的歌X的编码，看看歌X的编码是否在之前那一万个数字中，就能知道歌X是否在那一万首歌中。

作为例子，如果要你组织那一万首歌，一个简单的哈希算法就是让歌曲所占硬盘的字节数作为哈希码。这样的话，你可以让一万首歌“按照大小排序”，然后遇到一首新的歌，只要看看新的歌的字节数是否和已有的一万首歌中的某一首的字节数相同，就知道新的歌是否在那一万首歌之内了。

当然这个简单的哈希算法很容易出现两者同样大小的歌曲，这就是发送了碰撞。而好的哈希算法发生碰撞的几率非常小。

解决碰撞是一个复杂问题。碰撞主要取决于：

(1)散列函数，一个好的散列函数的值应尽可能平均分布。

(2)处理碰撞方法。

(3)负载因子的大小。太大不一定就好，并且浪费空间严重，负载因子和散列函数是联动的。

解决碰撞的办法：

(1)线性探查法：冲突后，线性向前试探，找到近期的一个空位置。缺点是会出现堆积现象。存取时，可能不是同义词的词也位于探查序列，影响效率。

(2)双散列函数法：在位置d冲突后，再次使用还有一个散列函数产生一个与散列表桶容量m互质的数c，依次试探(d+n*c)%m，使探查序列跳跃式分布。

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

散列函数能使对一个数据序列的訪问过程更加迅速有效，通过散列函数，数据元素将被更快地定位：

1. 直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，当中a和b为常数(这样的散列函数叫做自身函数)

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

3. 平方取中法：取keyword平方后的中间几位作为散列地址。

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

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

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

哈希算法的应用

从专业的角度来说，哈希算法是用来解决数据和数据之间对应关系的一种算法。它的初衷是用来加速数据存取。

计算机领域内的大多数查找算法都与存储数据的规模呈正相关，用于衡量查找算法效率的量我们称为平均查找长度，一般情况下，比较优秀的查找算法的平均查找长度也不会短于数据规模以2为底的对数哈希算法中，我们把数据项中的关键字用一种特定的对应关系和存储数据项的地址或地址偏移量对应起来。注意：这种对应一般不是一一对应，因为不可能有足够多的地址对应近乎无穷多的关键字。这样一来，当我们知道数据关键字的时候，在大多数情况下可以在常数时间(与数据规模无关的常数)内存取这个关键字。其他的时候，有可能发生多个关键字占据同一地址的现象，我们称之为碰撞。这种情况下需要对关键字进行二次或更多次的处理(如果发生多次碰撞)，所费时间在最差情况下也只与规模成正比。

那什么是hash映射呢?简单来说，就是为了便于计算机在有限的内存中处理big数据，我们通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小数存放在内存中，或大文件映射成多个小文件)，而这个映射散列方式便是我们通常所说的hash函数，设计的好的hash函数能让数据均匀分布而减少冲突。

1、海量日志数据，提取出某日访问百度次数最多的那个IP

分析：百度作为国内第一大搜索引擎，每天访问它的IP数量巨大，如果想一次性把所有IP数据装进内存处理，则内存容量明显不够，故针对数据太大，内存受限的情况，可以把大文件转化成(取模映射)小文件，从而大而化小，逐个处理。

换言之，先映射，而后统计，最后排序。

解法：具体分为以下3个步骤

1.分而治之/hash映射?

首先把这一天访问百度日志的所有IP提取出来，然后逐个写入到一个大文件中，接着采用映射的方法，比如%1000，把整个大文件映射为1000个小文件。

2.hash_map统计?

当大文件转化成了小文件，那么我们便可以采用hash_map(ip, value)来分别对1000个小文件中的IP进行频率统计，再找出每个小文件中出现频率最大的IP。

3.堆/快速排序?

统计出1000个频率最大的IP后，依据各自频率的大小进行排序(可采取堆排序)，找出那个频率最大的IP，即为所求。

注：Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是%1000算法，那么同一个IP在hash后，只可能落在同一个文件中，不可能被分散的。