一文彻底搞懂哈希！

迈不过友情╰ 2022-10-28 03:40 228阅读 0赞

### 文章目录 ###

*  1. unordered系列关联式容器
 *   *  1.1 unordered\_map
     *  1.2 unordered\_set
 *  2. 哈希底层结构
 *   *  2.1 哈希概念
     *  2.2 哈希冲突
     *  2.3 哈希函数
     *  2.4 哈希冲突解决
     *   *  2.4.1 闭散列
         *  2.4.2 开散列
         *  2.4.3 开散列与闭散列比较
 *  3. 哈希的模拟实现
 *   *  3.1 模板参数列表的改造
     *  3.2 增加迭代器操作
     *  3.3 增加通过key获取value操作
 *  4. 哈希的应用
 *   *  4.1 位图
     *   *  4.1.1 位图的概念
         *  4.1.2 位图思想解决问题步骤
         *  4.1.3 位图的实现
         *  4.1.4 位图的应用
     *  4.2 布隆过滤器
     *   *  4.2.1 布隆过滤器概念
         *  4.2.2 布隆过滤器插入
         *  4.2.3 布隆过滤器查找
         *  4.2.4 布隆过滤器删除
         *  4.2.5 布隆过滤器优点
         *  4.2.6 布隆过滤器缺陷

# 1. unordered系列关联式容器 #

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

## 1.1 unordered\_map ##

[unordered\_map在线文档说明][unordered_map]

1.  unordered\_map是存储<key, value>键值对的关联式容器，其允许通过key快速的索引到与其对应的value。
2.  在unordered\_map中，键值通常用于唯一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3.  在内部,unordered\_map没有对<key, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered\_map将相同哈希值的键值对放在相同的桶中。
4.  unordered\_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5.  unordered\_map实现了直接访问操作符(operator\[\])，它允许使用key作为参数直接访问value。
6.  它的迭代器至少是前向迭代器。

## 1.2 unordered\_set ##

[unordered\_set在线文档说明][unordered_set]

# 2. 哈希底层结构 #

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

## 2.1 哈希概念 ##

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

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：**插入元素**,根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放;**搜索元素**,对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。该方式即为哈希(散列)方法，**哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)**

例如：数据集合\{1，7，6，4，5，9\}；  
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]  
**用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。** 但是有一个问题：如果插入44呢，是不是和4的位置就冲突了，于是引出哈希冲突概念。

## 2.2 哈希冲突 ##

对于两个数据元素的关键字Ki和Kj (i != j)，有Ki !=Kj ,但有：Hash(Ki) == Hash(Kj)，**即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。**

## 2.3 哈希函数 ##

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

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

常见哈希函数:

1.  直接定制法  
    取关键字的某个线性函数为散列地址：Hash（Key）= A\*Key + B 优点：简单、均匀；缺点：需要事先知道关键字的分布情况；使用场景：适合查找比较小且连续的情况。
2.  除留余数法  
    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key%p(p<=m),将关键码转换成哈希地址。
3.  平方取中法  
    假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
4.  折叠法  
    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
5.  随机数法  
    选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法。
6.  数学分析法  
    设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

**注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。**

## 2.4 哈希冲突解决 ##

解决哈希冲突两种常见的方法是：闭散列和开散列

### 2.4.1 闭散列 ###

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

1.  线性探测  
    比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。**线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。**  
    **插入：** 通过哈希函数获取待插入元素在哈希表中的位置；如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]  
    **删除：** 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

// 哈希表每个空间给个标记
    // EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
    enum State{
        EMPTY, EXIST, DELETE};

**线性探测优点**：实现非常简单。  
**线性探测缺点**：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

1.  二次探测  
    线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 +i^ 2 )% m,或者：Hi = (H0 - i^2)% m。其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

**二次探测优点**：解决了线性探测中的数据堆积问题。  
**二次探测缺点**：空余位置非常少的情况下，需要进行多次探测才能找到空余位置。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。**因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。**

### 2.4.2 开散列 ###

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]  
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

**开散列实现**

