前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >海量数据面试题总结(2)-BitMap

海量数据面试题总结(2)-BitMap

作者头像
小萌哥
发布2020-07-20 15:38:08
1.1K0
发布2020-07-20 15:38:08
举报
文章被收录于专栏:算法研习社

本系列文章对海量数据面试题进行了归类和总结,给出海量数据处理问题的通用解决思路,后面附有例题,希望大家能够举一反三。

模式二:BitMap

所谓BitMap就是用一个bit位来标记某个元素所对应的value,而key即是该元素,由于BitMap使用了bit位来存储数据,因此可以大大节省存储空间。

一、BitMap基本思想

用一个简单例子来介绍BitMap算法原理。假设要对0-7内的5个元素[4,7,2,5,3]进行排序(元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数,我们需要8个bit。

1. 首先我们开辟一个字节(8bit)的空间,将这些空间的所有bit位都设置为0;

2. 然后遍历这5个元素,第一个元素是4,因为下边从0开始,因此我们把第五个字节的值设置为1;

3. 然后再处理剩下的四个元素,最终8个字节的状态如下图:

4. 现在我们遍历一次bytes区域,把值为1的byte的位置输出(2,3,4,5,7),这样便达到了排序的目的。

二、解决思路

1. 先确定每个数字的存储空间。如int32类型的每个数字需要32位存储空间,共有2^32种数,需要2^32=4G的连续内存空间才可以将所有数字一一表示。

2. 如果所需内存空间够小或可以满足计算需求,直接用BitMap算法,遍历每个数i,将a[i]置为1。

3. 根据不同情况,对a的键进行排序或查找某个键。

三、经典例题

1. 在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。

采用2-BitMap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit = 8GB内存。然后扫描这2.5亿个整数,查看BitMap中相对应位,如果是00变01,01变10,10保持不变。扫描完后,查看BitMap,把对应位是01的整数输出即可。

2. 给40亿个不重复的int型整数(32位),乱序,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

用BitMap的方法,申请4GB的内存,一个bit位代表一个int值。遍历40亿个数,设置相应的bit位为1。读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法研习社 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 模式二:BitMap
    • 一、BitMap基本思想
      • 二、解决思路
        • 三、经典例题
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档