一,概念
Bitmap (位图)是一个十分有用的数据结构。所谓的 Bit-map 就是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此在内存占用方面，可以大大节省。（《编程珠玑》第一章引入的问题，提到了 Bitmap）
二,实现基本原理
类似于java的BitSet,是位操作的对象，值只有0或1，内部维护了一个long数组，初始只有一个long，所以BitSet最小的size是64，当随着存储的元素越来越多，BitSet内部会动态扩充，最终内部是由N个long来存储，这些针对操作都是透明的。
用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用用的时候既可根据某一个是否为0表示，此数是否出现过。
一个1G的空间，有 8*1024*1024*1024=8.58*10^9bit，也就是可以表示85亿个不同的数
三,代码实现
1. 实现操作set: 将指定位置置为1.
2. 实现操作clear: 将指定位置置为0.
3. 实现操作get: 查找指定位置的值.
4. 容量自动扩展.
import (
"bytes"
)
//bitSet实现
type BitSet []uint64
const (
Address_Bits_Per_Word uint8 = 6
Words_Per_Size uint64 = 64 //单字64位
)
//创建指定初始化大小的bitSet
func NewBitMap(nbits int) *BitSet {
wordsLen := (nbits - 1) >> Address_Bits_Per_Word
temp := BitSet(make([]uint64,wordsLen+1,wordsLen+1))
return &temp
}
//把指定位置设为ture
func (this *BitSet) Set(bitIndex uint64) {
wIndex := this.wordIndex(bitIndex)
this.expandTo(wIndex)
(*this)[wIndex] |= uint64(0x01) << (bitIndex % Words_Per_Size)
}
//设置指定位置为false
func (this *BitSet) Clear(bitIndex uint64) {
wIndex := this.wordIndex(bitIndex)
if wIndex < len(*this) {
(*this)[wIndex] &^= uint64(0x01) << (bitIndex % Words_Per_Size)
}
}
//获取指定位置的值
func (this *BitSet) Get(bitIndex uint64) bool {
wIndex := this.wordIndex(bitIndex)
return (wIndex < len(*this)) && ((*this)[wIndex]&(uint64(0x01)<<(bitIndex%Words_Per_Size)) != 0)
}
//以二进制串的格式打印bitMap内容
func (this *BitSet) ToString() string {
var temp uint64
strAppend := &bytes.Buffer{}
for i := 0; i < len(*this); i++ {
temp = (*this)[i]
for j := 0; j < 64; j++ {
if temp&(uint64(0x01)<<uint64(j)) != 0 {
strAppend.WriteString("1")
} else {
strAppend.WriteString("0")
}
}
}
return strAppend.String()
}
//定位位置
func (this BitSet) wordIndex(bitIndex uint64) int {
return int(bitIndex >> Address_Bits_Per_Word)
}
//扩容:每次扩容两倍
func (this *BitSet) expandTo(wordIndex int) {
wordsrequired := wordIndex + 1
if len(*this) < wordsrequired {
if wordsrequired < 2*len(*this) {
wordsrequired = 2 * len(*this)
}
newCap := make([]uint64,wordsrequired,wordsrequired)
copy(newCap,*this)
(*this) = newCap
}
}
5. 使用举例: 查找指定数字,在数列中是否出现. (由于位图很节省空间,所以比较适合单击大数据的查找)
func start_bitMap() {
bMap := NewBitMap(64)
for i := 100; i < 1000; i++ {
bMap.set(uint64(i))
}
fmt.Printf("bmap第133个位置:%v \n",bMap.get(133))
fmt.Printf("bmap2string:%s \n",bMap.toString())
fmt.Printf("end:cap=%d,len=%d \n",cap(*bMap),len(*bMap))
}
