【数据结构】哈希应用-STL-位图

目录

1、位图的概念

2、位图的设计与实现

 2.1 set

2.2 reset

2.3 test

3、C++库中的位图

4、位图的优缺点

5、位图相关题目

1、位图的概念

面试题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

法一：遍历，时间复杂度是O(N)，太慢

法二：排序 + 二分查找。时间复杂度是O(N * logN) + O(logN)。只是第一次比较慢，后面就快了。使用这个方法有一个致命的缺陷是存放40亿个数据需要的内存太过庞大。

1GB = 1024MB = 1024 * 1024KB = 1024 * 1024 * 1024Byte

所以40亿个数据约等于16GB，说明40亿个数据是无法直接放到内存中的，只能放到硬盘文件中。而二分查找只能对内存数组中的有序数据就行查找。这里使用数组是最节省空间的，因为每个位置只存放数据，如果使用红黑树或哈希表需要的空间还要更大

法三：使用位图

数据是否在给定的整型数据中，结果是在或不在，刚好是两种状态，那么可以用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，如果二进制比特位为0，代表不存在。那么我们就可以设计一个用位表示数据是否存在的数据结构，这个数据结构就是位图。

2、位图的设计与实现

实现中要注意的是，C/C++中没有对应位的类型，只能看char/int这样的整型类型，我们再通过位运算去控制对应的比特位。比如我们数据存到vector<int>中，相当于每个Int映射对应的32个值，比如第一个整型映射0~31对应的位，第二个整型映射32~63对应的位，后面依次类推。那么来一个无符号整型x，i = x / 32，j = x % 32，x映射的位置就是vector第i个整型数据的第j位。

我的机器是小端存储，所以一个整型中，低位是在右边

 对于上面40亿个无符号整型，我们开空间需要开2^32个，因为无符号整型有2^32个，不是根据数据个数来开空间 

namespace cxf
{template<size_t N> // 开N个位的位图class bitset{public:bitset(){_bs.resize(N / 32 + 1); // 因为N除32可能会除不尽，所以多开一个整型，保证位够}private:std::vector<int> _bs;};
}

 2.1 set

向位图中插入数据，也就是将插入数据映射到的位标记成1

假设要向位图中插入数据77，要如何操作呢？

首先计算出位为77的地方位于第几个整型数据的第几个位。会发现位于第3个整型数据的第13个位，然后将1左移13个位的结果与第3个整型数据按位或，就可以将插入数据映射到的位标记成1

void set(size_t x)
{size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);
}

2.2 reset

向位图中删除数据，也就是将传入数据映射到的位标记成0

假设要向位图中删除数据77，要如何操作呢？

首先计算出位为77的地方位于第几个整型数据的第几个位。会发现位于第3个整型数据的第13个位，然后将1左移13个位再按位取反的结果与第3个整型数据按位与，就可以将插入数据映射到的位标记成0

void reset(size_t x)
{size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));
}

2.3 test

若传入数据映射到的位是1就返回真，是0就返回假

bool test(size_t x)
{size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);
}

可以测试一下

void test_bitset()
{cxf::bitset<100> bs; // 开一个100个位的位图bs.set(77);bs.set(66);cout << bs.test(77) << endl;cout << bs.test(66) << endl;bs.reset(66);cout << bs.test(77) << endl;cout << bs.test(66) << endl;
}

结果是1 1 1 0，是正确的

那要如何开2^32个空间呢？有3种方法

cxf::bitset<-1> bs1;
cxf::bitset<0xffffffff> bs2;
cxf::bitset<UINT_MAX> bs3;

namespace cxf
{template<size_t N> // 开N个位的位图class bitset{public:bitset(){_bs.resize(N / 32 + 1); // 因为N除32可能会除不尽，所以多开一个整型，保证位够}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:std::vector<int> _bs;};
}

3、C++库中的位图

与前面我们自己实现的位图是差不多的，operator[]可以像数组一样控制某个位

要注意，库中的位图是不能直接开2^32个空间的

void test_bitset2()
{std::bitset<UINT_MAX> bs;
}

像这样程序会崩溃的，因为我们自己实现的位图底层是使用vector，是去堆上开空间，而库中的位图是用一个静态数组实现的，没办法开太大。我们可以对其就行测试

void test_bitset2()
{cxf::bitset<100> bs1;cxf::bitset<10000> bs2;std::bitset<100> bs3;std::bitset<10000> bs4;cout << sizeof(bs1) << " ";cout << sizeof(bs2) << " ";cout << sizeof(bs3) << " ";cout << sizeof(bs4) << " ";
}

结果是16 16 16 1256

当然，是可以通过指针来解决的

std::bitset<-1>* ptr = new std::bitset<-1>();

4、位图的优缺点

优点：增删查改快，时间复杂度均为O(1)，节省空间

缺点：只适用于整型

5、位图相关题目

位图的应用：

题目一：给定100亿个整数，设计算法找到只出现一次的整数。

注意：此时虽然是100亿个整数，但是还是按范围开空间，所以还是开2^32个位，与前面一样

法一：可以用两个位来标记一个数,00表示没出现过，01表示出现了1次，10表示出现了2次及以上法二：用两个位图，一个数在每个位图中各占一个位，规则与法一相同

题目二：一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数

与上面类似，只不过这里是00表示没出现过，01表示出现了1次，10表示出现了2次，11表示出现3次及以上

我们来复用前面实现的位图来对这两个问题就行实现

namespace cxf
{template<size_t N> // 开N个位的位图class bitset{public:bitset(){_bs.resize(N / 32 + 1); // 因为N除32可能会除不尽，所以多开一个整型，保证位够}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:std::vector<int> _bs;};template<size_t N>class twobitset{public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2) // 00->01{_bs2.set(x);}else if (!bit1 && bit2) // 01->10{_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2) // 10->11{_bs2.ser(x);}}int get_count(size_t x) // 返回x出现的次数{bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2) return 0;else if (!bit1 && bit2) return 1;else if (bit1 && !bit2) return 2;else return 3;}private:bitset<N> _bs1;bitset<N> _bs2;};
}

题目三：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？

把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值就是交集