bitmap算法详解（点阵图的规律公式）

本文目录

• 点阵图的规律公式
• Android Bitmap理解
• BitMap和BitSet
• BitMap及其在ClickHouse中的应用
• 利用Bitmap类设计算法，在o(n)时间内剔除n个ASCII字符中的重复字符，各字符仅保留一份
• 如何高效使用和管理Bitmap

点阵图的规律公式

点阵图的规律公式如下：

1.数线段的一般公式是：（n-1）+···+2+1（n为线段的总端点数）.

2.在数角、三角形等图形的个数时，有时可以与数线段的条数联系起来思考。

3.数长方形的个数可以用公式“长边上的线段条数×宽边上的线段条数=长方形的个数”.

4.数正方形的个数可以用公式“n×n+(n-1)×(n-1)+···+2×2+1×1(n为正方形一边上的小格数)”

点阵图是由n多的像素组成的。它的概念主要是相对于区别矢量图而言的。点阵图和矢量图是现代计算机平面图形的两大概念。一般来说点阵图和位图是一个概念。

位图，也叫做点阵图，栅格图像，像素图，简单的说，就是最小单位由像素构成的图，缩放会失真。构成位图的最小单位是像素，位图就是由像素阵列的排列来实现其显示效果的，每个像素有自己的颜色信息，在对位图图像进行操作的时候，可操作的对象是每个像素，我们可以改变图像的色相、饱和度、明度，从而改变图像的显示效果。

举个例子来说，位图图像就好比在巨大的沙盘上画好的画，当你从远处看的时候，画面细腻多彩，但是当你靠的非常近的时候，你就能看到组成画面的每粒沙子以及每个沙粒单纯的不可变化颜色。

矢量图，也叫做向量图，简单的说，就是缩放不失真的图像格式。矢量图是通过多个对象的组合生成的，对其中的每一个对象的纪录方式，都是以数学函数来实现的，也就是说，矢量图实际上并不是象位图那样记录画面上每一点的信息

而是纪录了元素形状及颜色的算法，当你打开一幅矢量图的时候，软件对图形相对应的函数进行运算，将运算结果显示给你看。无论显示画面是大还是小，画面上的对象对应的算法是不变的，所以，即使对画面进行倍数相当大的缩放

其显示效果仍然相同。举例来说，矢量图就好比画在质量非常好的橡胶膜上的图，不管对橡胶膜怎样的常宽等比成倍拉伸，画面依然清晰，不管你离得多么近去看，也不会看到图形的最小单位。

Android Bitmap理解

参考：
Android Bitmap 详解：关于 Bitamp 你所要知道的一切

Android Bitmap（位图）详解

图片是由大量且有限个数的像素点组成。把一张图片通过bitmap的方式创建到内存中，实际上就是在内存中创建了一个叫做Bitmap的对象，然后把 图片所有像素 解码后的数据存放在Bitmap对象里面，Bitmap就拥有了图片的宽高，透明度，颜色值等数据。所以Bitmap的创建是通过BitmapFactory.decodeXxx()。

Config是Bitmap类中的枚举类。像素由ARGB四个颜色通道组成。Config描述位图中像素的存储方式。 这里的存储方式，无非就是对颜色通道和用多大的容器（bit）来存储的排列组合。所以config会影响图片透明度，占用内存大小，保存成文件的大小，图片质量。
Config的字母表示该配置存储的像素的颜色通道，数字表示对应通道的数据用多少位来存储。

ALPHA_8：表示只存储alpha通道，使用8bit（1字节）的内存（容器）来存储一个像素。
RGB_565：表示存储RGB三个通道，分别使用5bit，6bit，5bit的内存（容器）来存储一个像素。
ARGB_4444：表示存储ARGB四个通道，每个通道都是以4bit的内存（容器）来存储一个像素。
ARGB_8888：表示存储ARGB四个通道，每个通道都是以8bit的内存（容器）来存储一个像素。

所以，ARGB_8888配置占用内存最大，图片质量最高。
图片压缩的一个思路就是降低图片的配置。

