golang実装ビットマップ(BitSet)

一、概念
Bitmap(ビットマップ)は非常に有用なデータ構造である.Bit-mapとは、ある要素に対応するValueをビットでマークし、Keyはその要素です.Bit単位でデータを格納するため、メモリの消費量を大幅に節約できます.(「プログラミング珠玉」第1章で導入された問題はBitmapに言及)
二、基本原理を実現する
JavaのBitSetと同様に、ビット操作のオブジェクトであり、値は0または1のみであり、内部にはlong配列が維持され、初期にはlongが1つしかないため、BitSetの最小sizeは64であり、格納要素が多くなるにつれてBitSet内部は動的に拡張され、最終的に内部はN個のlongによって格納され、これらは操作に対して透明である.
1ビットで1つのデータが現れたかどうかを表し、0は現れなかったか、1は現れたことを表す.使用するときは、ある1つが0であるかどうかによって、この数が現れたことがあるかどうかを表すことができます.
1 Gの空間で、8*1024*1024*1024=8.58*10^9 bit、つまり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)<> 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 
", bMap.get(133))
	fmt.Printf("bmap2string:%s 
", bMap.toString())
	fmt.Printf("end:cap=%d,len=%d 
", cap(*bMap), len(*bMap))
}