问题导入

解决方案

用哈希表位图概念， 但是每个key只占用一个bite位， 用0表示没有本key， 1表示有此key

位图实现

三个主要接口

set（key）， 将key设成1

reset（key）： 将key设成0

test（key）：查看key是否存在

实现方式：异或来 查/改 比特位

源代码

namespace bit
{template<size_t N>class bitset{public:bitset(){_bs.resize(N / 32 + 1);}// x映射的位标记成1void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}// x映射的位标记成0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}// x映射的位是1返回真// x映射的位是0返回假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;};

使用范围（优缺点）

源码/板书

课件， 代码地址：24年-07月25日--哈希加餐-扩展学习 · 比特杭哥/112期 - 码云 - 开源中国 (gitee.com)

 板书