学习
实践
活动
工具
TVP
写文章

BitMap 算法

什么是 BigMap 算法 所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value,而 key 即是这个元素。由于采用bit为单位来存储数据,因此在可以大大的节省存储空间。 算法思想 32位机器上,一个整形,比如 int a; 在内存中占32bit,可以用对应的32个bit位来表示十进制的0-31个数,bitmap算法利用这种思想处理大量数据的排序与查询。 map映射表 假设需要排序或者查找的总数N=10000000,那么我们需要申请的内存空间为 int a[N/32 + 1].其中a[0]在内存中占32位,依此类推: bitmap表为:

1.2K60

经典算法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的整数输出即可。

61730
  • 广告
    关闭

    年末·限时回馈

    热卖云产品年终特惠,2核2G轻量应用服务器6.58元/月起,更多上云必备产品助力您轻松上云

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

    牛逼的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算法。虽然要花不少时间,但这确实是一种很好的学习方法。

    2.8K10

    漫画:什么是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.

    8220

    漫画: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算法。虽然要花不少时间,但这确实是一种很好的学习方法。

    10320

    理解BitMap算法的原理

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

    2.5K30

    干货 | 漫画:什么是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算法。虽然要花不少时间,但这确实是一种很好的学习方法。

    55220

    漫画:Bitmap算法 进阶篇

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

    5610

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

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

    46720

    Roaring Bitmap更好的位图压缩算法

    Array Container 存放稀疏的数据,Bitmap Container 存放稠密的数据。 Bitmap Container 第二种 Container 是 Bitmap Container。 由于每个 Bitmap Container 需要处理低 16 位数据,也就是需要使用 Bitmap 来存储需要 8192 B(2^16/8), 而一个 Long 值占 8 个 B,所以数组大小为 1024 因此一个 Bitmap Container 固定占用内存 8 KB。 可以看到元素个数达到 4096 之前,Array Container 占用的空间比 Bitmap Container 的少,当 Array Container 中元素到 4096 个时,正好等于 Bitmap

    4.7K71

    浪客剑心:位图法Bitmap算法分析

    屏幕飞快的刷新着,测试时间约是:6295.3601MS 总结 判断集合中是否存在重复元素或者查找缺失元素是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可,位图法Bitmap

    79260

    BitMap

    ---- 面试题海量数据处理经常出现BitMap,所以记一下笔记 1. BitMap BitMap也称为位图,其原理和布隆过滤器类似,其基本原理都是使用位数组及其下标来表示某些元素是否存在,其在处理大量数据的排序、查询、去重,以及在用户群做交集和并集运算的时候也有极大的便利 其时间复杂度为O(N),比一般的排序算法都快 且空间利用率高,在普通情况下10亿个整数占用空间3.8G,而位图占用120MB左右 2. bitmap = new BitMap(100); bitmap.add(10); System.out.println("是否存在10:"+ bitmap.contain (10)); bitmap.clear(10); System.out.println("是否存在10:" + bitmap.contain(10)); } }

    20120

    BitMap算法和Java的实现类BigSet

    针对第一种应用场景,通常的做法就是采用明细表来记录每一个访问量,然后统计每天的用户数(用一个用户,多次访问,只算一个)。

    81640

    Algorithms_算法专项_Bitmap原理及应用

    分治: 内存要求也不满足 bitmap ? 布隆过滤器? 这两个是可以的 我们这里先用bitmap来解决这个问题 ---- 基础知识回顾 Algorithms_数据结构与算法_位运算符的巧技一二事 ---- Bitmap 计算不同存储类型需要开辟的内存空间 在计算机科学中 = new ArtisanBitMap(300000000); bitMap.add(2); bitMap.add(300000000); // 判断是否存在 ("2是否存在: " + bitMap.find(2)); } } ---- 测试 ? ---- bitmap优缺点总结 优点 BitMap的时间复杂度是O(1), 高效 占用内存少 ,空间复杂度 ---- 缺点 数据最好不要重复。

    14630

    算法与数据结构专场】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中是有很多优化的,并不会像我们上面实现的代码一样那么浪费空间资源。有兴趣的可以研究下。

    30430

    Bitmap 详解

    时的一些注意事项 Bitmap recycler 相关 在Android中,Bitmap的存储分为两部分,一部分是Bitmap的数据,一部分是Bitmap的引用。 (bitmap); 还可以从BitmapDrawable中获取Bitmap对象 Bitmap bitmap = new BitmapDrawable.getBitmap(); drawable转换成Bitmap ; bitmap.getHeight() > reqHeight) {           bitmap = Bitmap.createBitmap(bitmap, 0, 0, reqWidth, reqHeight);       } else {           bitmap = Bitmap.createBitmap(bitmap, 0, 0, bitmap.getWidth(), bitmap.getHeight (bitmap);           if (bitmap !

    61520

    算法篇之BitMap原理与改造,利与弊的取舍

    今天分享下,我为适应业务需求对BIMAP算法的改造思路。 举例:还是以25这个数字为例,将25写入BitMap中。 假设byte数组的大小为10(不够扩容,跟List一样道理)。 BITMAP存在的缺点 看起来BITMAP确实很优秀,存储1~80000的数字,如果以int数组来存储,需要80000*4(int=4byte)=160000byte的内存空间,而使用BitMap只需要 改造后的BITMAP 接下来介绍,我为适应业务而改造的BITMAP。就是为了解决无法预估最小值的情况。 先说下原理。 为的是实现以中心分散的集中存储方式,更高效的节省BitMap的内存使用。借用负无穷到0,0到正无穷的思路。

    46740

    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倍。

    57620

    dotnet bitmap

    bitmap using (MemoryStream ms = new MemoryStream(image)) //容易出现异常 { bmImage = new Bitmap(Image.FromStream

    17920

    Bitmap介绍

    1.bitmap占多少内存 getByteCount()方法是在API12加入的,代表存储Bitmap的色素需要的最少内存。 来解码图片,如果被复用的Bitmap的内存比待分配内存的Bitmap大,那么getByteCount()表示新解码图片占用内存的大小(并非实际内存大小,实际大小是复用的那个Bitmap的大小),getAllocationByteCount ()表示被复用Bitmap真实占用的内存大小(getByteCount永远小于等于getAllocationByteCount) 2.如何计算Bitmap占用的内存 通常情况下认为 bitmap占用的内存 可是bitmap.getWidth()返回的值会根据dpi的不同而有所调整) 3.Bitmap如何压缩 答案是inSampleSize(具体实现就不贴出来了) 4.Bitmap如何复用 1.使用LruCache = android.graphics.Bitmap@d96dbc2 bitmapReuse = android.graphics.Bitmap@d96dbc2 bitmap:AllocationByteCount

    55020

    扫码关注腾讯云开发者

    领取腾讯云代金券