大数据的刷题必备

介绍哈希函数

哈希函数又叫散列函数，哈希函数的输入域可以是非常大的范围，但是输出域是固定范围，假设为s。

哈希函数的性质：

典型的哈希函数都拥有无限的输入值域。
输入值相同时，返回值一样。
输入值不同是返回值可能一样可能不一样。
不同的输入值得到的哈希值，整体均匀的分布在输出值域s上。（重要）

1 ~ 3 点性质是哈希函数的基础，第4点是评价一个哈希函数优劣的关键。

哈希函数

介绍Map-Reduce

Map 阶段 --> 把大任务分成子任务。
Reduce 阶段 --> 子任务并发处理，然后合并结果。

难点：工程上的处理

注意点：

备份的考虑，分布式存储的设计细节，以及容灾策略。
任务分配策略与任务进度跟踪的细节设计，节点状态的呈现。
多用户权限的控制。

示例：用 Map-Reduce 方法统计一篇文章中每个单词出现的个数

1、文章的预处理 - 将有效的单词全部抓取出来

预处理

2、 map 阶段 - 划分子任务

map阶段

3、 reduce 阶段 - 子任务并行处理

reduce阶段

常见海量数据题目解题关键

1、分而治之。通过哈希函数将大任务分流到机器，或分流成小文件。

2、常用到的数据结构有 hashMap 和 bitmap。

难点：通讯、时间和空间的估算。

案例一、请对10亿个IPV4的ip地址进行排序，每个ip只会出现一次。

分析：

先看一下普通的方法，既然要排序，先把10亿个ip地址都转换为整数，然后在排序。一个整数需要4个字节的内存，10亿个大约就要有4G的内存，虽然我们的电脑一般都有超过4G的内存，但是这种算法的性能还是太低了。

仔细思考一下，IPV4的ip总数量大约是 42 亿个，我们要对10亿个ip进行排序，需要排序的个数和可能有的总数相差不大，而且每个ip只出现一次，所以可以考虑用bitmap。

算法：

可以申请一个有42亿byte的bitmap，然后对10亿个ip地址进行遍历，如果出现则对应的字节值设为1，否则设为0。一次遍历之后就可以根据bitmap，遍历bitmap的每一个byte即可确定出ip的排序。

IPV4排序

代码：

#include<iostream>
#include<fstream>

using namespace std;

typedef unsigned char byte;

void sort_ip(char[] input_url,char[] output_url)
{
    byte bitmap[2 << 32];
    char buffer[256];
    ifstream in(input_url);
    if(!in.is_open())
    {
        cout << "Error opening input file.";exit(1);
    }
    while(!in.eof())
    {
        in.getline(buffer,100);
        bitmap[ip2int(buffer)] = 1;
    }
    ofstream out(output_url);
    if(out.is_open())
    {
        for(int i = 0; i < 2 << 32; ++i)
        {
            if(bitmap[i] == 1)
            {
                out << int2ip(i);
            }
        }
    }
    else
    {
        cout << "Error opening output file.";exit(1);
    }
}

int ip2int(char[] ip)
{
    // 将ip地址转换为整形
}

int int2ip(int ip)
{
    // 将整形转换为ip地址
}

案例二：请对10亿人的年龄进行排序。

分析：

年龄我们大概可以确定是在 1 ~ 200 这个范围内（据说彭祖活了800多岁，但是我们只算现代人）。而且这里只是说对年龄进行排序而不是说对个人信息按照年龄来排序，所以我们可以使用计数排序。

算法：

申请一个长度为200的 int 数组（int取值为42亿左右），遍历每个年龄，记录下每个年龄出现的次数，即可实现排序。

案例三：有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，内存限制为2G。

分析：

对于统计次数，首先想到的应该就是hashmap了，但是仔细分析一下，hashmap的一条记录要包含一个key和一个value，因为有20亿个数，所以为了保证不会溢出，key和value都至少是int32类型。如果这20亿个数都不同的话，就有20亿条记录，一条记录8字节大约需要16G的内存，会导致内存不足。所以我们需要先将大文件分流成小文件，然后再使用hashmap。根据上面分析，最少要分成8个文件。

算法：

用哈希函数把大文件分流成16个小文件，因为哈希函数的输入值相同时返回值一样，所以相同的一个数不会被分到不同的文件中，又因为不同的输入值得到的哈希值，整体均匀的分布在输出值域上，所以每个文件上的整数数量不会相差太多，近似于平均分配，所以小文件上不会发生溢出。分成小文件后对小文件上的数进行统计，得出最大数量的数，然后再拿所以小文件得出的结果进行比较，得出结果。

题目四：

32位无符号整数的范围是 0 ~ 4294967295 。现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没有出现的数。可以使用最多10M的内存，只用找到一个没有出现过的数即可，该如何找？

题目五：

某搜索公司一天的用户搜索词汇量是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行方法。

题目六：

工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略。 1、无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，记为key。 2、如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、查询还是删除操作，都只在这台机器上进行。请分析这种缓存策略可能带来的问题，并提出改进的方案。

矩阵·空间