大数据处理：(
求最大的n个用小根堆，最小的n个用大根堆)
使用mapreduce统计文章中单词出现个数，首先对文章预处理，去掉标点，对连字符-处理，对缩写处理，大小写转换。然后对每个单词进行hash映射，假设映射为10组，对每组中同一种单词进行合并，然后把每组的结果进行合并。
对40亿的ip地址进行排序，每个ip只出现一次可以用bitmap，该map单元个数2的32次方，每个单元只占1bit。jdk1就有了bitset类，但是其中有些方式是jdk4才有的，线程不安全。
有一个包含20亿个全是32位整数的大文件，在其中找到出现最多的数，内存限制2g。对20亿个数使用哈希函数分流，假设分成20个小文件，对每个小文件使用hashmap得到出现最多的数，再从20个文件的20个最多的数中选出最多的。
32位无符号整数最大为42亿多，有一个包含40亿个无符号数的文件，所以必然在32位整数的范围中有没出现的数，最多使用10m内存找到任意一个没出现过的数。可以将42亿的范围分成64个区间，将大文件分成64个小文件，小文件中不足2的32次方/64就说明在该区间有没出现的数。用bitmap统计该区间上的数的出现情况
百亿数据中找到出现最多的100个。同样使用hash函数分流成假设64个子文件，对每一个子文件统计每个数据的次数，然后利用小根堆进行top100的筛选。
工程师常使用服务器集群来设计和实现数据缓存，将数据的id通过哈希函数转换成哈希值，为key。如果机器有n台，key%n就是该数据所属机器的编号。分析这种缓存策略可能带来的问题，并提出改进方案。增加或者删除机器时，数据迁移的代价很大。用一致性哈希算法解决。从0到2的32次方成环，每个数据的key都对应在环中。根据机器id计算出的hash值也在该换中，数据的哈希值顺时针碰到的第一个机器id哈希值，就是对应的机器。
布隆过滤器：使用k个哈希函数对每个要过滤数据，在m范围的bitmap内进行映射。当其它数据经过布隆过滤器的k个哈希函数映射时，每个映射在之前的bitmap中都有，则说明该数据应该被过滤。
PS：全部内容来自牛客网左老师的讲座
阅读(3374) | 评论(0) | 转发(0) |
