大数据

2018-09-23 1192

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Map-Reduce和Hadoop逐渐称为面试热门。还有，容量的转换如下：bit就是位，也叫比特位，是计算机表示数据最小的单位。byte就是字节，1byte=8bit，1byte就是1B；一个字符=2字节；1KB=1024B字节B到GB是介绍他们之前，我们先来看看什么是哈希函数什么是Map-Reduce。

Map-Reduce和Hadoop逐渐称为面试热门。还有，容量的转换如下：

bit就是位，也叫比特位，是计算机表示数据最小的单位。

byte就是字节，1byte=8bit，1byte就是1B；

一个字符=2字节；

1KB=1024B

字节B到GB是 $10^9$

介绍他们之前，我们先来看看什么是哈希函数

什么是Map-Reduce。map阶段是通过Hash函数将任务分开成若干的子任务，Hash函数可以是用户指定或者系统默认。Reduce阶段是分开处理，然后将子任务合并成结果。

海量数据处理的关键：

案例1

首先用最简单的解决方法，那就是将IP转化为整数然后排序：

但是其实有更高更省空间的方法：

这种做法的解释是这样的：
因为所有的IP只会出现一次，所以可以考虑bitmap数据结构（在Java中就是二进制数组，byte[]）。下面先说一个byte数组的例子。

//只要知道数的取值范围，就可以用bytes数组排序。
//java并没有提供bit这种数据类型,即使最小的数据类型byte,也要
//占到8个bit.(以前从哪里看到过boolean值在不同的jvm实现下面可能是1bit,也可能是8bit)
public static void main(String[] args){
        boolean[] bytes = new boolean[101];
        int[] a = new int[]{76, 22, 11, 98, 93, 45, 65, 43, 76, 2};
        for(int i = 0; i < a.length; i++){
            bytes[a[i]] = true;
        }
        for(int i = 0; i < bytes.length; i++){
            if(bytes[i] == true)
                System.out.println(i);
        }
    }

IPV4中规定IP地址长度为32（按照TCP/IP参考模型划分），即有 $2^{32}$ 个地址。
IPV6协议的地址长度为128位，全部可分配的地址数为 $2^{128}$ 。
申请一个长度为 $2^{32}$ 的bit类型的数组，每个位置是一个bit，只可表示0或者1这两种状态，空间为512MB。每个IP地址转化为无符号整数K，数组下标 $0$ ~ $2^{32-1}$ 与k对应起来。如果k=1，就把bitmap[0] = 1；如果k=n，就把bitmap[n-1]=1。这样，能做到时间复杂度为O(n)，空间复杂度很小。