大数据题目解法

资源限制类题目

哈希函数可以把数据按照种类均匀分流

一个大文件 无符号整数 (2^32^-1 就是 0- 42亿范围）有40亿个数，1g内存求出现次数最多的数是哪一个？

如果使用hash表来做 key - value ,key是(4B),value是int(4B), 一个数就要8B，如果40亿个数都不一样，就需要 320亿B（32G）。

对数据a 先使用 hash函数得到数 b，然后 % 100得到 0-99范围的数，相同的数据进同一个文件，不同的数种类上进不同文件。对每一个小文件使用hash表，然后求出这100个数的最大值。不怕同一种数太多，怕不同种的数太多，内存不够。

布隆过滤器用于集合的建立与查询，并可以节省大量空间

解决黑名单过滤、对100亿url(64Byte)进行黑名单过滤过滤，如果使用hashset,需要640G内存。

爬虫去重，多个线程爬url, 如果已经爬过，就不要再爬，爬虫之间不要爬同一个。

集合有添加、有查询，没有查询、极大程度减少内存使用，允许有一定程度失误率。如果一个数据不在布隆过滤器中，可能会误报，但一个数据在布隆过滤器中，一定不会误报。

一致性哈希解决数据服务 器的负载管理问题

数据服务器怎么组织， 数据种类均匀分配。有3台服务器、一个数据同算hash然后取模方法，觉定这个数据在哪个服务器存储。hash key怎么选择，让高、中、低频的数据均匀分配的key，身份证之类。上面的算法好像可以把图片均衡地分配到不同的服务器,但增加和减少服务器时，如果要重新算hash会造成数据迁移。

概念

决分布式缓存的问题。 在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表中存在的动态伸缩等问题 。

一致性hash算法会建立一个有2^32个槽点(0 - 2^32-1^)的hash环，假设现在有A、B、C三台服务器，以A为例，会进行hash(A)%2^32^，得到一个0 - 2^32-1^之间的数，然后映射到hash环上

接下来，我们以m1为例，我们照样算出hash(m1)%2^32^的值，然后映射到hash环上，然后以该点出发，顺时针遇到的第一个服务器，即为数据即将存储的服务器。

如果这个时候在A - C之间插入了服务器D，请求获取getKey(m1)时，顺时针获得的服务器是D，从D上获取数据理所当然会失败，因为数据存在A上缓存。这样看缓存好像还是失效了。

虽然增加了节点D后，m1的缓存失效了，但是，分布在 A-B，B-C 以及 D-A上面的数据仍然有效，失效的只是C-D段的数据(数据存在A节点，但是顺时针获取的服务器是D)。这样就保证了缓存数据不会像hash算法那样大面积失效，同样起到减轻数据库压力的效果。

一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

hash偏斜

A、B、C服务节点，如果接近于将hash环平均分配那固然理想，但是如果他们hash值十分相近,就会导致某一段直接会被大量分配，给某一节点大量分配，如果这时这个节点被删除，会有大量请求涌向相邻的节点，给这个节点带来巨大压力，这部分缓存也就失效了，导致了缓存雪崩。

如何保证节点的负载均衡？如何保证在添加节点后的负载均衡？

虚拟节点

如果我们的节点足够多，就应该可以防止服务器节点分布不均的问题了。

以A节点为例，虚拟构造出(A0,A1,A2….AN)，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。只要是落在这些虚拟节点上的数据，都存入A节点。读取时也相同，顺时针获取的是A0虚拟节点，就到A节点上获取数据，这样就能解决数据分布不均的问题。

虚拟节点读写大概流程为: 数据读写 -> 虚拟节点 -> 真实节点 -> 读写

利用并查集结构做岛问题的并行计算

参考并查集一节

位图解决某一范围上数字的出现情况，并可以节省大量空间

问题

32位无符号整数的范围是0~4,294,967 ,295,现在有一个正好包含40亿个无符号 整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数?
[进阶]
内存限制为4KB,但是只用找到一个没出现过的数即可

解

准备一个2的32次方的Byte类型的数组要多少空间？ 2^32^/ 8 字节 越500M，这个Byte位置的0代表没出现过，1代表出现过

进价解法

准备4KB的int类型的数组，1个int类型是4字节，4KB/4=1024份，把整个范围 2^32^分为1024份，这个一定可以整除，一份是4194304

整个数组中0位置代表 0 - 4194304出现了多少次，统计完后，有的位置数量会多，一旦某个位置的词频数没有到达4194304，就说明这个范围上缺少数字，在这个范围上再一直分下去，一定可以定位到这个数字

同理如果只有3个位置，那么就对范围一直二分，最后一定可以定位到缺少的数

利用分段统计思想、并进一步节省大量空间

利用堆、外排序来做多个处理单元的结果合并

大数据题目

题目1

有一个包含100亿个URL的大文件，假设每个URL占用64B,请找出其中所有重复的URL
[补充]
某搜索公司一天的用户搜索词汇是海量的(百亿数据量),请设计- -种求出每天热门Top100
词汇的可行办法

解法1：使用布隆过滤器判断url存不存在（可能会有误判）

解法2：hash计算每个url, hash函数特性使相同的url会进同一个文件,每个文件分开统计

top求法，先使用hash分流的方法，分为多个小文件，对多个小文件求Top100,最后对这些小文件的Top100再求Top100(这时就需要使用堆排序)，推排序：先把这些小文件的最大值建立一个堆中，弹出最大的url， 然后找到弹出url所在文件中出现第二多的url放入堆中，再弹出一个，直到弹出100个为止。

题目2

32位无符号整数的范围是0~4294967295,现在有40亿个无符号整数,可以使用最多1GB的
内存，找出所有出现了两次的数。
[补充]
可以使用最多10MB的内存，怎么找到这40亿个整数的中位数?

解法：使用位图，用2位bit位来表示一个数出现的情况 00-没出现，01-出现一次，10，出现2次，11-出现3次及以上，这样内存消耗正好是1GB

补充的解法：以4kb的内存为例，准备4KB的int类型的数组，1个int类型是4字节，4KB/4=1024份，把整个范围 2^32^分为1024份，这个一定可以整除，一份是4194304，整个数组中0位置代表 0 - 4194304出现了多少次；看第20亿位的数落在那个范围内，对这个范围在次进行以上步骤等分为1024份，直到求出中位数。

题目3

有一个10G文件，里面是int类型的无序数，将这个文件内的数进行排序，最多可使用5g内存

使用一个小根堆，这个堆里面存储（数据，数量）占用8字节，堆其他开销算8字节，一共16字节，5G/16字节=2的28次方，这个堆可以存放2的28次方的数据，那么可以把整个范围 2^32^分为2的4次方，每份单独组织小根堆的状况（份和份之间一定是按照顺序来的），然后按照排序后的顺序和数量输出到新文件中，依次计算每份并写入到文件