哈希函数

1. 性质

经典Hash函数模型：out = f（in）

• 性质一：in的输入域无穷，比方说可以传入任意长度的字符串。但是在有些工程中也会给输入域规定范围。
  
• 性质二：out的输出域相对有限，比如MD5算法的输出域是 [ 0，(2^64)  - 1 ]；SHA1算法的输出域是 [ 0，(2^128)  - 1 ]；在Java中规定Hash算法的输出域是 [ 0，(2^32)  - 1 ]。可以认为输出域很大，但是一定是有穷尽的。

为什么Hash函数需要具备以上两种性质，就是因为在实际工程中面临很多这样类似的问题，比如：我们需要一个函数，无论传递给函数传入什么信息，最终都能被函数处理得到一个十六进制数。因此，如果我们使用MD5算法，那么最终得到的结果是一个长度为16的十六进制数；如果我们使用SHA1算法，那么最终得到的结果是一个长度为32的十六进制数。

• 性质三：输入相同的in，输出的out也相同。比如多次将"abc"传入Hash函数，那么Hash函数返回的值都是一样的。表示Hash函数中没有任何随机的成分。
  
• 性质四：因为in的输入域无穷，out的输出域有限，所以一定会有不同的in，输出相同的out。这种情况叫做Hash碰撞，Hash碰撞的几率特别低，但是是存在的。
  
• 性质五：无论有多少个in传入Hash函数，最终输出的out在输出域上都是均匀离散的。从而保证了均匀性和离散性。

均匀性：设定多个等规模的out输出域的真子集，使用这些真子集映射到输出域中，会发现每一个真子集中out的数量都是一样的。

离散性：in对应的out在输出域中是没有规律的。即使in非常像，out都不会有相似。

如果离散性不存在，那么可以通过输入相似的in，让输出域上出现某一个区域的集中，这样均匀性也不会存在。所以均匀性和离散型是同时存在，相辅相成的。

如果一个Hash函数的离散型和均匀性越好，该Hash函数就越优秀。

2. 推广

哈希函数有如下推广：

假设输入样本为in1，in2，in3...，通过Hash函数得到out1，out2，out3...（假设没有碰撞），然后我们给每一个out添加一个去%m的操作，得到m1，m2，m3... 。由于性质五，我们可知out在输出域上是均匀离散的，那么%m之后，可以保证m在 [ 0，m-1 ] 这个范围上也是均匀离散分布的。

根据推广，我们可以解决一些典型的工程问题。

题目：假设有一个大文件，该文件中存储了40亿个无符号整数，已知每一个无符号整数的范围是：[ 0，(2^32) - 1 ]，转化成10进制是 [ 0，42亿多 ]。如果只有1G的内存，如何得到文件中出现次数最多的那个数？

分析：

这道题，如果使用Java来解，我们通常想到的经典解法是利用Java中的HashMap。Key是Integer类型，表示文件中的数；Value是Integer类型，表示该数出现的次数。然后我们从头到尾遍历该文件，遍历结束后，HashMap中最大Value对应的Key就是出现次数最多的那个数。

但是，该题目只给了1G的内存，那么使用HashMap来做够不够用呢？

已知HashMap中的一条记录有两个空间，包括Key的空间和Value的空间，Key和Value都是int类型都是4个字节，因此HashMap中一条记录最起码需要8个字节。除此之外，HashMap内部存储索引还需要一部分空间，我们假设索引没有占用空间。40亿个数，最差情况是40亿个数都不一样，这样HashMap中就要存储40亿条记录。每一条记录8个字节，40亿条记录一共需要320亿字节，折合32G的内存空间。因此，不能使用Java中提供的HashMap来做本题。

我们发现，HashMap空间的占用，只和Key的种类数有关，在本题中就是和文件中数字的种类数有关，相同种的数多次出现是不会增加HashMap的占用空间的，修改一下对应的Value就可以实现（HashMap的词频压缩）。所以在本题中，我们并不害怕某个数出现很多次，而是害怕有很多个不一样的数字。

解决方案：

将文件中所有的数传入Hash函数，计算出40亿个out，将out依次%100，得到一个0 ~ 99范围的数。创建0 ~ 99号文件，将%100后的out存储到对应号的文件中。假设最坏情况有40亿个不相同的数字，我们也可以保证0 ~ 99号文件中每个文件存储的数字数量和种类分布都是差不多的。

然后，对每一号文件单独使用HashMap进行处理。如果40亿条记录放在一个文件中使用HashMap处理需要32G的内存，而40亿条记录均匀分布在一百个文件中，对其中一个文件使用HashMap处理则仅需要320M的内存。我们一号一号文件进行处理，这样就会保证内存不会被占满。每一号文件在HashMap处理后都会有一个出现次数最多的那个数，同时相同的数肯定只会出现在同一号文件里。因此在所有文件处理完之后，就会得到100个出现次数最多的数，而且100个数都不相同。最后在这100个数中找出出现次数最多的那个数就是最终的答案。