golang实现位图(BitSet)

一,概念

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))
}