开发者社区> woooow> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

大数据

简介: 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

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


img_f7ec28935271405e28d67f5982f6fabd.png

img_c5429b7c07168d3ccf89bca9f61db1cb.png

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


img_3f265d24104625061a4a789aee1984fe.png

海量数据处理的关键:


img_8acbd066fa7b5d15edd447d40d82764c.png

案例1

img_22e948df43cbdf3c64bc80ec9a6bc75a.png

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


img_40297c2f7f4b103e23bc477a1794832b.png

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


img_6a77e89eebf3652bbb4accfc3a02d02c.png

这种做法的解释是这样的:
因为所有的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),空间复杂度很小。

案例2

img_0e89909ae72ec096d9528ad026c848e5.png

年龄都在0到200之间,所以只需要申请一个长度为200的数组,然后遇到年龄为k的,只需要在数组为k的数加1即可,最后倒出来。


img_7c4c5e19acfc11a9e80dbfd201ed9da3.png

案例3

img_025fe48b85b4d7c77cbbdd4d3a69c569.png

img_326f6fb4eadbfc5e769e249e404cffd5.png

img_d7ed3c52ae52fbbebb3a2e13ee26b2ac.png

案例4

img_79db133378f4070dc6023fa4356c303f.png

下图中的20亿其实为40亿


img_266d21f4e37dcd58b4857b66730c8b5b.png

img_e10b5ef87b149317bd5df24833baf7ad.png

img_d1c2f60f7fa5bd039094dc539b5a7328.png

img_7db55809dd8789b970034ccacfb861c0.png

img_b50c8467bccc1faabd873e2cc761e9df.png

案例5

img_5257a746acb7e33d26cb47292fb990f3.png

img_b5b1ef82b040de61b8f84189b5db72cb.png

案例6

img_273abf99c0cc5394afc95fbd303c95cf.png

img_58a61c1b73bdd77db5c1488747e42697.png

假设id通过哈希函数计算和的结果为
0~2^32
,这些key首尾相连构成环形分布。假设N=3台机器根据哈希函数也在环中,那么id为1的数据顺时针知道距离最近的机器,id1的所有删除、添加查询操作都在这上面。
img_7236fa172d5b53b5a72be7c192eac4e7.png

img_01c06974f5b8e85125b7c600d68a09dd.gif

img_3ee5ab4f783c32bd21efe1e7951e5ca4.png

假如添加机器m3,经过哈希函数计算m3的机器id在m1和m2中间。那么data1数据原来实在m2上操作的,现在变成m3上操作,并且将m2的data1的旧数据迁移到m3上。

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

相关文章
大数据入门
大数据入门
10 0
大数据初了解
了解大数据行业
8 0
初识大数据
了解大数据
28 0
大数据:大数据之数组
好程序员:大数据培训分享实用大数据之数组1.5.1 数组的定义与元素访问 数组是一个容器, 是一个用来存储指定数据类型的容器注意事项: 数组是一个定长的容器, 一旦实例化完成, 长度不能修改名词解释: 数组长度: 指的就是这个容器的容量, 表示这个数组中能存储多少个数据 元素: 指的就是数组中.
568 0
操作大数据集
一、子查询插入数据 1、语法INSERT INTO table [ column (, column) ] subquery; 2、说明:    您可以使用INSERT语句向一个表中添加行,其中的值来自于查询结果集。
1023 0
掘金大数据
无论是否出于你的意愿,数据正在每天为你做着人生笔记:你去了哪里?看到了什么?做了什么?你的性格喜好?与谁联络?心情如何?……这些通通可以从你的网络浏览记录、交易记录、手机通话记录、联通视频记录、收发邮件记录、社交网络记录等等当中获得,你在网络上的每一个“足迹”都会以数据的形式被记录并存储下来,它们精准及时、事无巨细。
1199 0
+关注
woooow
我不生产bug,我只是bug的搬运工
文章
问答
文章排行榜
最热
最新
相关电子书
更多
大数据在新制造领域的应用
立即下载
数据安全助力大数据产业发展
立即下载
大数据在旅游业中的应用初探
立即下载