BitMap 算法
引导
如果我们现在有一堆数据,[0 ,3 ,4 ,7 ,9 ,1 ,2 ,5 ,6 ,8 ,2 ,3 ,5 ,7 ,9 ,0 ,1 ,4 ,6 ,8],需要对数据进行排重,只留下最原始的数据。
那么我们可以用如下方式实现：
package mainimport ( "fmt")func main() { //获取到一个数组
nums := []int{0, 3, 4, 7, 9, 1, 2, 5, 6, 8, 2, 3, 5, 7, 9, 0, 1, 4, 6, 8} //获取一个排重数组
numMap := map[int]bool{} //排重后的结果
newNums := []int{} for _, num := range nums {
_, ok := numMap[num] if ok { //已经存在了
continue
} //记录重复状态
numMap[num] = true
newNums = append(newNums, num)
}
fmt.Println("排除重复前：", nums)
fmt.Println("排除重复后：", newNums) //排除重复前： [0 3 4 7 9 1 2 5 6 8 2 3 5 7 9 0 1 4 6 8]
//排除重复后： [0 3 4 7 9 1 2 5 6 8]}流程如下
1 . 实例化一个map，存储标记。
image
2 . 如果数据存在，则改变状态。
3 . 不存在的数据，就加入到新的数组中。
4 . 排序完成。
不知小伙伴绝不觉得和计数排序的逻辑很像。当然优化方案也可以按照计数排序的方式。
缺点分析
针对数据量大的数据，我们需求的map就会很大。这样占用的空间特别高。所以针对这种情况我们需要一种替代方案来完成，海量数据排重操作。
BitMap
所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省
其实如果你知道计数排序的话，你就会发现这个和计数排序很像。
bitmap应用
可进行数据的快速查找，判重，删除。
去重数据而达到压缩数据.
目前bitmap在数据采集【大数据-爬虫】环节非常有用，比如对url去重。
bitmap 实现
package bitmapimport ( "bytes"
"sync")type Bit uint64 //统一bit类型const BitSize = 64 //每一个bit位存储数据量const IndexBit = 6 //位置位移数量type Bitmap []Bit //bitmapvar mux = sync.Mutex{}var bitsMap [BitSize]Bit//func init() {// for i := 0; i < BitSize; i++ {// bitsMap[i] = Bit(0x01) << Bit(i)// }//}//设置bitfunc (b *Bitmap) SetBit(value Bit, stat bool) *Bitmap {
mux.Lock() defer mux.Unlock()
index, pos := b.ValueToIndexAndPos(value) if stat {
b.UpCapToIndex(index) //设置
(*b)[index] |= Bit(0x01) << pos
} else { //取消
if index < len(*b) {
(*b)[index] &^= Bit(0x01) << pos
}
} return b
}func (b *Bitmap) Set(value Bit) *Bitmap {
b.SetBit(value, true) return b
}func (b *Bitmap) Unset(value Bit) *Bitmap {
b.SetBit(value, false) return b
}func (b *Bitmap) Get(value Bit) bool {
index, pos := b.ValueToIndexAndPos(value) //(*b)[index] &^= Bit(0x01) << pos
return index < len(*b) && ((*b)[index]&(Bit(0x01)<<pos) != 0)
}func (b *Bitmap) ValueToIndexAndPos(value Bit) (int, Bit) { return int(value >> IndexBit), value % Bit(BitSize)
}func (b *Bitmap) UpCapToIndex(index int) {
toIndex := index + 1
l := len(*b) if l < toIndex {
l2 := 2 * l if toIndex < l2 {
toIndex = l2
}
n := make([]Bit, toIndex, toIndex) copy(n, *b)
*b = n
}
}func (b *Bitmap) ToString(split ...string) string {
l := len(*b)
sl := len(split)
ss := ""
if sl > 0 {
ss = split[0]
}
str := ""
for i := 0; i < l; i++ { if i > 0 && sl > 0 {
str += ss
}
str += (*b)[i].ToString()
} return str
}func (bit *Bit) ToString() string {
b := &bytes.Buffer{}
t := *bit for i := 0; i < BitSize; i++ { if (t & bitsMap[i]) != 0 {
b.WriteString("1")
} else {
b.WriteString("0")
}
} return b.String()
}关键技能解析
位运算
为了更好描述效果，这里我们使用较小的数据类型： byte ，一个byte包含8bit位。
package mainimport ( "fmt"
"github.com/imroc/biu")func main() { var b byte
b = 1
fmt.Println("常规展示：", b) // 原始数据: 1
fmt.Println("二进制位：", biu.ByteToBinaryString(b)) //二进制方式：00000001
//向左移动一位
b = b << 1
fmt.Println("左边移动一位：", b) // 原始数据: 2
fmt.Println("二进制位：", biu.ByteToBinaryString(b)) //二进制方式：00000010
var b1 byte = 3
fmt.Println("b1=：", b1) // 原始数据: 3
fmt.Println("二进制位：", biu.ByteToBinaryString(b1)) //二进制方式：00000011
// 或（|） 运算: 二进制位中对应位置有1则为1，否则为0。
// 2 的二进制为： 10 ， 3 的二进制为： 11
// 那么 2|3 = 11
fmt.Println("（2|3）二进制位：", biu.ByteToBinaryString(2|3)) //二进制方式：00000011
// 与（&） 运算: 二进制位中对应位置都为1则为1，否则为0。
// 2 的二进制为： 10 ， 3 的二进制为： 11
// 那么 2&3 = 10
fmt.Println("（2&3）二进制位：", biu.ByteToBinaryString(2&3)) //二进制方式：00000010
//异或（^）运算： 二进制中对应位置不同的为1，否则为0.
// 2 的二进制为： 10 ， 3 的二进制为： 11
// 那么 2^3 = 01
fmt.Println("（2^3）二进制位：", biu.ByteToBinaryString(2^3)) //二进制方式：00000001
var c = byte(2) //取反（^）:二进制中的所有位置 0 为1,1为 0.
fmt.Println("（^2）常规输出：", ^c) //二进制方式：253
fmt.Println("（^2）二进制位：", biu.ByteToBinaryString(^c)) //二进制方式：11111101}Bitmap使用
bm := &bitmap.Bitmap{} //实例化bitmap
bm.SetBit(100, true) //设置位置100
bm.SetBit(12, true)
bm.SetBit(1, true)
bm.SetBit(12, true) //设置位置12
//获取状态
fmt.Println("bit:100：",bm.Get(100)) //true
fmt.Println("bit:12：",bm.Get(12)) //true
//取消设置
bm.SetBit(12, false)
fmt.Println("bit:12：",bm.Get(12)) //false
作者：小码侠
链接：https://www.jianshu.com/p/b37e54255cf5