1.BitMap原理与实现
2.Bitmap使用详解

BitMap原理与实现

        比较经典的问题是： 在只能够使用2G的内存中，如何完成以下操作：

        ①：对亿个不重复的整数进行排序。

        ②：找出亿个数字中重复的数字。

        无论是排序还是找重复的数字都需要将这亿个数字加入到内存中在去进行操作，很明显，题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的

        * 4/（* * ） = 3.G

        那么这时候就需要用到 BitMap结构了

        bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,汉字boost python源码剖析而map的key值正是这个数字本身。

        相比于一般的数据结构需要用4个byte去存储数值本身，相当于是节省了 4*8：1 = 倍的内存空间

        bitMap不一定要用bit数组,可以使用 int,long等等的基本数据类型实现，因为其实质都是在bit位上存数据，用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少

            例如：java中的BitSet使用Long数组

        BitMap的实现当然少不了位运算，先来明确几个常见位运算，这是实现BitMap的基础：

        set(bitIndex): 添加操作

            1 .确定该数处于数组中的哪个元素的位上

             int wordIndex = bitIndex >> 5;

        因为我用的是int[]实现，所以这里右移 5 位（2^5 = ）

            2 .确定相对于该元素中的位置偏移

             int bitPosition = bitIndex & ((1 << 5) - 1);

        这里相当于是 bitIndex % （1<<5）的取模运算，因为当取模运算的除数是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 << == 1<<     

             1L << ==1L<<

        即对于int和long型数据，直接左移其位数相当于是附带了对其的取模操作

        总结：使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。

        Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构

        当一个元素加入布隆过滤器中的时候，会进行哪些操作：

        当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行哪些操作：

        然后，一定会出现这样一种情况：不同的字符串可能哈希出来的位置相同（可以适当增加位数组大小或者调整我们的哈希函数来降低概率）,因此：布隆过滤器可能会存在误判的情况

        总结来说就是： 布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

        Bloom Filter的应用: 常用于解决缓存穿透等场景。

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的内存优化