哈希函数和哈希表

笔者在读研刚开始的时候,偶尔看面经,有这样一个问题:只用2GB内存在20亿个整数中找到出现次数最多的数,当时的我一脸懵逼,怎么去思考,20亿个数?What The Fuck! 但是,看完今天的文章,你或许就会觉得原来也不过如此啊!其核心就是哈希函数和哈希表的应用!

哈希函数

哈希函数又称为散列函数,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。假设输出值域为S,哈希函数的性质如下:

  1. 典型的哈希函数都有无限的输入值域
  2. 当哈希函数输入一致时,输出必相同
  3. 当哈希函数传入不同的输入值时,返回值可能一样,也可能不一样,由于输入域远大于值域
  4. (重要)很多的不同输入所得的输出值会均匀的分布在S上(但不是绝对均匀)

最后一个性质对于一个优秀的哈希函数是非常重要的,并且这种均匀与数据的输入规律无关。比如“aa1”、"aa2"经过hash后可能结果会相差很多,当一个哈希函数的输出在S中是均匀的,那么我们将输出值对m取余(%m),就会将不定长输入映射到0~m-1空间中,并且在这个空间也保持均匀分布!哈希表就是这么做的,一会再说!哈希函数还有以下特点:

  1. 免碰撞:即不会出现输入 x≠y ,但是H(x)=H(y) 的情况,其实这个特点在理论上并不成立,比如目前比特币使用的 SHA256 算法,会有2^256种输出,如果我们进行2^256 + 1 次输入,那么必然会产生一次碰撞,事实上,通过 理论证明 ,通过2^130次输入就会有99%的可能性发生一次碰撞,不过即使如此,即便是人类制造的所有计算机自宇宙诞生开始一直运算到今天,发生一次碰撞的几率也是极其微小的。
  2. 隐匿性:也就是说,对于一个给定的输出结果 H(x) ,想要逆推出输入 x ,在计算上是不可能的。如果想要得到 H(x) 的可能的原输入,不存在比穷举更好的方法。

常见的哈希函数有:SHA1、MD5、SHA2等

哈希函数映射

哈希表

哈希表就是利用哈希函数,可以根据关键码而直接进行访问的数据结构,也就是将关键码(Key value)通过哈希函数映射到表中的一个位置来进行访问。由于是直接访问,所以对于哈希表的元素理论上的增删改查时间复杂度都是O(1)。

而计算散列地址的方法有很多种,通常我们使用的是除留余数法,也就是说使用哈希函数对关键字得到的输出值对散列表长度取余得到的余数即为散列地址。

哈希冲突

由于我们的输入长度和范围是任意的,但是经过哈希函数后的输出值域是固定的,所以必然会产生冲突。如上图的buckets152(红色区域)就相当于发生冲突!处理冲突的方法有:

  • 开放地址法
  • 再散列法
  • 公共溢出法
  • 拉链法(经典、重点)

我们来说下拉链法,也如上图所示,拉链法的思路很简单,就是当发生哈希冲突后,会在当前地址区域建立一个链表,将冲突目标添加到链表中去。这种方式也不太好,当冲突发生过多时,链表的查找方式效率也就不是很高了! 因此对于JAVA中(C++标准中没有hashmap,只有第三方的),hashmap的实现也是类似,但是有一点改进,也就是如果发生冲突,将冲突对象添加到链表,假设冲突个数达到了8次,那么就会使用红黑树来代替链表,以加快查找速度。冲突个数少时,没有必要使用红黑树

C++中的hash_map

c++的hash_map和map的用法很类似,但一定要区别,map和hash_map虽然都是key-value形式,但是map的底层是红黑树,而hash_map的底层是hash表! 如果在Linux下使用hash_map,一定要加上一个__gnu_cxx的命名空间声明!

#include<iostream>
#include<hash_map>

using namespace __gnu_cxx;    // Linux下使用时,需要加上这句话才可以使用hash_map.

using namespace std;

int main(int args, char** argv){
    hash_map<int, string>* has = new hash_map<int, string>;
    has->insert(make_pair(32, "zhang"));
    has->insert({0, "teddy"});     // 两种插入元素的方法

    auto res = has->find(0);
    auto res2 = has->find(32);
    cout << res->second << endl;
    cout << res2->second << endl;

    return 0;
}

题目:2G内存下在20亿数据中找到出现次数最多的数

首先我们确定value的范围,如果一个数出现了20亿次,那么value就为20亿次。因此我们使用32位的正整型,也就是4B的空间,同理key也是4B的空间,因此一条记录(Entry)需要8B的空间,当记录为20亿个时,需要至少16GB的内存。 在极端最差的状态,20亿个数都不相同,那么哈希表中可能会有20亿条记录,这样的话显然内存不足,因此一次性统计20个数风险很大。 解决方案:将包含有20亿个数的大文件分成16个小文件,利用哈希函数,这样的话,同一个重复的数肯定不会分到不同的文件中去,并且,如果哈希函数足够好,那么这16个文件中不同的数也不会大于2亿(20 / 16)。然后我们在这16个文件中依次统计就可以了,最后进行汇总得到重复数最多的数。当然如果使用分布式系统,那么可以利用哈希函数将这些数据分配到不同的电脑上去! 资源链接

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java技术大本营

java练习本(2019-07-21)

“ Love is the greatest refreshment in life. ”

6820
来自专栏曌的晓痴

LeetCode - 两数相加

原题地址: https://leetcode-cn.com/problems/add-two-numbers/

9150
来自专栏曌的晓痴

LeetCode-下一个排列

感觉从之前的题目开始写起来的话,会需要一定的时间去思考当时为什么这么写,那么每次写都是重新思考,除非进度能够赶上最新的刷题进度,所以决定从最新的开始往前写......

9030
来自专栏曌的晓痴

LeetCode - 最长回文子串

同样是三年前做的一道题目,很经典的字符串领域的算法题,求字符串的最长回文子串,当时我也是提交了好几次,并且看了相关的资料以后,才成功通过。

11220
来自专栏曌的晓痴

LeetCode - Z字形变换

又双叒叕是三年前做的题目了,只有题目序号很大的,才是最近做的。因为最近做的都是些Easy模式的,用于找回感觉。

5810
来自专栏曌的晓痴

LeetCode - 两数之和

开启新的一个篇章,LeetCode题解,个人的一些解题思路分享(可能有的题目就是这么菜,之后慢慢更,可以先把自己做完的100多题每天1题的方式先发出来,一遍更一...

7330
来自专栏猪圈子

postman日记之断言篇

上帝:我记得有个故事,讲的是一个邮递员杀人的事情I remembered a particular story about a postman who was ...

23770
来自专栏志学Python

用数字数数字符串

最近一直在想一个好办法来写文章,想来想去还是用使用案例的方式来写这些文章,这样就不是干巴巴的一些知识点,没多大意思,从今天开始,我们就进来细学Python的基础...

6830
来自专栏志学Python

图解算法系列(四):链表

链表是由许多相同的数据类型的数据项按照特定的顺序排列而成的线性表,链表的特点是各个数据项在计算机内存中位置是不连续而且随机存放的,其优点是数据的插入或者删除都相...

9830
来自专栏曌的晓痴

LeetCode - 无重复字符的最长子串

这题仍然是3年前的作品,中等难度的一道题目,每次看自己以前写的代码,毫无注释,然后重新去理解自己的思路,去写解题思路真是痛苦啊...以后得慢慢补上这些注释.

7140

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励