「bitmap去重java」bitmap 去重
今天给各位分享bitmap去重java的知识，其中也会对bitmap 去重进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
BitMap和BitSet
Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，可以很大力度的节省空间，常用于对大量整数做去重和查询操作。
1byte=8bit
1kb=1024byte
1mb=1024kb
1gb=1024mb
java中 int类型占用4个字节=4*8=32bit
从上述结果来看，按位存储比按字节存储数字节约了（7.45/0.233-1约等于31倍空间），而且按字节存储根据内存4G的要求无法一次性在内存中进行处理。
众所周知，每一位的取值无非就是0和1，给每一位编号，那么用0表示数字存在，1表示数字不存在。
假如现在有一个字节也就是8位的空间，那么按照BitMap，可以表示8个数字，
按照上图所示，该字节的8位表示了整数数组[6,5,2,0]。那么java中int类型占用了4个字节，也就是32位，那么就可以最多表示32个数字。超过32位数字呢？那就使用两个以上int去表示。
假设我们要存储的数字最大值位N，则申请int temp[1+N/32]的数组空间，其中：
temp[0]可表示 0~31
temp[1]可表示 32-63
.....以此类推
给定任一整数M，M数字所在数组中的下标位置就应该是M/32，M数字所在的位就是M%32
总共两步
1.找到整数所在数组temp的下标
int index = M/32
2.将temp[index] 的第M%32位置1
temp[index]=temp[index] | (1(M%32))
根据bitMap的原理可知，想要清除掉一个数字，那就是将对应的位置0
总共两步
1.找到整数所在数组temp的下标
int index = M/32
2.将temp[index] 的第M%32位置0
temp[index]=temp[index] （~ (1(M%32))）
根据每一位代表一个数字，1表示存在，0表示不存在，那么只需要判断整数对应位是否位1即可
总共两步
1.找到整数所在数组temp的下标
int index = M/32
2.将temp[index] 的第M%32位置0
temp[index] (1(M%32) ！= 0？"存在":"不存在"
运行结果
BitSet就是实现了Bit-Map算法。BitSet位于java.util包下，从JDK1.0开始就已经有了。该类实现了一个按需增长的位向量。位集的每一个组件都有一个boolean类型的值。BitSet的每一位代表着一个非负整数。可以检查、设置、清除单个位。一个BitSet可以通过逻辑与、逻辑或、逻辑异或去修改另一个BitSet。默认情况下，所有位的标识都是false。
设值
清除
检查
BitSet有三种构造方法，我们直接来看无参构造器
可以看到BitSet是使用long数组存储。那么long类型占用8个字节，即64位，一个long类型可表示64个数字。默认设置BitSet可表示最大的位数为64位。与上述自己实现的基本类似。
再来看set方法
get方法
clear方法
可以看到JDK中的BitSet实现原理与第三节中一样，采用Bit-Map思想，BitSet封装较多的API，可供开发者们随意使用。
java map去重
map的key是不会重的，所以我就认为你是需要将value去重。
可以遍历map，将value存入一个set中，然后遍历时判断是否已经存在于set。
Bitmap使用详解
用到的图片不仅仅包括.png、.gif、.9.png、.jpg和各种Drawable系对象，还包括位图Bitmap
图片的处理也经常是影响着一个程序的高效性和健壮性。
为什么不直接用Bitmap传输？
位图文件虽好，但是非压缩格式，占用较大存储空间。
Bitmap主要方法有：获取图像宽高、释放，判断是否已释放和是否可修改，压缩、创建制定位图等功能
用于从不同的数据源(如文件、输入流、资源文件、字节数组、文件描述符等)解析、创建Bitmap对象
允许我们定义图片以何种方式如何读到内存。
推荐阅读： Android - Bitmap-内存分析
注意事项：
decodeFileDescriptor比decodeFile高效
查看源码可以知道
替换成
建议采用decodeStream代替decodeResource。
因为BitmapFactory.decodeResource 加载的图片可能会经过缩放，该缩放目前是放在 java 层做的，效率比较低，而且需要消耗 java 层的内存。因此，如果大量使用该接口加载图片，容易导致OOM错误，BitmapFactory.decodeStream 不会对所加载的图片进行缩放，相比之下占用内存少，效率更高。
这两个接口各有用处，如果对性能要求较高，则应该使用 decodeStream；如果对性能要求不高，且需要 Android 自带的图片自适应缩放功能，则可以使用 decodeResource。
推荐阅读：[ BitmapFactory.decodeResource加载图片缩小的原因及解决方法
canvas和Matrix可对Bitmap进行旋转、放缩、平移、切错等操作
可以用Bitmap.onCreateBitmap、Canvas的clipRect和clipPath等等方式
推荐阅读： android自定义View学习4--图像剪切与变换
对初始化Bitmap对象过程中可能发生的OutOfMemory异常进行了捕获。如果发生了OutOfMemory异常，应用不会崩溃，而是得到了一个默认的Bitmap图。
如果不进行缓存，尽管看到的是同一张图片文件，但是使用BitmapFactory类的方法来实例化出来的Bitmap，是不同的Bitmap对象。缓存可以避免新建多个Bitmap对象，避免内存的浪费。
如果图片像素过大，使用BitmapFactory类的方法实例化Bitmap的过程中，需要大于8M的内存空间，就必定会发生OutOfMemory异常。
可以将图片缩小，以减少载入图片过程中的内存的使用，避免异常发生。
推荐阅读：
Bitmap详解与Bitmap的内存优化
40亿个QQ号码去重
文件中有40亿个QQ号码，请设计算法对QQ号码去重，相同的QQ号码仅保留一个，内存限制1G。
BitMap的原理
BitMap 的基本原理就是用一个bit 位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。
举例：在Java里面一个int类型占4个字节，假如要对于10亿个int数据进行处理呢？ 10亿*4/1024/1024/1024=4个G 左右，需要4个G的内存。
如果能够采用bit储,一个bit是8位，就可以标识8个数字，那么 512M = （512 * 1024 * 1024 * 8） 位 = 43亿 , 那么在存储空间方面可以大大节省。1M - 1024bit -1024*8个bit位
在Java里面，BitMap已经有对应实现的数据结构类java.util.BitSet，BitSet的底层使用的是long类型的数组来存储元素。
我们来看看具体存储：
对于1，3，5，7这四个数，如果存在的话，则可以这样表示：
1代表这个数存在，0代表不存在。例如表中01010101代表1，3，5，7存在，0，2，4，6不存在。那如果8，10，14也存在怎么存呢？如图，8，10，14我们可以存在第二个字节里
以此类推。
然后从小到大遍历所有正整数(4字节)，当bitmapFlag值为1时，就表明该数是存在的
BitMap原理与实现
比较经典的问题是： 在只能够使用2G的内存中，如何完成以下操作：
①：对10亿个不重复的整数进行排序。
②：找出10亿个数字中重复的数字。
无论是排序还是找重复的数字都需要将这10亿个数字加入到内存中在去进行操作，很明显，题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的
1000000000* 4/（1024* 1024* 1024） = 3.725G
那么这时候就需要用到 BitMap结构了
bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,而map的key值正是这个数字本身。
相比于一般的数据结构需要用4个byte去存储数值本身，相当于是节省了 4*8：1 = 32倍的内存空间
bitMap不一定要用bit数组,可以使用 int,long等等的基本数据类型实现，因为其实质都是在bit位上存数据，用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少
例如：java中的BitSet使用Long数组
BitMap的实现当然少不了位运算，先来明确几个常见位运算，这是实现BitMap的基础：
set(bitIndex): 添加操作
1 .确定该数处于数组中的哪个元素的位上
int wordIndex = bitIndex 5;
因为我用的是int[]实现，所以这里右移 5 位（2^5 = 32）
2 .确定相对于该元素中的位置偏移
int bitPosition = bitIndex ((1 5) - 1);
这里相当于是 bitIndex % （15）的取模运算，因为当取模运算的除数是2的次幂，所以可以使用以下的位运算来计算，提升效率（对比HashMap的容量为什么总是2的幂次方的问题，HashMap求下标时也是使用 hash(n-1)）
tips: 位运算的优先级是低于+,-等等的，所以要加上括号,防止发生不可描述的错误
3 .将该位置1
bits[wordIndex] |= 1 bitPosition;
相当于是将指定位置处的bit值置1，其他位置保持不变，也就是将以这个bitIndex为key的位置为1
tips: 这里是参考了网上的各位大佬的文章,取余 + 按位或，又对比了下BitSet的源码：
words[wordIndex] |= (1L bitIndex);
没有取余操作，直接|，这两个一样吗？答案当然是一样的
举个栗子：
1 148 == 1 20
1L 125 ==1L 61
即对于int和long型数据，直接左移其位数相当于是附带了对其的取模操作
总结 ：使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。
Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构
当一个元素加入布隆过滤器中的时候，会进行哪些操作：
当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行哪些操作：
然后，一定会出现这样一种情况： 不同的字符串可能哈希出来的位置相同 （可以适当增加位数组大小或者调整我们的哈希函数来降低概率）,因此： 布隆过滤器可能会存在误判的情况
总结来说就是： 布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在 。
Bloom Filter的应用: 常用于解决缓存穿透等场景。
海量数据去重-精确去重[Bitmap]
假如我们使用Bitmap（或称BitSet）储存，定义一个很大的bitmap数组，每个元素对应Bitmap中的1位。
初始数组都是0，每个原始在数组中的index位置标识为1.
估算示例：
（1）若有10^9 个元素，即10亿，则占用的内存为120M 。（10^9/8/1024/1024=120M）
（2）所有2^32个元素，约43亿，则占用内存为512M 。 (2^32/8/1023/1024=512M)
注： Integer.Max_value=2^32;
场景分析：
某电商平台，要分析每个商品的UV，可能涉及到不同维度组合的商品UV统计，到底需要定义多少以及多大的BitMap去存储呢？
首先，商品有热们和冷门之分，热门的UV可能比较多，冷门的可能寥寥无几。另外时间维度可能有分/时/天/周/月等等，还有渠道维度等等，用户的需求可能基于多个维度组合统计。这个给计算带来很大的挑战，是否有一种动态的内存分配方案，更好的利用内存资源呢？
答案是 : 使用RoaringBitmap 。
RoaringBitmap 跟JDK1.8 currentHashMap的思路有点像，如当hash冲突时，如果链表节点个数8个，则转化为红黑二叉树存储。如果6则自动转化为普通链表存储。
它将一个32位的Integer 分为高16位和低16位，前者用于创建桶，总计 2^16 个桶 short[]，没有则创建一个。（把它理解为index索引桶也行，后者作为value，放入该桶中。高16位相同的数据在同一个桶中values[] ;
即
将一个数值 k 划分为高 16 位(k % 2^16)和低 16 位(k mod 2^16)，取高 16 位找到对应的桶，然后在低 16 位存放在相应的 Container 中；
在这里，RoaringBitmap 也会根据一个阈值4096，
若元素数量4096则使用ArrrayContainer储存；
若元素数量4096则使用BitmapContainer储存；
ArrayContainer ：存储稀疏少量的数据。
BitmapContainer: 存储稠密的数据 （占用内存始终是8kb)
这里有个问题：上面假设存放的Integer类型，那非Integer类型如何存储？
答：需要建立一个非Integer类型到数值类型的映射关系表。
关于bitmap去重java和bitmap 去重的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。