bitmap

在网上有一道面试题大概意思就是: 存在十亿个数字,现在需要知道哪些数字没有出现在里面. 这个问题你可能觉得一个for循环就能解决,但是实际上你可能忽略了一个问题,那就是10亿个数字需要占据的内存空间.例如在java中要存下10亿个数字需要多大空间呢?假设使用int存储,一个int占32个位也就是4个字节.存放10亿个数字则需要: 10亿*4/1024/1024/1024 = 4G左右 .面对上面的问题我们肯定不能使用这种方式存储.而使用我们的Bitmap就能很好的解决上面的问题.

Bitmapi简单的说就是使用bit(位)来存储状态,适合用来存储大规模的数据,但是状态又不是很多的情况.举例来说,如果我现在有 1,3,4,2,7 这五个数字,如果我们使用5个int来存储则需要20个字节的空间.但是我现在使用1字节就能存储上面的五个数字.如下图所示,1个字节可以用8位表示,1位有0和1两种值分别用来表示该位上是否有值,而位的索引用来表示数字(图中以从左到右的顺序计算).




而它的缺点同样也比较明显.它的一个位只能存储一个数据,对于重复的数据无法记录.如果数据分布很稀疏,会造成空间的浪费.例如,如果现在只有{1,3,1000000000}这个三个数据,它有很多空间会被浪费掉.

BitMap在java中提供了BitSet的实现,同时在我们平常使用的Redis中也有实现.它很适合用来做大量的用户统计.例如统计登录人数,签到,在线等等.这些需求都可以通过redis的bit相关指令很简单的就能实现.
例如,统计网站的在线人数:

上面的方式不仅简单,而且就算用户数量很大也能又快又好的完成.

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，可供开发者们随意使用。

Bitmap.getAllocationByteCount() 方法获取 Bitmap 占用的字节大小 默认情况下 BitmapFactory 使用 Bitmap.Config.ARGB_8888 的存储方式来加载图片内容，而在这种存储模式下，每一个像素需要占用 4 个字节。 实际上 BitmapFactory 在解析图片的过程中，会根据当前设备屏幕密度和图片所在的 drawable 目录来做一个对比，根据这个对比值进行缩放操作。 在 Android 中，各个 drawable 目录对应的屏幕密度分别为下： PS: Options.inMutable 置为 true，这里如果不置为 true 的话，BitmapFactory 将不会重复利用 Bitmap 内存 复用 inBitmap 之前，需要调用 canUseForInBitmap 方法来判断 reuseBitmap 是否可以被复用。这是因为 Bitmap 的复用有一定的限制： 在不压缩图片的前提下，不建议一次性将整张图加载到内存，而是采用分片加载的方式来显示图片部分内容，然后根据手势操作，放大缩小或者移动图片显示区域。 BitmapRegionDecoder 将图片加载到内存中，图片可以以绝对路径、文件描述符、输入流的方式传递给 BitmapRegionDecoder 当需要在界面上同时展示一大堆图片的时候，比如 ListView、RecyclerView 等，由于用户不断地上下滑动，某个 Bitmap 可能会被短时间内加载并销毁多次。这种情况下通过使用适当的缓存，可以有效地减缓 GC 频率保证图片加载效率，提高界面的响应速度和流畅性。 LruCache（Least Recently Used）算法的核心思想就是 最近最少使用算法 。 内部维护了一个 LinkHashMap 的链表，通过put数据的时候判断是否内存已经满了，如果满了，则将最近最少使用的数据给剔除掉，从而达到内存不会爆满的状态。