位图

嵌牛导读：位图的引出，主要还是在于当我们想做一个很大的set的时候，位图可以帮助我们节省非常大的空间。

嵌牛鼻子：位图

嵌牛提问：处理算法复杂度过高，如何降低算法复杂度呢？

嵌牛正文：

比如说：我们有1千万个整数，整数的范围在1到1亿之间。如何快速查找某个整数是否在1千万个整数中呢？

非常简单的话，我们可以用一个桶来做。但是会浪费90%的空间。即做一个1亿大小的bool数组，哪个数存在，哪个置为true。需要100M空间

用一个散列表。假设散列函数非常完美，有50%的占有率的一个hashset。我们需要2千万 * 4 = 80M大小的空间。但是这里的散列函数是有一点计算复杂度的。

引出

而我们的位图就是用的第一种思想，但是，我们用一个字节来表示俩个状态，true和false太过浪费，我们就只用1个bit来表示。

所以就只需要100M / 8 = 20 大概不到20M左右的空间。

小坑

我们的想法是非常好的，但是要怎么操作呢？大部分语言中让我们可以操纵的最小计算机单位是1个字节。即我们是没办法直接去操纵一个位的。因此我们就需要一个映射。

Add

原来的想法

如果我们想要表示1个数字已经存在，比如x。我们直接就是

vector<bool> charVec;

charVec[x] = true;

这样就可以了。

上面的想法实际上就是置第x+1个bool值为true，位图的想法就是去置第x+1个bit值为1

但是大部分语言提供的最小的可操作单位就是一个字节。因此我们就需要做一个简单的映射

int index = x / 8

int bit = x % 8

charVec[index] |= 1 << bit

// 或者

vector<int16t> int16Vec

int index = x / 16

int bit = x % 16

int16Vec[index] |= 1 << bit

// 或者

vector<int32t> int32Vec

int index = x / 32

int bit = x % 32

int32Vec[index] |= 1 << bit

我觉得上面的代码已经讲得非常清楚了，用语言表示反而比较苍白无力。

比如说我们想要Add(100)，我们就需要在第101个bit上置1。（我们的第一个bit置1表示0，这个可以自己修改），然后我们就要算出第101个bit首先在第多少个字节上。其在第index个字节上。然后再算出其在第多少个bit上。其在第bit+1个bit上。大概就是这样的一个数学关系，举几个例子就很好理清楚。

Has

如何判断一个数是否在我们在set中呢？

int index = x / 8

int bit = x % 8

if( charVec[index] & (1 << bit) )

    return true

备注：以上是大概类似c++形式的伪代码。仅仅做了俩个方法，C++11是新出了bitset的数据结构供我们使用的。非常方便。我自己就不重复造轮子了。下面是《Go语言圣经》中的部分源码，注意其底层结构时动态增长的。

go源码

type IntSet struct {

words []uint64

}

func (s *IntSet) Has(x int) bool {

index, bit := x/64, uint(x%64)

return index < len(s.words) && s.words[index]&(1<<bit) != 0

}

func (s *IntSet) Add(x int) {

index, bit := x/64, uint(x%64)

// 扩容，如果下标不够就需要扩容

for index >= len(s.words) {

s.words = append(s.words, 0)

}

s.words[index] |= (1 << bit)

}

// 合并俩个set

func (s *IntSet) UnionWith(t *IntSet) {

for i, tword := range t.words {

if i < len(s.words) {

s.words[i] |= tword

} else {

s.words = append(s.words, tword)

}

}

}

func (s *IntSet) String() string {

var buf bytes.Buffer

buf.WriteByte('{')

for i, word := range s.words {

if word == 0 {

continue

}

for j := 0; j < 64; j++ {

if word&(1<<uint(j)) != 0 {

if buf.Len() > len("{") {

buf.WriteByte(' ')

}

fmt.Fprintf(&buf, "%d", 64*i+j)

}

}

}

buf.WriteByte('}')

return buf.String()

}