首页
学习
活动
专区
工具
TVP
发布

经典算法bitmap算法

概述 本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说BitMap的特点已经在各个场景的使用性...Bit-Map算法 先看看这样的一个场景: 给一台普通PC,2G内存,要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数,给出一个整数,问如果快速地判断这个整数是否在文件40亿个数据当中?...bitmap = new BitMap(100); bitmap.add(7); System.out.println("插入7成功"); boolean...isexsit = bitmap.contain(7); System.out.println("7是否存在:"+isexsit); bitmap.clear(7);...然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。

1.1K30
您找到你想要的搜索结果了吗?
是的
没有找到

牛逼的Bitmap算法

给定长度是10的bitmap,每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。 2....要问此时bitmap里存储了哪些元素?显然是4,3,2,1,一目了然。 Bitmap不仅方便查询,还可以去除掉重复的整型数。 1. 建立用户名和用户ID的映射: 2....按照年龄标签,可以划分成90后、00后两个Bitmap: 用更加形象的表示,90后用户的Bitmap如下: 这时候可以直接求得非90后的用户吗?直接进行非运算?...同样是刚才的例子,我们给定90后用户的Bitmap,再给定一个全量用户的Bitmap。最终要求出的是存在于全量用户,但又不存在于90后用户的部分。 如何求出呢?...2.如果同学们有兴趣,可以亲自去阅读源码,甚至是尝试实现自己的Bitmap算法。虽然要花不少时间,但这确实是一种很好的学习方法。

3.7K10

漫画:什么是Bitmap算法

给定长度是10的bitmap,每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。 2....把整型数4存入bitmap,对应存储的位置就是下标为4的位置,将此bit置为1。 3. 把整型数2存入bitmap,对应存储的位置就是下标为2的位置,将此bit置为1。 4....把整型数1存入bitmap,对应存储的位置就是下标为1的位置,将此bit置为1。 5. 把整型数3存入bitmap,对应存储的位置就是下标为3的位置,将此bit置为1。...要问此时bitmap里存储了哪些元素?显然是4,3,2,1,一目了然。 Bitmap不仅方便查询,还可以去除掉重复的整型数。 1. 建立用户名和用户ID的映射: 2....让每一个标签存储包含此标签的所有用户ID,每一个标签都是一个独立的Bitmap。 3. 这样,实现用户的去重和查询统计,就变得一目了然: 1. 如何查找使用苹果手机的程序员用户? 2.

36220

漫画:Bitmap算法 整合版

给定长度是10的bitmap,每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。 2....把整型数1存入bitmap,对应存储的位置就是下标为1的位置,将此bit置为1。 5. 把整型数3存入bitmap,对应存储的位置就是下标为3的位置,将此bit置为1。...按照年龄标签,可以划分成90后、00后两个Bitmap: 用更加形象的表示,90后用户的Bitmap如下: 这时候可以直接求得非90后的用户吗?直接进行非运算?...同样是刚才的例子,我们给定90后用户的Bitmap,再给定一个全量用户的Bitmap。最终要求出的是存在于全量用户,但又不存在于90后用户的部分。 如何求出呢?...2.如果同学们有兴趣,可以亲自去阅读源码,甚至是尝试实现自己的Bitmap算法。虽然要花不少时间,但这确实是一种很好的学习方法。

37420

理解BitMap算法的原理

BitMap 的思想的和原理是很多算法的基础,比如 Bloom Filter、Counting Bloom Filter。...看到这里,如果熟悉排序算法里面计数排序,那么我们就能发现原理非常类似,不同的是使用bitmap排序占用的存储空间更小,但缺点是不支持重复数字。...来看一下关于BitMap算法一些处理大数据问题的场景: (1)给定40亿个不重复的 int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中。...解法2:采用两个BitMap,即第一个Bitmap存储的是整数是否出现,接着,在之后的遍历先判断第一个BitMap里面是否出现过,如果出现就设置第二个BitMap对应的位置也为1,最后遍历BitMap,...总结 本文主要介绍了BitMap算法的基本原理和应用案例,其本质上是采用了bit位来表示元素状态,从而在特定场景下能够极大的节省存储空间,非常适合对海量数据的查找,判重,删除等问题的处理。

6.5K41

干货 | 漫画:什么是Bitmap算法

给定长度是 10 的 bitmap,每一个 bit 位分别对应着从 0 到 9 的 10 个整型数。此时 bitmap 的所有位都是 0。 ? 2....把整型数1存入bitmap,对应存储的位置就是下标为1的位置,将此bit置为1。 ? 5. 把整型数3存入bitmap,对应存储的位置就是下标为3的位置,将此bit置为1。 ?...要问此时 bitmap 里存储了哪些元素?显然是 4,3,2,1,一目了然。 Bitmap 不仅方便查询,还可以去除掉重复的整型数。 ? ? ? ? ? ?...同样是刚才的例子,我们给定 90 后用户的 Bitmap,再给定一个全量用户的 Bitmap。最终要求出的是存在于全量用户,但又不存在于 90 后用户的部分。 ? 如何求出呢?...如果同学们有兴趣,可以亲自去阅读源码,甚至是尝试实现自己的Bitmap算法。虽然要花不少时间,但这确实是一种很好的学习方法。

