首页 > 代码库 > 数据结构--bitmap
数据结构--bitmap
最近在看《编程珠玑》这本书。 第1章中引入了bitmap(位图)的数据结构。以前没有接触过, 抽空研究了一下,记录下来。
书中描述的情景:
1. 最多1000万个7位数电话号码(号码不重复,实际大概800万个),保存在文本中
2. 每隔一段时间要对号码进行排序
3.程序模块最多可用1M Bytes的内存, 磁盘空间充足
分析:
通常方案:7位电话号码可以用uint32_t (4个字节)来存储, 4 * 8 * 10^6 Bytes约为32M Bytes,一次性排序显然内存不满足。
1M Bytes 内存可以存放 10^6/4 = 250万个号码, 1000万个约要分40趟进行读取排序写入文件,在归并到一起
此方案,需要40次读原始文本的代价,效率低下。
位图方案: 1个字节(8Bit)可以存放8个整数, 实际800万个号码,刚好1M Bytes的内存空间可以使用,符合要求。
一、原理
通常存储方案, 每个整数(假如4个字节), 占用内存多, 在内存不足或海量数据时, 导致处理方法复杂。
位图, 可以理解用位(Bit)来表示数据, 1个字节是8位, 可以存储8个连续的整数, 内存空间充分利用。 每一位 1表示有数据, 0 表示没有数据。
举例说明:
整数集合 {1 , 11, 9 , 7 , 10 }
5个整数,用通常存储方案,需要 5 * 4 = 20 字节
位图只需要 12位, 不到2个字节(通常是用2个字节来存放,方便管理和字节对齐)
这5个整数用位图表示如下:
0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
第1个字节,表示的数据范围 0 ~ 7; 第2个字节, 表示的数据范围 : 8 ~ 15
二、 一个整数(假设为N)位图的表示方法
1. 计算整数N属于哪个单元
1个字节(8Bit)可以存放8个连续的整数,一个位图可以划分为多个这样的小单元。
整数N除以8 的值可以判断在哪个单元中。
如例子中: 整数 9, 9 / 8 = 1(从0 开始计算的),可以知道在第2个字节单元中。
2. 位图中数据N的插入
每一个字节中,可以表示8个连续整数, 要确定N在单元中的确切位置
插入9之前:
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
插入9后可以表示为: X | (0X80 >> 9 % 8)
公式可以表示为: X | ( 0X80 >> N % 8)
推算过程: 0X80, 二进制表示 1000 0000 ,右移 9 % 8= 1位, 变为 0 100 0000,和 插入之前的数 “或”运算,就可以把9的位置设为1了。
3. 位图中整数N的查询
假设N 所在的划分单元的数值为 X,
公式可以表示为: X & ( 0X80 >> N % 8)
推算过程:0X80 右移 N % 8 位, 与X 进行“交”运算, 如果结果为0, 则整数N不在位图中, 反之,在位图中。
4. 位图中整数N的删除
假设N所在的划分单元的数值为X,
公式可以表示为: X & ~(0X80 >> N % 8)
推算过程:0X80 右移 N % 8 位,求反会把对应的为置为0,其他位为1, 再与X 进行“交”运算, 只把N所在单元的位置设为0
通过以上的分析,写代码就方便了。 我用c语言写了一个简单的测试代码:
_bitmap.h
#ifndef _BITMAP_H #define _BITMAP_H #include <stdint.h> static inline void bitmap_add(char* p, int64_t n) { p += n / 8; *p |= (0x80 >> n % 8); } static inline void bitmap_del(char* p, int64_t n) { p += n / 8; *p &= ~(0x80 >> n % 8); } // yes: > 0, no: 0 static inline int bitmap_lookup(char* p, int64_t n) { p += n / 8; return *p & (0x80 >> n % 8); } #endif /*_BITMAP_H*/
test.c
#include <stdio.h> #include "_bitmap.h" int main(int argc, char* argv[]) { uint32_t num[] = {7999, 6000, 0, 1, 13, 11, 12, 99, 88, 55, 77, 800, 5000}; #define SIZE 1000 char a[SIZE] = {0}; // Can store 0 ~ 7999 int i = 0; for (i = 0; i < sizeof(num) / sizeof(uint32_t); i++) { bitmap_add(a, num[i]); } //print bitmap char* p = a; for (i = 0; i < SIZE; i++) { int j = 0; for (j = 0; j < 8; j++) { if ((*p & (0x80 >> j))) printf("%d\t", i * 8 + j); } p++; } printf("\n"); // delete bitmap_del(a, 99); bitmap_del(a, 0); // print bitmap p = a; for (i = 0; i < SIZE; i++) { int j = 0; for (j = 0; j < 8; j++) { if ((*p & (0x80 >> j))) printf("%d\t", i * 8 + j); } p++; } printf("\n"); int x = 99; if (bitmap_lookup(a, x)) { printf("%d is in bitmap\n", x); } else { printf("%d is not in bitmap\n", x); } x = 7999; if (bitmap_lookup(a, x)) { printf("%d is in bitmap\n", x); } else { printf("%d is not in bitmap\n", x); } return 0; }
输出结果: