哈希函数又叫散列函数,输入范围很大,输出范围固定。 哈希函数的性质:
1~3是哈希函数的基础,第四点是评价hash函数优劣的关键。
注意点:
Map-Reduce统计文章单词出现的个数
数据的归属问题:数据经过hash计算到环上,如果在中间顺时针到离它最近的机器上
例如上图:data1归属于machine2,data3归属于machine3,data3、data4归属于machine1 机器的添加和删除:一个机器故障,数据顺时针迁移到下一台机器上。添加新的机器的时候添加机器和它逆时针的最近机器之间的数据迁移到添加机器上。
难点在对通讯、时间、空间复杂度的估计
请对10亿个IPV4地址排序,每个ip出现一次 方法:BitMap:
10亿人的年龄排序 方法:计数排序
有一个包含20亿个全是32位整数的大文件,在其中找到出现次数最多的数.但是内存限制只有2G. 哈希表方案(不可行):
哈希分流(可行):
计算:8字节x2亿 = 1.6G
32位无符号整数的范围是0~4294967295。现在有一个正好包含40亿个无符号整数的文件,所以在整个范围中必然有没出现过的数。可以使用最多10M的内存, 只用找到一个没出现过的数即可,该如何找?
hashMap方法(不可行):
bitMap方法(不可行):
hash分流
百亿数据量的搜索词汇,设计求每天最热100词的方法 hash分流