哈希函数1：用于资源限制类机器统计文件或词频

提示：咱们这几篇文章重点讲哈希函数，这些个知识点，用来跟互联网大厂的面试官聊的，不用写代码！

文章目录

• 哈希函数1：用于资源限制类机器统计文件或词频
• • @[TOC](文章目录)
• 什么是哈希函数？
• f%N仍然满足（5）性质：均匀分布
• 用哈希函数统计文件或者词频
• 总结

什么是哈希函数？

Hash函数译为哈希函数，又称散列函数。

是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出的值称为散列值或消息摘要。
简单来说就是一种将任意长度的输入消息压缩成某一固定长度的消息摘要的函数。

它具备以下的性质（哈希函数所必须的性质）：

（1）f的输入无限：可应用于任意大小的数据块。
（2）f的输出有限：产生定长的输出。
（3）f没有随机性，同样的输入一定是同样的输出
（4）多对一：f对不同的输入，可能是同样的输入，因为（1）（2）导致输入很多，但是输出固定那么些
（5）f有均匀性或分散性：输入不同，但是输出是离散均匀分布在输出域中的；

对任意给定的x，计算f(x)比较容易，用硬件和软件均可以实现。

咱们来解释（1）–（5）的特性
（1）f的输入无限：可应用于任意大小的数据块。
你的输入可以是任意的长度：

（2）f的输出有限：产生定长的输出。
不论（1）的长度是0，还是N，还是无穷大，哈希函数的输出都是固定长度的M长

（3）f没有随机性，同样的输入一定是同样的输出
不是说，本次x进入，输出y，下次x同样的进去，f就输出z了，不是，而是同一个x就是同一个y永远固定的对应关系，没有随机性！
比如下面绿色x，永远输出都是y，不动的。

（4）多对一：f对不同的输入，可能是同样的输入，因为（1）（2）导致输入很多，但是输出固定那么些
由于输入实在是太多，但是输出固定长度，肯定很多的输入，对应就是同一个输出的，比如下面绿色x，粉色x1，都可能对应同一个输出y
即哈希函数是多对一的映射

（5）f有均匀性或分散性：输入不同，但是输出是离散均匀分布在输出域中的；
简单来说，就是你往一个区域丢米，这个米，在桌子上是随机分布的，均匀分布的
你拿个盘子，到处扫描桌子，桌子上，任意位置盘子扫描到的小区，米粒的数量大致相等的
这就是分散均匀，看图：
黑框是桌子，粉框是盘子
经过哈希函数映射的输出是随机均匀分布在黑框里面的
你盘子到处移动都没关系，你到哪，盘子里面的米粒数量都是大致相等的，比如都是5个

哈希函数就是这样必须满足（1）-（5）这几个性质的函数！

有很多，很多，比如：MD5，SHA系列等等

f%N仍然满足（5）性质：均匀分布

根据上面（5），咱们扩展一下：
f%N仍然满足（5）性质，无非就是将f全部转移到0–N-1的范围上均匀分布了

这个性质用处大了！
这个性质用处大了！
这个性质用处大了！

用哈希函数统计文件或者词频

现有你有一台机子：内存资源就1G=1024M=1024*1024字节=10^8次方字节=1亿字节
你有一个文件，内部有40×10^8次字节数据=40亿字节，都是存的数字int，每一个数字占用4字节空间
请你用这台机子统计一下，到底哪个数字出现的次数最大？

分析：
你要我用1亿字节容量的机子，给你统计40亿字节容量的文件？
我们如果用哈希表直接统计key：value的话，key是int数字x，x的次数是value
万一每一个数字x都是不同的数字，那你需要40亿容量的key……
这显然一台机子放不下呀！

那就要想办法切分成40份，怎么切呢？

顺序读取40亿字节的文件，将所有数字x通过哈希函数f的到y，y再模N=40
根据f%40均匀分布的特点，
其实我们将可能不同的数字x和z，经过f直接映射为同一个数y，统计y的词频
当然，同一个数字x多次出现，经过f会映射出同一个数字y来，这样哈希表正常统计y的词频就是x的词频。

而且分布在0–39号小文件的数字种类大致差不多
每个文件的容量在1亿左右，刚刚好够一个机子放下

因此呢，咱们就0–39号一个一个文件，输入机子，找词频最高的，更新给max，
最终就利用一台容量不大的机子，搞定了40亿字节容量的词频统计。

如何，哈希函数是不是功能超级强大啊？

总结

提示：重要经验：
（1）哈希函数f的输入无限：可应用于任意大小的数据块。
（2）哈希函数f的输出有限：产生定长的输出。
（3）哈希函数f没有随机性，同样的输入一定是同样的输出
（4）哈希函数多对一：f对不同的输入，可能是同样的输入，因为（1）（2）导致输入很多，但是输出固定那么些
（5）哈希函数f有均匀性或分散性：输入不同，但是输出是离散均匀分布在输出域中的；
6）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。