template<class V>
    struct HashBucketNode
    {
        
        HashBucketNode(const V& data)
            : _pNext(nullptr), _data(data)
        {
        }
        HashBucketNode<V>* _pNext;
        V _data;
    };
    
    template<class V>
    class HashBucket
    {
        
        typedef HashBucketNode<V> Node;
        typedef Node* PNode;
    public:
        HashBucket(size_t capacity = 3): _size(0)
        {
         _ht.resize(GetNextPrime(capacity), nullptr);}
    
    // 哈希桶中的元素不能重复
        PNode* Insert(const V& data)
        {
        
         // 确认是否需要扩容。。。
         // _CheckCapacity();
    
         // 1. 计算元素所在的桶号
            size_t bucketNo = HashFunc(data);
    
         // 2. 检测该元素是否在桶中
            PNode pCur = _ht[bucketNo];
            while(pCur)
            {
        
                if(pCur->_data == data)
                    return pCur;
    
                pCur = pCur->_pNext;
            }
        // 3. 插入新元素
            pCur = new Node(data);
            pCur->_pNext = _ht[bucketNo];
            _ht[bucketNo] = pCur;
            _size++;
            return pCur;
        }
        // 删除哈希桶中为data的元素(data不会重复)，返回删除元素的下一个节点
        PNode* Erase(const V& data)
        {
        
            size_t bucketNo = HashFunc(data);
            PNode pCur = _ht[bucketNo];
            PNode pPrev = nullptr, pRet = nullptr;
        while(pCur)
        {
        
            if(pCur->_data == data)
            {
        
                if(pCur == _ht[bucketNo])
                    _ht[bucketNo] = pCur->_pNext;
                else
                    pPrev->_pNext = pCur->_pNext;
    
                pRet = pCur->_pNext;
                delete pCur;
                _size--;
                return pRet;
             }
        }
        return nullptr;
     }
    
        PNode* Find(const V& data);
        size_t Size()const;
        bool Empty()const;
        void Clear();
        bool BucketCount()const;
        void Swap(HashBucket<V, HF>& ht;
        ~HashBucket();
    private:
        size_t HashFunc(const V& data)
        {
        
            return data%_ht.capacity();
        }
    private:
        vector<PNode*> _ht;
        size_t _size; // 哈希表中有效元素的个数
    }；

**开散列增容**  
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？**开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。**

void _CheckCapacity()
    {
        
        size_t bucketCount = BucketCount();
        if(_size == bucketCount)
        {
        
            HashBucket<V, HF> newHt(bucketCount);
        for(size_t bucketIdx = 0; bucketIdx < bucketCount; ++bucketIdx)
        {
        
            PNode pCur = _ht[bucketIdx];
            while(pCur)
            {
        
                // 将该节点从原哈希表中拆出来
                _ht[bucketIdx] = pCur->_pNext;
    
                // 将该节点插入到新哈希表中
                size_t bucketNo = newHt.HashFunc(pCur->_data);
                pCur->_pNext = newHt._ht[bucketNo];
                newHt._ht[bucketNo] = pCur;
                pCur = _ht[bucketIdx];
             }
         }
         newHt._size = _size;
         this->Swap(newHt);
        }
    }

**开散列的思考**

1.  只能存储key为整形的元素，其他类型怎么解决？

// 哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法
    
    // 整形数据不需要转化
    template<class T>
    class DefHashF
    {
        
    public:
        size_t operator()(const T& val)
        {
        
            return val;
        }
    };
    // key为字符串类型，需要将其转化为整形
    class Str2Int
    {
        
    public:
        size_t operator()(const string& s)
        {
        
            const char* str = s.c_str();
            unsigned int seed = 131; // 31 131 1313 13131 131313
            unsigned int hash = 0;
            while (*str)
            {
        
                hash = hash * seed + (*str++);
            }
    
            return (hash & 0x7FFFFFFF);
        }
    };
    // 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
    template<class V, class HF>
    class HashBucket
    {
        
        // ……
    private:
        size_t HashFunc(const V& data)
        {
        
            return HF()(data.first)%_ht.capacity();
        }
    };

1.  除留余数法，最好模一个素数，如何每次快速取一个类似两倍关系的素数？

const int PRIMECOUNT = 28;
    const size_t primeList[PRIMECOUNT] =
    {
        
        53ul, 97ul, 193ul, 389ul, 769ul,
        1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
        49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
        50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
        1610612741ul, 3221225473ul, 4294967291ul
    };
    size_t GetNextPrime(size_t prime)
    {
        
        size_t i = 0;
        for(; i < PRIMECOUNT; ++i)
        {
        
            if(primeList[i] > primeList[i])
                return primeList[i];
        }
        return primeList[i];
    }

### 2.4.3 开散列与闭散列比较 ###

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于闭散列法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用开散列法反而比闭散列法节省存储空间。

# 3. 哈希的模拟实现 #

## 3.1 模板参数列表的改造 ##

// K:关键码类型
    // V: 不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是unordered_set,V为 K
    // KeyOfValue: 因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现
    // HF: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
    template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
    class HashBucket;

## 3.2 增加迭代器操作 ##

// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
    template<class K, class V, class KeyOfValue, class HF>
    class HashBucket;
    // 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
    template <class K, class V, class KeyOfValue, class HF>
    struct HBIterator
    {
        
        typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
        typedef HashBucketNode<V>* PNode;
        typedef HBIterator<K, V, KeyOfValue, HF> Self;
        HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr);
        Self& operator++()
        {
        
        // 当前迭代器所指节点后还有节点时直接取其下一个节点
            if (_pNode->_pNext)
                _pNode = _pNode->_pNext;
            else
            {
        
            // 找下一个不空的桶，返回该桶中第一个节点
                size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data))+1;
                for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
                {
        
                    if (_pNode = _pHt->_ht[bucketNo])
                        break;
                }
            }
            return *this;
        }
        Self operator++(int);
        V& operator*();
        V* operator->();
        bool operator==(const Self& it) const;
        bool operator!=(const Self& it) const;
        PNode _pNode; // 当前迭代器关联的节点
        HashBucket* _pHt; // 哈希桶--主要是为了找下一个空桶时候方便
    };