总内存 = 宽的像素数 × 高的像素数 × 每个像素点占用的大小
注：
1 byte = 8 bit
1 KB = 1024 byte

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位表示了整数数组。那么java中int类型占用了4个字节，也就是32位，那么就可以最多表示32个数字。超过32位数字呢？那就使用两个以上int去表示。

假设我们要存储的数字最大值位N，则申请int temp的数组空间，其中：
temp可表示 0~31
temp可表示 32-63
.....以此类推
给定任一整数M，M数字所在数组中的下标位置就应该是M/32，M数字所在的位就是M%32

总共两步
1.找到整数所在数组temp的下标
int index = M/32
2.将temp 的第M%32位置1

temp | (1《《(M%32))

根据bitMap的原理可知，想要清除掉一个数字，那就是将对应的位置0
总共两步
1.找到整数所在数组temp的下标
int index = M/32
2.将temp 的第M%32位置0
temp &（~ (1《《(M%32))）

根据每一位代表一个数字，1表示存在，0表示不存在，那么只需要判断整数对应位是否位1即可
总共两步
1.找到整数所在数组temp的下标
int index = M/32
2.将temp 的第M%32位置0
temp &(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及其在ClickHouse中的应用

问题要从面试或者大数据场景下最常见的一个算法说起，问题是这样的，假如有几十亿个unsigned int类型的数据，要求去重或者计算总共有多少不重复的数据？最简单的办法就是直接利用一个HashMap，进行去重。但是这里面有个内存使用量的问题，几十亿个元素，即使不考虑HashMap本身实现所用到的数据结果，单单key本身，假如每个unsigned int占用4个字节，简单算一下的话，这里都需要几十GB的内存占用，因此，这里就引出了BItMap。
BItMap的思想非常简单，就是用一个bit表示一个二元的状态，比如有或者没有，存在或者不存在，用bit本身的位置信息，对应不同的数据。比如针对上面的问题，我们可以开辟一个2^32 bit的内存空间，每一个bit存储一个unsigned int类型的数据，有就是1，没有就是0，总共需要存储unsigned int类型的最大范围个数据，也就是2^32 个数据，这个2^32其实就是所谓的基数。如下图所示：

假如存在数字8，那就把对应的第8位的值赋为1。上图插入的数据为1、3、7、8。接着依次把所有的数据遍历然后更新这个BitMap。这样我们就可以得到最终结果。

假如上面的问题变成了对几十亿个URL做判断，那应该怎么去做呢？URL没有办法和BitMap的位置关系对应上，所以，我们需要加一层哈希，把每个URL经过哈希运算得到一个整数，然后对应上BitMap。如下图所示：

但是有哈希，肯定会存在碰撞，如果BitMap基数（也就是长度）比较小，那碰撞的概率就大，如果基数比较大，那占用的空间又会比较多。Bloom Filter的思想就是引入多个哈希函数来解决冲突的问题。也就是说对每个URL，经过多个哈希函数的运算，得到多个值，每个数值对应的BitMap的对应的位置都赋值为1。这个两个URL经过多个哈希函数结果还是一样的概率就大大降低。

但是由于依然存在冲突的可能性（其实冲突就是来源于我们BitMap的长度小于了数据量的基数，这也就是牺牲了准确性换来了空间使用的减少），所以Bloom Filter 存在假阳性的概率，不适用于任何要求 100% 准确率的场景，也就是说Bloom Filter 只能用来判无，不能用来判有。比如一个URL经过多次哈希运算之后，发现对应的BitMap的位置都已经是1了，那也不能说明，这个URL之前存在过了，也有可能是哈希冲突的结果。但是一个URL经过多次哈希运算之后，发现对应的BitMap的位置不是都是1，那当前URL之前一定是没有存在过的。

可以看到，Bloom Filter 引入多次哈希，在查询效率和插入效率不变的情况下，用较少空间的BitMap解决大数据量的判断问题。

大部分情况下仅仅做有无的判断是不能满足使用需求的，我们还是需要真正意义上的BitMap（可以方便的用来做交并等计算），但是最好可以在基数比较大的时候，依然可以占用相对比较小的空间。这就是RoaringBitMap所要实现的。

简单来说RoaringBitMap是BitMap的一种带索引的复杂BitMap数据结构。以32位的RoaringBitMap为例，首先划分2^16 个空间（Container），每个Container内部都是一个大小为2^16 bit的BitMap，总的内存使用量还是2^32 = 512Mb。这样的话和普通的BitMap是没有区别的，而RoaringBitMap的创新之处在于每个Container内的BitMap是在没有使用到的情况下是可以不分配内存空间的。这样可以大大减小内存的使用量。

（这个图片是Roaring Bitmaps: Implementation of an Optimized Software Library 论文原图）

要将一个4个字节的数据插入RoaringBitMap，首先要用数据的高16位，找到对应的Container，然后用数据的低16在Container中插入。
在每个Container内部，RoaringBitMap不是简单的用BitMap来进行数据的存储，而是把Container的类型划分为几种，不同的Container用来存储不同情况的数据。

当2个字节（4个字节的原数据，低16位用来插入具体的Container中）的数据，总的个数小于4096个的时候，当前Container使用 array Container。为什么是4096个呢？4096*2B=8Kb，而一个Container如果是bitmap的结构的话，最多也就是2^16bit=8Kb的空间。所以这里当数据个数小于4096使用array Container会更节省空间。当然这里名字为array Container，实际上是链表结构，不需要最开始就初始化4096个short int的数组。

当array Container存储的数到4096个的时候（也就是使用内存到8Kb的时候），array Container会转换为bitmap container，bitmap container就是一个2^16 bit普通的bitmap，可以存储2^16 = 65536个数据。这个8Kb还有一个好处，是可以放到L1 Cache中，加快计算。

这个严格的说，只是一种数据压缩存储方法的实现。其压缩原理是对于连续的数字只记录初始数字以及连续的长度，比如有一串数字 12,13,14,15,16 那么经过压缩后便只剩下12,5。从压缩原理我们也可以看出，这种算法对于数据的紧凑程度非常敏感，连续程度越高压缩率也越高。当然也可以实现其他的压缩方法。

RoaringBitMap其核心就在于加了一层索引，利用复杂的数据结构换取了空间上的效率。需要注意的是这里并没有增加计算的复杂度，其出色的数据结构让其在做交并计算的时候性能也毫不逊色。

ClickHouse中有bloom_filter类型的Skipping indexs，可以方便的用来过滤数据。

ClickHouse实现了大量的BitMap的函数，用来操作BitMap。ClickHouse中的BitMap在32位的时候用的是Set实现的，大于32位的时候也是使用RoaringBitMap实现的。我们这里不看具体的函数，我们来看一个典型的使用场景。

最常见的一个场景是根据标签来进行用户的圈选。常见的解决办法是有一张用户标签表，比如

要查询标签tag1=’xx’和tag2=’xx’的用户需要执行SQL：

但是由于不可能对每个tag列构建一级索引，所以这条SQL执行的效率并不高。可选的一种方式是先构建关于标签的BitMap数据结果，然后进行查询：

（1） 创建tag的bitmap表：

（2）写入数据

（3）查询

如果有多张tag表，进行交并计算（要比普通的用户表进行JOIN或者IN计算要高效很多）：

利用Bitmap类设计算法，在o(n)时间内剔除n个ASCII字符中的重复字符，各字符仅保留一份

【答案】：将非重复的ASCII字符视作一个集合，并将其组织为一个Bitmap结构——ASCII编码为k的字符，对应于其中第k个比特位。
初始时，该集合为空，Bitmap结构中的所有比特位均处于0状态。以下，只需在o(n)时间内遍历所有的输入字符，并对ASCII编码为k的字符，通过set(k)接口将其加入集合。
请注意，这里使用的Bitmap结构只需128个比特位。因此，最后只需再花费o(128)=o(1)时间遍历一趟所有的比特位，并输出所有通过test()测试的比特位，即可完成字符集的去重。

如何高效使用和管理Bitmap

一、图片加载流程 

        首先，我们谈谈加载图片的流程，项目中的该模块处理流程如下： 

1.在UI主线程中，从内存缓存中获取图片，找到后返回。找不到进入下一步； 

2.在工作线程中，从磁盘缓存中获取图片，找到即返回并更新内存缓存。找不到进入下一步； 

3.在工作线程中，从网络中获取图片，找到即返回并同时更新内存缓存和磁盘缓存。找不到显示默认以提示。 

二、内存缓存类（PanoMemCache）

        这里使用Android提供的LruCache类，该类保存一个强引用来限制内容数量，每当Item被访问的时候，此Item就会移动到队列的头部。当cache已满的时候加入新的item时，在队列尾部的item会被回收。

view plain copy print ?

public class PanoMemoryCache {  

    // LinkedHashMap初始容量  

    private static final int INITIAL_CAPACITY = 16;  

    // LinkedHashMap加载因子  

    private static final int LOAD_FACTOR = 0.75f;  

    // LinkedHashMap排序模式  

    private static final boolean ACCESS_ORDER = true;  

    // 软引用缓存  

    private static LinkedHashMap《String, SoftReference《Bitmap》》 mSoftCache;  

    // 硬引用缓存  

    private static LruCache《String, Bitmap》 mLruCache;  

    public PanoMemoryCache() {  

    // 获取单个进程可用内存的最大值  

    // 方式一：使用ActivityManager服务（计量单位为M）  

        /*int memClass = ((ActivityManager) context.getSystemService(Context.ACTIVITY_SERVICE)).getMemoryClass();*/  

    // 方式二：使用Runtime类（计量单位为Byte）  

        final int memClass = (int) Runtime.getRuntime().maxMemory();  

        // 设置为可用内存的1/4（按Byte计算）  

        final int cacheSize = memClass / 4;  

        mLruCache = new LruCache《String, Bitmap》(cacheSize) {  

            @Override  

            protected int sizeOf(String key, Bitmap value) {  

                if(value != null) {  

                    // 计算存储bitmap所占用的字节数  

                    return value.getRowBytes() * value.getHeight();  

                } else {  

                    return 0;  

                }  

            }  

            @Override  

            protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap newValue) {  

                if(oldValue != null) {  

                    // 当硬引用缓存容量已满时，会使用LRU算法将最近没有被使用的图片转入软引用缓存  

                    mSoftCache.put(key, new SoftReference《Bitmap》(oldValue));  

                }  

            }  

        };  

    /* 

    * 第一个参数：初始容量（默认16） 

    * 第二个参数：加载因子（默认0.75） 

    * 第三个参数：排序模式（true：按访问次数排序；false：按插入顺序排序） 

    */  

        mSoftCache = new LinkedHashMap《String, SoftReference《Bitmap》》(INITIAL_CAPACITY, LOAD_FACTOR, ACCESS_ORDER) {  

            private static final long serialVersionUID = 7237325113220820312L;  

            @Override  

            protected boolean removeEldestEntry(Entry《String, SoftReference《Bitmap》》 eldest) {  

                if(size() 》 SOFT_CACHE_SIZE) {  

                    return true;  

                }  

                return false;  

            }  

        };  

    }  

    /** 

     * 从缓存中获取Bitmap 

     * @param url 

     * @return bitmap 

     */  

    public Bitmap getBitmapFromMem(String url) {  

        Bitmap bitmap = null;  

        // 先从硬引用缓存中获取  

        synchronized (mLruCache) {  

            bitmap = mLruCache.get(url);  

            if(bitmap != null) {  

                // 找到该Bitmap之后，将其移到LinkedHashMap的最前面，保证它在LRU算法中将被最后删除。  

                mLruCache.remove(url);  

                mLruCache.put(url, bitmap);  

                return bitmap;  

            }  

        }  

        // 再从软引用缓存中获取  

        synchronized (mSoftCache) {  

            SoftReference《Bitmap》 bitmapReference = mSoftCache.get(url);  

            if(bitmapReference != null) {  

                bitmap = bitmapReference.get();  

                if(bitmap != null) {  

                    // 找到该Bitmap之后，将它移到硬引用缓存。并从软引用缓存中删除。  

                    mLruCache.put(url, bitmap);  

                    mSoftCache.remove(url);  

                    return bitmap;  

                } else {  

                    mSoftCache.remove(url);  

                }  

            }  

        }  

        return null;  

    }  

    /** 

     * 添加Bitmap到内存缓存 

     * @param url 

     * @param bitmap 

     */  

    public void addBitmapToCache(String url, Bitmap bitmap) {  

        if(bitmap != null) {  

            synchronized (mLruCache) {  

              mLruCache.put(url, bitmap);    

            }  

        }  

    }  

    /** 

     * 清理软引用缓存 

     */  

    public void clearCache() {  

        mSoftCache.clear();  

    mSoftCache = null;  

    }  

}  

        补充一点，由于4.0平台以后对SoftReference类引用的对象调整了回收策略，所以该类中的软引用缓存实际上没什么效果，可以去掉。2.3以前平台建议保留。 

三、磁盘缓存类（PanoDiskCache） 

五、使用decodeByteArray()还是decodeStream()？ 

        讲到这里，有童鞋可能会问我为什么使用BitmapFactory.decodeByteArray(data, 0, data.length, opts)来创建Bitmap，而非使用BitmapFactory.decodeStream(is, null, opts)。你这样做不是要多写一个静态方法readInputStream()吗？ 

        没错，decodeStream()确实是该使用情景下的首选方法，但是在有些情形下，它会导致图片资源不能即时获取，或者说图片被它偷偷地缓存起来，交 还给我们的时间有点长。但是延迟性是致命的，我们等不起。所以在这里选用decodeByteArray()获取，它直接从字节数组中获取，贴近于底层 IO、脱离平台限制、使用起来风险更小。 

六、引入缓存机制后获取图片的方法 

view plain copy print ?

/** 

     * 加载Bitmap 

     * @param url 

     * @return  

     */  

    private Bitmap loadBitmap(String url) {  

        // 从内存缓存中获取，推荐在主UI线程中进行  

        Bitmap bitmap = memCache.getBitmapFromMem(url);  

        if(bitmap == null) {  

            // 从文件缓存中获取，推荐在工作线程中进行  

            bitmap = diskCache.getBitmapFromDisk(url);  

            if(bitmap == null) {  

                // 从网络上获取，不用推荐了吧，地球人都知道~_~  

                bitmap = PanoUtils.downloadBitmap(this, url);  

                if(bitmap != null) {  

                    diskCache.addBitmapToCache(bitmap, url);  

                    memCache.addBitmapToCache(url, bitmap);  

                }  

            } else {  

                memCache.addBitmapToCache(url, bitmap);  

            }  

        }  

        return bitmap;  

    }  