1K20

漫画:Bitmap算法 进阶篇

上一期漫画分享了Bitmap算法的基本概念,小伙伴们的互动十分积极,在此很感谢大家的热情。 没看过上一期漫画的朋友们可以点击下面的链接: 漫画:什么是Bitmap算法?...按照年龄标签,可以划分成90后、00后两个Bitmap: 用更加形象的表示,90后用户的Bitmap如下: 这时候可以直接求得非90后的用户吗?直接进行非运算?...同样是刚才的例子,我们给定90后用户的Bitmap,再给定一个全量用户的Bitmap。最终要求出的是存在于全量用户,但又不存在于90后用户的部分。 如何求出呢?..., as the bitmap may need to be rewritten....2.如果同学们有兴趣,可以亲自去阅读源码,甚至是尝试实现自己的Bitmap算法。虽然要花不少时间,但这确实是一种很好的学习方法。

18210

算法与数据结构专场】BitMap算法介绍

这种采用一个二进制位来存储数据的方法,我们也叫做bitmap算法。 可能有人会问,假如我要添加一个数n,我知道它要存在第n个位那里,把第n个二进制改为1,可是我要怎么操作呢?...这个对于bitmap算法是如何存储的,如何进行增删操作的,我会在之后的文章里讲,这篇就大概介绍下bitmap算法。...Java中有自带的bitmap实现,今天我们就用Java中自带的bitmap来做道题练练手。我们换道类似题目吧,不知道你一眼是否就能想到用bitmap算法来做。...我们采用bitmap算法来做。不过这里50亿个数,别人肯定是以文件流的形式给你的。这样我们为了方便,我们就假设这些数是以存在int型数组的形式给我们的。...算法的应用不仅仅是节省内存,它还有很多其他的优点。

60920

⑥【bitmap 】Redis数据类型: bitmap

个人简介:Java领域新星创作者;阿里云技术博主、星级博主、专家博主;正在Java学习的路上摸爬滚打,记录学习的过程~ 个人主页:.29.的博客 学习社区:进去逛一逛~ ⑥Redis bitmap...Bitmap支持的最大位数是232位,它可以极大的节约存储空间,使用512M内存就可以存储多达42.9亿的字节信息(232 = 4294967296) 常见使用场景: 用户是否登陆过(Y/N) 电影、视频...、广告等是否被点击播放过 上班打卡签到 1. setbit 设置偏移量的值(值只能0和1) setbit key offset value # bitmap的偏移量是从0开始的,值只能是0或1 # 将偏移量...8的值设为1 bitmap bm1 8 1 2. getbit 获取指定偏移量的值 getbit key offset # bitmap的偏移量是从0开始的,值只能是0或1 # 获取指定偏移量的值 getbit...bm1 0 getbit bm1 8 3. strlen 统计字节数占用多少 strlen key # bitmap的偏移量是从0开始的,值只能是0或1 # 按照8偏移位一组算一个byte,设置同一组偏移位

16010

算法与数据结构专场】BitMap算法基本操作代码实现

上篇我们讲了BitMap是如何对数据进行存储的,没看过的可以看一下【算法与数据结构专场】BitMap算法介绍 这篇我们来讲一下BitMap这个数据结构的代码实现。...在Java的bitMaP实现中,它采用的是用一个long数据来进行存储的。一个long占用8个字节,即64bit,所以一个long可以存储64个数。...如何向bitmap中添加一个数值 我们先来说说如何在bitmap中如何添加一个数值的问题,例如我们我们要添加n=14。...例如我们只在bitmap存储1个数,并且存的数值是2000000000,我们就会在第2000000000个二进制把0改为1。也就是说arr数组的大小至少为2000000000/8+1。...所以说,像我们上面的那种写法可以说是暴力写法,没有经过任何优化,实际上,在Java自带的bitMap中是有很多优化的,并不会像我们上面实现的代码一样那么浪费空间资源。有兴趣的可以研究下。

45430

Bitmap详解

1.bitmap占多少内存 getByteCount()方法是在API12加入的,代表存储Bitmap的色素需要的最少内存。...来解码图片,如果被复用的Bitmap的内存比待分配内存的Bitmap大,那么getByteCount()表示新解码图片占用内存的大小(并非实际内存大小,实际大小是复用的那个Bitmap的大小),getAllocationByteCount...()表示被复用Bitmap真实占用的内存大小 2.如何计算Bitmap占用的内存 通常情况下认为 bitmap占用的内存 = width * height * 一个像素所占的内存。...Log.i(TAG, "bitmap_setParams:ByteCount = " + bitmap_setParams.getByteCount() + ":::bitmap_setParams:AllocationByteCount...3.Bitmap如何压缩 inSampleSize 设置inSampleSize之后,Bitmap的宽、高都会缩小inSampleSize倍。

1.4K30
领券