0 引入

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

本文使用python实现bitmap算法。
由于算法储存数据的粒度到了位，因此代码中使用了很多位运算，先回顾一下python中的位运算操作。

# 或运算
>>> bin(10), bin(8)
('0b1010', '0b1000')
>>> bin(10 | 8)
'0b1010'# 与预算
>>> bin(10), bin(8)
('0b1010', '0b1000')
>>> bin(10 & 8)
'0b1000'# 位移运算
>>> bin(10)
'0b1010'
>>> bin(10 << 3)
'0b1010000'

1 设计思想

代码中使用n个4字节的整数来储存数据，每个整数有32位。

假定我们要储存的客户的ID，元素个数n根据需要储存的最大ID计算得到。

然后循环的把ID存储bitmap中，储存每个ID时，先计算ID对应的元素下标和在元素中的存在第几位。
例如我们要储存的ID是30，通过后面的get_element_index和get_bit_index函数的计算分别得到元素下标是0，储存位数是30。

然后把第0个元素的第30位（从0开始）置为1即可。

2 代码

class BitMap(object):def __init__(self, max_value):"""使用多个整型元素来储存数据，每个元素4个字节（32位）"""self._size = int((max_value + 31 - 1) / 31)  # 计算需要的字节数，字节数也是数组的大小self.array = [0 for i in range(self._size)]  # 数组的元素都初始化为0，每个元素有32位@staticmethoddef get_element_index(num):"""获取该数即将储存的字节在数组中下标"""return num // 31@staticmethoddef get_bit_index(num):"""获取该数在元素中的位下标"""return num % 31def set(self, num):"""将该数存在对应的元素的对应位置"""element_index = self.get_element_index(num)bit_index = self.get_bit_index(num)self.array[element_index] = self.array[element_index] | (1 << bit_index)def find(self, num):"""查找该数是否存在与bitmap中"""element_index = self.get_element_index(num)bit_index = self.get_bit_index(num)if self.array[element_index] & (1 << bit_index):return Truereturn Falsedef count_one(self):"""统计bitmap中数据的个数"""count = 0for n in self.array:while n > 0:n = n & (n - 1)count += 1return countdef main():array_list = [30, 32, 5, 45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46, 1, 5]# 根据最大数的值创建BitMap对象bitmap = BitMap(max_value=max(array_list))# 将数据逐个存入bitmapfor num in array_list:bitmap.set(num)# 查询数据是否存在于bitmap中results = []for i in range(max(array_list) + 1):if bitmap.find(i):results.append(i)print(results)if __name__ == '__main__':main()