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)
?
状态位，删除、判断存在性与否 不再赘述了。
?
?
好处：
省空间、查询方便
?
用途：
准备在附近列表mongo拆分中用来用户地点更新时，来查询此用户上一次位置属于哪个mongo中，来删除旧记录
旧方案中，得查一次redis获取上一次位置，再判断从属哪个mongo，替换后只要内存查询即可。
?
?
附上实现代码：
?
?
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
}
