golang之路--bitmap 实现

介绍一下bitmap的思想:

 

情景1：

有些时候我们为了判断一个某个元素是否存在一个集合中，普通的方式是map[int]xxxx存储。数据量小的时候还可以

待数据量庞大的时候，比如我们判断某人的momoid是否在某个Momoid切片中，存储就悲剧了。算一下：

一个int = 4byte  倘若存储500W个数据 4 * 500 * 1000  / 1024 /1024 = 2G的存储,怎么办放弃吧…

 

改进：

对于这种数字形式存在性问题上完全可以用bit的0，1来确定数字的存在。那么之前的一个int = 32bit 只能存储 1种状态

现在可以存储 32X  个数字状态。瞬间 存储空间降低额32倍。

 

算法：

设定 : int  为 32 bit     

 int[] bitmap  

1.给定一个整数计算其归属的数组下标，因为是 0 - 31 ，32 - 63 ….为一个整数 很显然下标计算就是

 

      idx = momoid  / 32 = momoid >> 5 

 

2，设置改下标 bitmap[ idx ] 对应整数的位标识，很显然，只要对 momoid 对 32 取余即可得到状态位下标

 

bitIdx = momoid % 32  

 

3. 设置该数的状态, 只要将1<< bitidx 位 再与bitmap[idx] 值求或就可完成

 

bitmap[idx] = bitmap[idx] | ( 1 << bitidx)

 

状态位，删除、判断存在性与否 不再赘述了。

 

 

好处：

省空间、查询方便

 

附上实现代码：

 

 

var bitmap []uint32 = make([]uint32, MAX)

 

const (

SHIFT = uint32(5)

MASK  = 0x1F

MAX   = 1024 * 1024 * 1024

)

 

/**

* 整数32Bit可表示32个整数是否存在

* 只要将整数除以32既可以得到下标

* 而32位的置位0或1可以直接通过对

* momoid求mod获取对第几位置位

*/

func AddUser(momoid uint32) {

//对32位置位即对momoid进行取mod获得第几位置位

bitmap[momoid>>SHIFT] |= (1 << (momoid & MASK))

}

 

/** 

* 判断是否存在

* 直接取出 第几位判断该位是否为1即可

*/

func ContainUser(momoid uint32) bool {

return (bitmap[momoid>>SHIFT]>>(momoid&MASK))&0x01 == 1

}

 

/**

* 删除用户

* 把momoid % MASK 位数 设置为 0即可

* 方式下：

* ^(momoid % MASK) & bitmap 

*/

func DelUser(momoid uint32) {

bitNum := ^(bitmap[momoid>>SHIFT] & (1 << (momoid & MASK)))

bitmap[momoid>>SHIFT] &= bitNum

}

评论

1 楼 hardPass 2013-05-31  

引用

算一下：
一个int = 4byte  倘若存储500W个数据 4 * 500 * 1000  / 1024 /1024 = 2G的存储,怎么办放弃吧…

大锅，500W个数据 是多少啊？ 应该是5,000,000

4* 5 * 1000 * 1000 Byte = 20MB?