Map-Reduce和Hadoop逐渐称为面试热门。还有,容量的转换如下:
- bit就是位,也叫比特位,是计算机表示数据最小的单位。
- byte就是字节,1byte=8bit,1byte就是1B;
- 一个字符=2字节;
- 1KB=1024B
- 字节B到GB是
介绍他们之前,我们先来看看什么是哈希函数
什么是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参考模型划分),即有个地址。
IPV6协议的地址长度为128位,全部可分配的地址数为。
申请一个长度为的bit类型的数组,每个位置是一个bit,只可表示0或者1这两种状态,空间为512MB。每个IP地址转化为无符号整数K,数组下标 ~ 与k对应起来。如果k=1,就把bitmap[0] = 1;如果k=n,就把bitmap[n-1]=1。这样,能做到时间复杂度为O(n),空间复杂度很小。
案例2
年龄都在0到200之间,所以只需要申请一个长度为200的数组,然后遇到年龄为k的,只需要在数组为k的数加1即可,最后倒出来。
案例3
案例4
下图中的20亿其实为40亿
案例5
案例6
假设id通过哈希函数计算和的结果为
假如添加机器m3,经过哈希函数计算m3的机器id在m1和m2中间。那么data1数据原来实在m2上操作的,现在变成m3上操作,并且将m2的data1的旧数据迁移到m3上。