海量数据查找之Bitmap算法

什么是BitMap算法

  所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value,而 key 即是这个元素。由于采用bit为单位来存储数据,因此在可以大大的节省存储空间。

算法思想

  在32位机器上,一个整形,比如 int a; 在内存中占32bit,可以用对应的32个bit位来表示十进制的0-31个数,bitmap算法利用这种思想处理大量数据的排序与查询。

优点:

  • 效率高,无需进行比较和移位
  • 占用内存少,由于一个int型数字占用32bit,采用bitmap存储时,假如是连续的数字,最多可节省32倍的空间。比如N=10000000;只需占用内存为N/8 = 312500Bytes = 305K,如果采用int数组存储,则需要38M多

缺点:

  • 无法对存在重复的数据进行排序和查找
  • 如果数字是非连续的,甚至数字间隔较大,就不能很好的节省空间

示例

申请一个int型的内存空间4Byte,32bit。输入 4, 2, 1, 3时:

输入4:

输入2:

输入1:

输入3:

思想比较简单,关键是十进制和二进制bit位需要一个 map 映射表,把10进制映射到bit位上。当查询是否存在是只需要校验对应的位上是0还是1即可

对比Bloom-Filter算法你会发现,如果数字间隔较大,且容忍一定的误判,就更适合使用Bloom-Filter算法,因为BitMap中的数组长度是由最大数字决定的,如果最大数字较大,且不连续,就会很浪费空间

JouyPub wechat
欢迎订阅「K叔区块链」 - 专注于区块链技术学习