## 3.3 增加通过key获取value操作 ##

template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
    class HashBucket
    {
        
        friend HBIterator<K, V, KeyOfValue, HF>;
        // ......
    public:
        typedef HBIterator<K, V, KeyOfValue, HF> Iterator;
     //
     // ...
     // 迭代器
        Iterator Begin()
        {
        
            size_t bucketNo = 0;
            for (; bucketNo < _ht.capacity(); ++bucketNo)
            {
        
                if (_ht[bucketNo])
                    break;
            }
            if (bucketNo < _ht.capacity())
                return Iterator(_ht[bucketNo], this);
            else
                return Iterator(nullptr, this);
        }
        Iterator End(){
         return Iterator(nullptr, this);}
        Iterator Find(const K& key);
        Iterator Insert(const V& data);
        Iterator Erase(const K& key);
    
        // 为key的元素在桶中的个数
        size_t Count(const K& key)
        {
        
            if(Find(key) != End())
                return 1;
    
            return 0;
        }
    
        size_t BucketCount()const{
         return _ht.capacity();}
        size_t BucketSize(size_t bucketNo)
        {
        
            size_t count = 0;
            PNode pCur = _ht[bucketNo];
            while(pCur)
            {
        
                count++;
                pCur = pCur->_pNext;
            }
    
            return count;
        }
     // ......
    };

# 4. 哈希的应用 #

## 4.1 位图 ##

### 4.1.1 位图的概念 ###

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]  
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

### 4.1.2 位图思想解决问题步骤 ###

1.  估算大概需要多少比特位
2.  给出所有比特位，然后全部置为0
3.  将集合中的数据映射到对应的比特位上，对应比特位置为1

**data找到位图中对应比特位编号：**  
data应该在哪个字节：data/8  
data在该字节哪个比特位：data%8

### 4.1.3 位图的实现 ###

