数据结构——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
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

插入9之后:

0 1 0 0 0 0 0 0
8 9 10 11 12 13 14 15

如果插入之前。单元数值为X,

插入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;
}

输出结果:

数据结构——bitmap

上一篇:C++代码书写规范——给新手程序员的一些建议


下一篇:jdbc操作mysql(三):利用注解封装