七、工作线程池化 

        有关多线程的切换问题以及在UI线程中执行loadBitmap()方法无效的问题，请参见另一篇博文： 使用严苛模式打破Android4.0以上平台应用中UI主线程的“独断专行”。 

有关工作线程的处理方式，这里推荐使用定制线程池的方式，核心代码如下： 

view plain copy print ?

// 线程池初始容量  

private static final int POOL_SIZE = 4;  

private ExecutorService executorService;  

@Override  

public void onCreate(Bundle savedInstanceState) {  

    super.onCreate(savedInstanceState);  

    // 获取当前使用设备的CPU个数  

    int cpuNums = Runtime.getRuntime().availableProcessors();  

    // 预开启线程池数目  

    executorService = Executors.newFixedThreadPool(cpuNums * POOL_SIZE);  

    ...  

    executorService.submit(new Runnable() {  

        // 此处执行一些耗时工作，不要涉及UI工作。如果遇到，直接转交UI主线程  

        pano.setImage(loadBitmap(url));  

    });  

    ...  

}  

        我们知道，线程构造也是比较耗资源的。一定要对其进行有效的管理和维护。千万不要随意而行，一张图片的工作线程不搭理也许没什么，当使用场景变为 ListView和GridView时，线程池化工作就显得尤为重要了。Android不是提供了AsyncTask吗？为什么不用它？其实 AsyncTask底层也是靠线程池支持的，它默认分配的线程数是128，是远大于我们定制的executorService。