C++ 哈希+unordered

文章目录

• 1. 前言
• 2. unordered 系列关联式容器
• • 2.1 unordered_map
  • • 2.1.1 unordered_map 的概念
    • 2.1.2 unordered_map 的使用
    • 2.2 unordered_set
    • • 2.2.1 unordered_set 的概念
      • 2.2.2 unordered_set 的使用
      • 3. 底层结构
      • • 3.1 哈希的概念
        • 3.2 哈希冲突
        • 3.3 哈希函数
        • 3.4 哈希冲突的解决
        • • 3.4.1 闭散列
          • 3.4.2 开散列
          • 4. 模拟实现
          • • 4.1 哈希表的改造
            • 4.2 unordered_map 的模拟实现
            • 4.3 unordered_set 的模拟实现
            • 5. 哈希的应用
            • • 5.1 位图
              • • 5.1.1 位图的概念
                • 5.1.2 位图的实现
                • 5.1.3 位图的应用
                • 5.2 布隆过滤器
                • • 5.2.1 布隆过滤器的提出
                  • 5.2.2 布隆过滤器的概念
                  • 5.2.3 布隆过滤器的实现
                  • 5.2.4 布隆过滤器的优点
                  • 5.2.5 布隆过滤器的缺陷

                    ---

                    1. 前言

                    想象一下，你有一个巨大的图书馆，里面摆满了成千上万本书。如果你想要找到其中一本特定的书，你会怎么做？如果你按照书的编号来有序地排列它们，找到特定的书本可能会很容易。但是，如果书籍是随机地摆放，你可能需要逐本地查找，这个过程会非常耗时。

                    
                    （图片来源网络，侵删）

                    而哈希函数就像是给每本书分配一个独特的编号，然后将它们放置在合适的位置，使得我们能够快速地找到并访问它们。哈希函数能够将输入数据映射到一个固定大小的哈希表中，每个元素都有一个唯一的位置。当我们需要查找特定的元素时，只需使用哈希函数计算出它的位置，然后直接访问该位置的元素，无需遍历整个数据集。

                    这种基于哈希的快速查找技术在现代编程中非常常见。在本篇博客中，我们将深入剖析哈希相关的知识点。

                    本篇文章将着重讲解 unordered 系列关联式容器（unordered_map 和 unordered_set）、底层结构（哈希的概念、哈希函数、哈希冲突）、模拟实现（unordered_map 和 unordered_set 的模拟实现）以及哈希的应用（位图和布隆过滤器）。

                    2. unordered 系列关联式容器

                    在 C++98 中，STL 提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log_2N log2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在 C++11 中，STL又提供了4个 unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对 unordered_map 和 unordered_set 进行介绍。

                    2.1 unordered_map

                    2.1.1 unordered_map 的概念

                    英文解释：

                    

                    也就是说：

                    
                    （图片来源网络，侵删）

                    1. unordered_map 是存储 键值对的关联式容器，其允许通过 key 快速的索引到与其对应的 value。

                    2. 在 unordered_map 中，键值通常用于唯一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

                    3. 在内部，unordered_map 没有对 按照任何特定的顺序排序, 为了能在常数范围内找到 key 所对应的 value，unordered_map 将相同哈希值的键值对放在相同的桶中。

                    4. unordered_map 容器通过 key 访问单个元素要比 map 快，但它通常在遍历元素子集的范围迭代方面效率较低。

                    5. unordered_map 实现了直接访问操作符（operator[]），它允许使用 key 作为参数直接访问 value。

                    6. 它的迭代器至少是单向迭代器。

                       
                       （图片来源网络，侵删）

                    2.1.2 unordered_map 的使用

                    1. unordered_map 的模板参数列表

                       

                       说明：

                       • key：键值对中 key 的类型。
                       • T：键值对中 value 的类型。
                       • Hash：哈希函数用于确定元素在内部数据结构中的位置。
                       • Pred：键相等判断函数用于比较两个键是否相等。
                       • Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。

                       • unordered_map 的构造函数

                         函数声明	功能介绍
                         unordered_map	构造不同格式的 unordered_map 对象。

                       • unordered_map 的容量操作

                         函数名称	函数声明	功能简介
                         empty	bool empty () const;	检测 unordered_map 中的元素是否为空，是返回 true，否则返回 false。
                         size	size_t size() const;	返回 unordered_map 中有效元素的个数。

                       • unordered_map 的元素访问操作

                         函数名称	函数声明	功能简介
                         operator[]	mapped_type& operator[] (const key_type& k);	返回 k 对应的 value。
                         at	mapped_type& at (const key_type& k); const mapped_type& at (const key_type& k) const;	返回 k 对应的 value。

                         区分：

                         在元素访问时，有一个与 operator[] 类似的操作 at 函数（该函数不常用），都是通过 key 找到与 key 对应的 value 然后返回其引用，不同的是：当 key 不存在时，operator[] 用默认 value 与 key 构造键值对然后插入，返回该默认 value；at 函数直接抛异常。

                       • unordered_map 的查找操作

                         函数名称	函数声明	功能介绍
                         find	iterator find (const key_type& k); const_iterator find (const key_type& k) const;	在 unordered_map 中查找 key 为 k 的元素，找到返回该元素位置的迭代器，否则返回 end。 在 unordered_map 中查找 key 为 k 的元素，找到返回该元素位置的 const 迭代器，否则返回 cend。
                         count	size_t count (const key_type& k) const;	返回 unordered_map 中值为 k 的键值在 map 中的个数（这里只会返回0或1）。

                       • unordered_map 的修改操作

                         函数名称	函数声明	功能介绍
                         insert	pair insert (const value_type& val);	在 unordered_map 中插入键值对 val。如果插入成功，返回 ；如果插入失败，说明 val 在 unordered_map 中已经存在，返回 。
                         erase	iterator erase (const_iterator position); size_t erase (const key_type& k);	删除 unordered_map 中 position 位置上的元素，并返回一个指向被删除元素之后位置的迭代器。 删除 unordered_map 中键值为 k 的元素，返回删除的元素的个数（这里只会返回0或1）。
                         swap	void swap (unordered_map& ump);	与 ump 交换元素。
                         clear	void clear();	将 map 的元素清空。

                       • unordered_map 的桶操作

                         函数名称	函数声明	功能介绍
                         bucket_count	size_t bucket_count() const	返回哈希桶中桶的总个数。
                         bucket_size	size_t bucket_size(size_t n) const	返回 n 号桶中有效元素的总个数。
                         bucket	size_t bucket(const key_type& k)	返回元素 k 所在的桶号。

                    2.2 unordered_set

                    2.2.1 unordered_set 的概念

                    英文解释：

                    

                    也就是说：

                    1. unordered_set 是一种容器，它以无特定顺序存储唯一元素，并且允许根据 value 快速检索单个元素。

                    2. 在 unordered_set 中，元素的 value 同时也是唯一标识它的 key。键是不可变的，因此，在容器中的元素一旦插入就不能修改，尽管可以插入和删除。

                    3. 在内部，unordered_set 中的元素没有按照任何特定的顺序排序，而是根据它们的哈希值被组织到不同的桶中，以便能够通过值快速直接地访问单个元素（平均情况下具有常数时间复杂度）。

                    4. 与集合容器相比，unordered_set 容器更快地通过 key 访问单个元素，尽管对于对子集进行范围迭代，它们通常不太高效。

                    5. 容器中的迭代器至少是单向迭代器。

                    2.2.2 unordered_set 的使用

                    1. unordered_set 的模板参数列表

                       

                       说明：

                       • T：unordered_set 中存放元素的类型。

                       • Hash：哈希函数用于确定元素在内部数据结构中的位置。

                       • Pred：键相等判断函数用于比较两个键是否相等。

                       • Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。

                       • unordered_set 的构造函数

                         函数声明	功能介绍
                         unordered_set	构造不同格式的 unordered_set 对象。

                       • unordered_set 的容量操作

                         函数名称	函数声明	功能介绍
                         empty	bool empty() const;	检测 unordered_set 是否为空，空返回 true，否则返回 false。
                         size	size_t size() const;	返回 unordered_set 中有效元素的个数。

                       • unordered_set 的查找操作

                         函数名称	函数声明	功能介绍
                         find	iterator find (const value_type& val) const;	在 unordered_set 中查找值为 val 的元素，如果找到则返回该元素位置的迭代器，未找到则返回 end 迭代器。
                         count	size_t count (const value_type& val) const;	返回 unordered_set 中值为 val 的元素的个数（这里只会返回0或1）。

                       • unordered_set 的修改操作

                         函数名称	函数声明	功能介绍
                         insert	pair insert (const value_type& val);	在 unordered_set 中插入元素 val。如果插入成功，返回 ；如果插入失败，说明 val 在 unordered_set 中已经存在，返回 。
                         erase	iterator erase (const_iterator position); size_t erase (const value_type& val);	删除 unordered_set 中 position 位置上的元素，并返回一个指向被删除元素之后位置的迭代器。 删除 unordered_set 中值为 val 的元素，返回删除的元素的个数（这里只会返回0或1）。
                         swap	void swap (unordered_set& ust);	与 ust 交换元素。
                         clear	void clear();	将 unordered_set 的元素清空。

                       • unordered_set 的桶操作

                         函数名称	函数声明	功能介绍
                         bucket_count	size_t bucket_count() const	返回哈希桶中桶的总个数。
                         bucket_size	size_t bucket_size(size_t n) const	返回 n 号桶中有效元素的总个数。
                         bucket	size_t bucket(const key_type& k)	返回元素 k 所在的桶号。

                    3. 底层结构

                    3.1 哈希的概念

                    顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( l o g 2 N log_2 N log2​N)，搜索的效率取决于搜索过程中元素的比较次数。

                    理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

                    如果构造一种存储结构，通过某种函数（hashFunc）使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

                    当向该结构中：

                    • 插入元素

                      根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。

                    • 搜索元素

                      对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

                      该方式即为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（Hash Table）（或者称散列表）。

                      例如：

                      数据集合：{ 1,7,6,4,5,9 };

                      哈希函数设置为：hash(key) = key % capacity;（capacity 为存储元素底层空间总的大小）

                      图解：

                      

                      注：用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。

                      3.2 哈希冲突

                      对于两个数据元素的关键字 k i k_i ki​ 和 k j k_j kj​（i != j），有 k i k_i ki​ != k j k_j kj​，但有：Hash( k i k_i ki​) == Hash( k j k_j kj​)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

                      把具有不同关键码而具有相同哈希地址的数据元素称为同义词。

                      发生哈希冲突该如何处理呢？

                      3.3 哈希函数

                      引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

                      哈希函数设计原则：

                      • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。
                      • 哈希函数计算出来的地址能均匀分布在整个空间中。
                      • 哈希函数应该比较简单。

                        常见哈希函数

                        1. 直接定址法（常用）

                        取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

                        优点：简单、均匀。

                        缺点：需要事先知道关键字的分布情况。

                        使用场景：适合查找比较小且连续的情况。

                        1. 除留余数法（常用）

                        设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key % p(pEMPTY, EXIST, DELETE}; size_t operator()(const K& key) { return (size_t)key; } }; // 字符串哈希函数特化：HashFunc size_t operator()(const string& key) { // BKDR size_t hash = 0; for (auto e : key) { hash *= 31; hash += e; } return hash; } }; namespace open_address { enum Status { EMPTY, EXIST, DELETE }; template pair public: HashTable() { _tables.resize(10); } bool Insert(const pair if (Find(kv.first)) return false; // 负载因子0.7就扩容 if (_n * 10 / _tables.size() == 7) { size_t newSize = _tables.size() * 2; HashTable if (_tables[i]._s == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } Hash hf; // 线性探测 size_t hashi = hf(kv.first) % _tables.size(); while (_tables[hashi]._s == EXIST) { hashi++; hashi %= _tables.size(); } _tables[hashi]._kv = kv; _tables[hashi]._s = EXIST; ++_n; return true; } HashData Hash hf; size_t hashi = hf(key) % _tables.size(); while (_tables[hashi]._s != EMPTY) { if (_tables[hashi]._s == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } hashi++; hashi %= _tables.size(); } return nullptr; } // 伪删除法 bool Erase(const K& key) { HashData ret-_s = DELETE; --_n; return true; } else { return false; } } // 打印观察分布 void Print() { for (size_t i = 0; i _kv.first == key) { if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; return true; } prev = cur; cur = cur->_next; } return false; } Node* Find(const K& key) { Hash hf; size_t hashi = hf(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; } size_t Count(const K& key) { Hash hf; KeyOfT kot; size_t hashi = hf(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return 1; } cur = cur->_next; } return 0; } // 桶的总个数 size_t BucketCount() { size_t bucketCount = 0; for (size_t i = 0; i _next; } return bucketSize; } // 打印信息 void Some() { size_t bucketSize = 0; size_t maxBucketLen = 0; size_t sum = 0; double averageBucketLen = 0; for (size_t i = 0; i _next; } sum += bucketLen; if (bucketLen > maxBucketLen) { maxBucketLen = bucketLen; } } averageBucketLen = (double)sum / (double)bucketSize; printf("all bucketSize:%d\n", _tables.size()); printf("bucketSize:%d\n", bucketSize); printf("maxBucketLen:%d\n", maxBucketLen); printf("averageBucketLen:%lf\n\n", averageBucketLen); } private: vector _tables; size_t _n = 0; }; }

                        开散列与闭散列比较

                        应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a HashNode} }; template typedef HashNode} __HTIterator(Node* node, const HashTable} Self& operator++() { if (_node-_next) { // 当前桶还有节点，走到下一个节点 _node = _node->_next; } else { // 当前桶已经走完了，找下一个桶开始 ++_hashi; while (_hashi _tables.size()) { if (_pht->_tables[_hashi]) { _node = _pht->_tables[_hashi]; break; } ++_hashi; } if (_hashi == _pht->_tables.size()) { _node = nullptr; } } return *this; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) { return _node != s._node; } };

                      • 改造后代码实现

                        template
                        class HashTable
                        {
                        	typedef HashNode Node;
                        	template
                        	friend struct __HTIterator;
                        public:
                        	typedef __HTIterator iterator;
                        	typedef __HTIterator const_iterator;
                        	iterator begin()
                        	{
                        		for (size_t i = 0; i _next;
                        				delete cur;
                        				cur = next;
                        			}
                        			_tables[i] = nullptr;
                        		}
                        	}
                        	size_t Size() const
                        	{
                        		return _n;
                        	}
                        	bool Empty() const
                        	{
                        		return _n == 0;
                        	}
                        	pair Insert(const T& data)
                        	{
                        		Hash hf;
                        		KeyOfT kot;
                        		iterator it = Find(kot(data));
                        		if (it != end())
                        			return make_pair(it, false);
                        		// 负载因子最大到1
                        		if (_n == _tables.size())
                        		{
                        			vector newTables;
                        			newTables.resize(_tables.size() * 2, nullptr);
                        			// 遍历旧表
                        			for (size_t i = 0; i _next;
                        					// 挪动到映射的新表
                        					size_t hashi = hf(kot(cur->_data)) % newTables.size();
                        					cur->_next = newTables[i];
                        					newTables[hashi] = cur;
                        					cur = next;
                        				}
                        				_tables[i] = nullptr;
                        			}
                        			_tables.swap(newTables);
                        		}
                        		size_t hashi = hf(kot(data)) % _tables.size();
                        		Node* newnode = new Node(data);
                        		// 头插
                        		newnode->_next = _tables[hashi];
                        		_tables[hashi] = newnode;
                        		++_n;
                        		return make_pair(iterator(newnode, this, hashi), true);
                        	}
                        	bool Erase(const K& key)
                        	{
                        		Hash hf;
                        		KeyOfT kot;
                        		size_t hashi = hf(key) % _tables.size();
                        		Node* prev = nullptr;
                        		Node* cur = _tables[hashi];
                        		while (cur)
                        		{
                        			if (kot(cur->_data) == key)
                        			{
                        				if (prev == nullptr)
                        				{
                        					_tables[hashi] = cur->_next;
                        				}
                        				else
                        				{
                        					prev->_next = cur->_next;
                        				}
                        				delete cur;
                        				return true;
                        			}
                        			prev = cur;
                        			cur = cur->_next;
                        		}
                        		return false;
                        	}
                        	iterator Find(const K& key)
                        	{
                        		Hash hf;
                        		KeyOfT kot;
                        		size_t hashi = hf(key) % _tables.size();
                        		Node* cur = _tables[hashi];
                        		while (cur)
                        		{
                        			if (kot(cur->_data) == key)
                        			{
                        				return iterator(cur, this, hashi);
                        			}
                        			cur = cur->_next;
                        		}
                        		return end();
                        	}
                        	size_t Count(const K& key)
                        	{
                        		Hash hf;
                        		KeyOfT kot;
                        		size_t hashi = hf(key) % _tables.size();
                        		Node* cur = _tables[hashi];
                        		while (cur)
                        		{
                        			if (kot(cur->_data) == key)
                        			{
                        				return 1;
                        			}
                        			cur = cur->_next;
                        		}
                        		return 0;
                        	}
                        	// 桶的总个数
                        	size_t BucketCount()
                        	{
                        		size_t bucketCount = 0;
                        		for (size_t i = 0; i _next;
                        		}
                        		return bucketSize;
                        	}
                        	// 打印信息
                        	void Some()
                        	{
                        		size_t bucketSize = 0;
                        		size_t maxBucketLen = 0;
                        		size_t sum = 0;
                        		double averageBucketLen = 0;
                        		for (size_t i = 0; i _next;
                        			}
                        			sum += bucketLen;
                        			if (bucketLen > maxBucketLen)
                        			{
                        				maxBucketLen = bucketLen;
                        			}
                        		}
                        		averageBucketLen = (double)sum / (double)bucketSize;
                        		printf("all bucketSize:%zd\n", _tables.size());
                        		printf("bucketSize:%zd\n", bucketSize);
                        		printf("maxBucketLen:%zd\n", maxBucketLen);
                        		printf("averageBucketLen:%lf\n\n", averageBucketLen);
                        	}
                        private:
                        	vector _tables;
                        	size_t _n = 0;
                        };
                        

                      4.2 unordered_map 的模拟实现

                      unordered_map 的底层结构就是哈希表，因此在 unordered_map 中直接封装一个哈希表，然后将其接口包装下即可。

                      代码实现如下：

                      #pragma once
                      #include"HashTable.h"
                      namespace my_unordered_map
                      {
                      	template
                      	class unordered_map
                      	{
                      		struct MapKeyOfT
                      		{
                      			const K& operator()(const pair& kv)
                      			{
                      				return kv.first;
                      			}
                      		};
                      	public:
                      		typedef typename hash_bucket::HashTable::iterator iterator;
                      		iterator begin()
                      		{
                      			return _ht.begin();
                      		}
                      		iterator end()
                      		{
                      			return _ht.end();
                      		}
                      		size_t size() const
                      		{
                      			return _ht.Size();
                      		}
                      		bool empty() const
                      		{
                      			return _ht.Empty();
                      		}
                      		pair insert(const pair& kv)
                      		{
                      			return _ht.Insert(kv);
                      		}
                      		bool erase(const K& key)
                      		{
                      			return _ht.Erase(key);
                      		}
                      		V& operator[](const K& key)
                      		{
                      			pair ret = _ht.Insert(make_pair(key, V()));
                      			return ret.first->second;
                      		}
                      		const V& operator[](const K& key) const
                      		{
                      			pair ret = _ht.Insert(make_pair(key, V()));
                      			return ret.first->second;
                      		}
                      		iterator find(const K& key)
                      		{
                      			return _ht.Find(key);
                      		}
                      		size_t count(const K& key)
                      		{
                      			return _ht.Count(key);
                      		}
                      		size_t bucket_count()
                      		{
                      			return _ht.BucketCount();
                      		}
                      		
                      		size_t bucket_size(const K& key)
                      		{
                      			return _ht.BucketSize(key);
                      		}
                      	private:
                      		hash_bucket::HashTable _ht;
                      	};
                      }
                      

                      4.3 unordered_set 的模拟实现

                      unordered_set 的底层结构就是哈希表，因此在 unordered_set 中直接封装一个哈希表，然后将其接口包装下即可。

                      代码实现如下：

                      #pragma once
                      #include"HashTable.h"
                      namespace my_unordered_set
                      {
                      	template
                      	class unordered_set
                      	{
                      		struct SetKeyOfT
                      		{
                      			const K& operator()(const K& key)
                      			{
                      				return key;
                      			}
                      		};
                      	public:
                      		typedef typename hash_bucket::HashTable::const_iterator iterator;
                      		typedef typename hash_bucket::HashTable::const_iterator const_iterator;
                      		iterator begin() const
                      		{
                      			return _ht.begin();
                      		}
                      		iterator end() const
                      		{
                      			return _ht.end();
                      		}
                      		size_t size() const
                      		{
                      			return _ht.Size();
                      		}
                      		bool empty() const
                      		{
                      			return _ht.Empty();
                      		}
                      		pair insert(const K& key)
                      		{
                      			auto ret = _ht.Insert(key);
                      			return pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
                      		}
                      		bool erase(const K& key)
                      		{
                      			return _ht.Erase(key);
                      		}
                      		iterator find(const K& key)
                      		{
                      			auto ret = _ht.Find(key);
                      			return const_iterator(ret._node, ret._pht, ret._hashi);
                      		}
                      		size_t count(const K& key)
                      		{
                      			return _ht.Count(key);
                      		}
                      		size_t bucket_count()
                      		{
                      			return _ht.BucketCount();
                      		}
                      		size_t bucket_size(const K& key)
                      		{
                      			return _ht.BucketSize(key);
                      		}
                      		
                      	private:
                      		hash_bucket::HashTable _ht;
                      	};
                      }
                      

                      5. 哈希的应用

                      5.1 位图

                      5.1.1 位图的概念

                      所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

                      来看一个问题：

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

                      1. 遍历 O ( N ) O(N) O(N)

                      2. 排序 O ( N l o g 2 N ) O(Nlog_2N) O(Nlog2​N) + 二分查找 O ( l o g 2 N ) O(log_2N) O(log2​N)

                      3. 位图解决

                      数据是否在给定的整型数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息。如果二进制比特位为1，则代表存在；二进制比特位为0，则代表不存在。

                      比如：

                      

                      5.1.2 位图的实现

                      namespace my_bitset
                      {
                      	// N是需要多少比特位
                      	template
                      	class bitset
                      	{
                      	public:
                      		bitset()
                      		{
                      			_bits.resize((N >> 5) + 1, 0);
                      		}
                      		void set(size_t x)
                      		{
                      			size_t i = x / 32;
                      			size_t j = x % 32;
                      			_bits[i] |= (1 
                      			size_t i = x / 32;
                      			size_t j = x % 32;
                      			_bits[i] &= ~(1 
                      			size_t i = x / 32;
                      			size_t j = x % 32;
                      			return _bits[i] & (1 
                      	size_t operator()(const string& key)
                      	{
                      		// BKDR
                      		size_t hash = 0;
                      		for (auto e : key)
                      		{
                      			hash *= 31;
                      			hash += e;
                      		}
                      		return hash;
                      	}
                      };
                      struct APHash
                      {
                      	size_t operator()(const string& key)
                      	{
                      		size_t hash = 0;
                      		for (size_t i = 0; i