class bitset
    {
        
    public:
        bitset(size_t bitCount)
            : _bit((bitCount>>5)+1), _bitCount(bitCount)
        {
        }
        // 将which比特位置1
        void set(size_t which)
        {
        
            if(which > _bitCount)
                return;
            size_t index = (which >> 5);
            size_t pos = which % 32;
            _bit[index] |= (1 << pos);
        }
        // 将which比特位置0
        void reset(size_t which)
        {
        
            if(which > _bitCount)
                return;
        size_t index = (which >> 5);
        size_t pos = which % 32;
        _bit[index] &= ~(1<<pos);
        }
        // 检测位图中which是否为1
        bool test(size_t which)
        {
        
            if(which > _bitCount)
                return false;
            size_t index = (which >> 5);
            size_t pos = which % 32;
            return _bit[index] & (1<<pos);
        }
        // 获取位图中比特位的总个数
        size_t size()const{
         return _bitCount;}
        // 位图中比特为1的个数
        size_t Count()const
        {
        
            int bitCnttable[256] = {
        
     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
     3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
     3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
     4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
     3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
     6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
     4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
     6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
     3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
     4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
     6, 7, 6, 7, 7, 8};
    
            size_t size = _bit.size();
            size_t count = 0;
            for(size_t i = 0; i < size; ++i)
            {
        
                int value = _bit[i];
                int j = 0;
                while(j < sizeof(_bit[0]))
                {
        
                    unsigned char c = value;
                    count += bitCntTable[c];
                    ++j;
                    value >>= 8;
                }
            }
           return count;
        }
    private:
        vector<int> _bit;
        size_t _bitCount;
    };

### 4.1.4 位图的应用 ###

1.  快速查找某个数据是否在一个集合中
2.  排序
3.  求两个集合的交集、并集等
4.  操作系统中磁盘块标记

## 4.2 布隆过滤器 ##

### 4.2.1 布隆过滤器概念 ###

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

### 4.2.2 布隆过滤器插入 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 4]

// 假设布隆过滤器中元素类型为K，每个元素对应5个哈希函数
    template<class K, class KToInt1 = KeyToInt1, class KToInt2 = KeyToInt2,class KToInt3 = KeyToInt3, class KToInt4 = KeyToInt4,
    class KToInt5 = KeyToInt5>
    class BloomFilter
    {
        
    public:
        BloomFilter(size_t size) // 布隆过滤器中元素个数
            : _bmp(5*size), _size(0)
        {
        }
        bool Insert(const K& key)
        {
        
            size_t bitCount = _bmp.Size();
            size_t index1 = KToInt1()(key)%bitCount;
            size_t index2 = KToInt2()(key)%bitCount;
            size_t index3 = KToInt3()(key)%bitCount;
            size_t index4 = KToInt4()(key)%bitCount;
            size_t index5 = KToInt5()(key)%bitCount;
            _bmp.Set(index1); _bmp.Set(index2);_bmp.Set(index3);
            _bmp.Set(index4);_bmp.Set(index5);
            _size++;
        }
    private:
        bitset _bmp;
        size_t _size; // 实际元素的个数
    }

### 4.2.3 布隆过滤器查找 ###

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

bool IsInBloomFilter(const K& key)
    {
        
        size_t bitCount = _bmp.Size();
        size_t index1 = KToInt1()(key)%bitCount;
        if(!_bmp.Test(index1))
            return false;
        size_t index2 = KToInt2()(key)%bitCount;
        if(!_bmp.Test(index2))
            return false;
        size_t index3 = KToInt3()(key)%bitCount;
        if(!_bmp.Test(index3))
            return false;
        size_t index4 = KToInt4()(key)%bitCount;
        if(!_bmp.Test(index4))
            return false;
        size_t index5 = KToInt5()(key)%bitCount;
        if(!_bmp.Test(index5))
            return false;
        return true; // 有可能在
    }

**注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。**

### 4.2.4 布隆过滤器删除 ###

**布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。**  
比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1.  无法确认元素是否真正在布隆过滤器中
2.  存在计数回绕

### 4.2.5 布隆过滤器优点 ###

1.  增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2.  哈希函数相互之间没有关系，方便硬件并行运算
3.  布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4.  在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5.  数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6.  使用同一组散列函数的布隆过滤器可以进行交、并、差运算

### 4.2.6 布隆过滤器缺陷 ###

1.  有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2.  不能获取元素本身
3.  一般情况下不能从布隆过滤器中删除元素
4.  如果采用计数方式删除，可能会存在计数回绕问题

[unordered_map]: http://www.cplusplus.com/reference/unordered_map/unordered_map/?kw=unordered_map
[unordered_set]: http://www.cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: /images/20221024/b4775ee2507e45a7a0325dc38661d74e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]: /images/20221024/dc7e17e771a14789a8575e59e76360d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]: /images/20221024/a9622ed642e6434fb99f094d6bc780ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]: /images/20221024/7fd75ea1e2ae45bb9e945729464ea188.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 4]: /images/20221024/1e534b2f40de49f9abd7f11b6dfbd1c0.png