首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >大数据专题

大数据专题

作者头像
故事尾音
发布2019-12-18 17:13:57
3440
发布2019-12-18 17:13:57
举报

哈希函数

哈希函数又叫散列函数,输入范围很大,输出范围固定。 哈希函数的性质:

  • 无限的输入域
  • 输出值相同时,返回值一样
  • 输入值不同时,返回值可能一样,也可能不一样
  • 不同的输入值得到的hash,整体均匀分布在输出域上

1~3是哈希函数的基础,第四点是评价hash函数优劣的关键。

Map-Reduce

  1. map阶段:把大任务分解为子任务
  2. reduce阶段:子任务并发处理然后合并结果

注意点:

  • 数据备份和容灾(需要多少备份)
  • 任务分配策略和任务进度跟踪
  • 多用户权限的控制

Map-Reduce统计文章单词出现的个数

一致性hash

数据的归属问题:数据经过hash计算到环上,如果在中间顺时针到离它最近的机器上

例如上图:data1归属于machine2,data3归属于machine3,data3、data4归属于machine1 机器的添加和删除:一个机器故障,数据顺时针迁移到下一台机器上。添加新的机器的时候添加机器和它逆时针的最近机器之间的数据迁移到添加机器上。

常见海量处理题目的关键

  • 分而治之:通过hash函数把大任务分流到机器,或者分流成小文件
  • 常用hashMap或者bitMap上面

难点在对通讯、时间、空间复杂度的估计

IPV4地址排序

请对10亿个IPV4地址排序,每个ip出现一次 方法:BitMap:

年龄排序

10亿人的年龄排序 方法:计数排序

出现内存中最多的数

有一个包含20亿个全是32位整数的大文件,在其中找到出现次数最多的数.但是内存限制只有2G. 哈希表方案(不可行):

哈希分流(可行):

计算:8字节x2亿 = 1.6G

没出现过的数

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

hashMap方法(不可行):

bitMap方法(不可行):

hash分流

eLwa4g.png
eLwa4g.png

热词Topk

百亿数据量的搜索词汇,设计求每天最热100词的方法 hash分流

eLwNE8.png
eLwNE8.png
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-08-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 哈希函数
  • Map-Reduce
  • 一致性hash
  • 常见海量处理题目的关键
  • IPV4地址排序
  • 年龄排序
  • 出现内存中最多的数
  • 没出现过的数
  • 热词Topk
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档