# Bitmap

## 简介

bitmap的核心思想是利用元素本身的值来保存其位置，一般要求元素不能重复。Bitmap算法利用这种思想处理大量数据的排序、查询以及去重。

## 实例

例如我们有list `[0, 2, 3, 4, 8, 10, 13, 14, 15, 16, 17, 19, 20, 22, 23]`，那么我们只需要24个bit就可以存储这些元素，策略如下：

1. 构建一个长度为24个bit的数组
2. 对所有数字做遍历，把bit 1插入到bit数组中下标与该数字值相等的位置；例如，数字5就应该向bit数组的第5个位置中插入1，插入后结果是 `100000`
3. 重复上面的操作，直到把所有的数字都插入到bit数组中，此时数字保存完毕、并且此时数组中的数字都是有序的，操作完成。

**代码实现：**

```java
package com.wangjun.test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class Bitmap {

    public static void main(String[] args) {
        List<Integer> list = getList();
        System.out.println(list);
        int s = 0;
        for (int i : list) {
            // 把1左移i位的值等于2的i次方
            // 之后把该值与s并上等于把该值上所有的1都插入s的对应位置上
            s = s | 1 << i;
        }

        StringBuilder sb = new StringBuilder(Integer.toBinaryString(s));
        System.out.println(sb.reverse()); // 对二进制做反转操作以方便观察
    }

    /**
     * 生成随机的list
     */
    private static List<Integer> getList() {
        Set<Integer> set = new HashSet<>();
        while (set.size() < 15) {
            int i = new Random().nextInt();
            if (i < 0)
                i = -i;
            i = i % 30;
            set.add(i);
        }
        List<Integer> list = new ArrayList<>();
        list.addAll(set);
        return list;
    }
}
```

运行结果：

```
[0, 3, 5, 9, 11, 12, 13, 14, 18, 19, 21, 24, 25, 26, 28]
10010100010111100011010011101
```

第一行是原始的值，第二行是用位图保存的值。我们发现位图的第0位、第3位、第5位 … 第26位、第28位上的值都为1，对应了这些下标所对应的值的存在，可见我们已经成功的把数字保存到了位图之中。

通过仔细的观察我们发现，在上面的例子中我们用一个int类型的值就可以保存15位大小在0\~30之间的数字了，事实上一个int类型的值最多可以保存 `4 * 8 = 32` 个连续而不重复的数字，按照这样来算即使是1亿个连续而不重复的int类型数字也只需要

```
100000000 / 1024 / 1024 = 95.36M
```

即只需要不到96M的内存我们就可以存下这些数字。如果我们不使用位图来保存则需要

```
100000000 * 32 / 1024 / 1024 = 3052M
```

差不多是3个G左右的内存，可见Bitmap对内存的节省还是相当夸张的。

> 参考：
>
> <https://www.jianshu.com/p/bf9dbbc147ed>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/shu-ju-jie-gou/bitmap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.