一、原理

BitMap从字面的意思，很多人认为是位图，其实准确的来说，翻译成基于位的映射。

在所有具有性能优化的数据结构中，大家使用最多的就是hash表，是的，在具有定位查找上具有O(1)的常量时间，多么的简洁优美。但是数据量大了，内存就不够了。

当然也可以使用类似外排序来解决问题的，由于要走IO所以时间上又不行。

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

bitmap应用

       1）可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。
       2）去重数据而达到压缩数据

还可以用于爬虫系统中url去重、解决全组合问题。

BitMap应用：排序示例

假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0(如下图：)

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending。不过计算机一般是小端存储的，如intel。小端的话就是将倒数第5位置1）,因为是从零开始的，所以要把第五位置为一（如下图）：

然后再处理第二个元素7，将第八位置为1，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：

然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。

BitMap算法流程
假设需要排序或者查找的最大数MAX=10000000（lz:这里MAX应该是最大的数即bitmap的大小，而不是int数据的总数！），那么我们需要申请内存空间的大小为int a[1 + MAX/32]。

其中：a[0]在内存中占32为可以对应十进制数0-31，依次类推：
bitmap表为：
a[0]--------->0-31
a[1]--------->32-63
a[2]--------->64-95
a[3]--------->96-127
..........

我们要把一个整数N映射到Bit-Map中去，首先要确定把这个N Mapping到哪一个数组元素中去，即确定映射元素的index。我们用int类型的数组作为map的元素，这样我们就知道了一个元素能够表示的数字个数(这里是32)。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。

注：上述bitmap是int类型，int为8字节即32位，所以int a[1 + MAX/32]。

二、代码实现
 

package main

import (
	"fmt"
)

type BitMap []byte

const byteSize = 8 //定义的bitmap为byte的数组，byte为8bit

func NewBitMap(n uint) BitMap {
	return make([]byte, n/byteSize+1)
}
func (bt BitMap) set(n uint) {
	if n/byteSize > uint(len(bt)) {
		fmt.Println("大小超出bitmap范围")
		return
	}
	byteIndex := n / byteSize   //第x个字节（0,1,2...）
	offsetIndex := n % byteSize //偏移量(0<偏移量<byteSize)
	//bt[byteIndex] = bt[byteIndex] | 1<<offsetIndex //异或1（置位）
	//第x个字节偏移量为offsetIndex的位 置位1
	bt[byteIndex] |= 1 << offsetIndex //异或1（置位）
}
func (bt BitMap) del(n uint) {
	if n/byteSize > uint(len(bt)) {
		fmt.Println("大小超出bitmap范围")
		return
	}
	byteIndex := n / byteSize
	offsetIndex := n % byteSize
	bt[byteIndex] &= 0 << offsetIndex //清零
}
func (bt BitMap) isExist(n uint) bool {
	if n/byteSize > uint(len(bt)) {
		fmt.Println("大小超出bitmap范围")
		return false
	}
	byteIndex := n / byteSize
	offsetIndex := n % byteSize
	//fmt.Println(bt[byteIndex] & (1 << offsetIndex))
	return bt[byteIndex]&(1<<offsetIndex) != 0 //TODO：注意：条件是 ！=0，有可能是：16,32等
}
func main() {
	//a1 := byte('a')
	//fmt.Println(a1)
	bitMap := NewBitMap(20)
	bitMap.set(20)
	bitMap.set(1)
	bitMap.set(2)
	bitMap.set(3)
	bitMap.set(4)
	bitMap.set(5)
	fmt.Println("20:", bitMap.isExist(20))
	fmt.Println("5:", bitMap.isExist(5))
	bitMap.del(20)
	fmt.Println("20:", bitMap.isExist(20))
	fmt.Println("5:", bitMap.isExist(5))
	fmt.Println("1:", bitMap.isExist(1))
	fmt.Println("3:", bitMap.isExist(3))
	fmt.Println("6:", bitMap.isExist(6))
}

运行效果：