一文彻底搞懂哈希！

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

文章目录

    1. unordered系列关联式容器
    • 1.1 unordered_map
    • 1.2 unordered_set
    1. 哈希底层结构
    • 2.1 哈希概念
    • 2.2 哈希冲突
    • 2.3 哈希函数
    • 2.4 哈希冲突解决
      • 2.4.1 闭散列
      • 2.4.2 开散列
      • 2.4.3 开散列与闭散列比较
    1. 哈希的模拟实现
    • 3.1 模板参数列表的改造
    • 3.2 增加迭代器操作
    • 3.3 增加通过key获取value操作
    1. 哈希的应用
    • 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在线文档说明

  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. 它的迭代器至少是前向迭代器。

1.2 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为存储元素底层空间总的大小。
在这里插入图片描述
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。 但是有一个问题：如果插入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的元素，即发生哈希冲突。线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
    插入： 通过哈希函数获取待插入元素在哈希表中的位置；如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
    在这里插入图片描述
    删除： 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

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

    1. 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 开散列

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

开散列实现

  1. template<class V>
  2. struct HashBucketNode
  3. {
  5.     HashBucketNode(const V& data)
  6.         : _pNext(nullptr), _data(data)
  7.     {
  8.     }
  9.     HashBucketNode<V>* _pNext;
  10.     V _data;
  11. };
  13. template<class V>
  14. class HashBucket
  15. {
  17.     typedef HashBucketNode<V> Node;
  18.     typedef Node* PNode;
  19. public:
  20.     HashBucket(size_t capacity = 3): _size(0)
  21.     {
  22.      _ht.resize(GetNextPrime(capacity), nullptr);}
  24. // 哈希桶中的元素不能重复
  25.     PNode* Insert(const V& data)
  26.     {
  28.      // 确认是否需要扩容。。。
  29.      // _CheckCapacity();
  31.      // 1. 计算元素所在的桶号
  32.         size_t bucketNo = HashFunc(data);
  34.      // 2. 检测该元素是否在桶中
  35.         PNode pCur = _ht[bucketNo];
  36.         while(pCur)
  37.         {
  39.             if(pCur->_data == data)
  40.                 return pCur;
  42.             pCur = pCur->_pNext;
  43.         }
  44.     // 3. 插入新元素
  45.         pCur = new Node(data);
  46.         pCur->_pNext = _ht[bucketNo];
  47.         _ht[bucketNo] = pCur;
  48.         _size++;
  49.         return pCur;
  50.     }
  51.     // 删除哈希桶中为data的元素(data不会重复)，返回删除元素的下一个节点
  52.     PNode* Erase(const V& data)
  53.     {
  55.         size_t bucketNo = HashFunc(data);
  56.         PNode pCur = _ht[bucketNo];
  57.         PNode pPrev = nullptr, pRet = nullptr;
  58.     while(pCur)
  59.     {
  61.         if(pCur->_data == data)
  62.         {
  64.             if(pCur == _ht[bucketNo])
  65.                 _ht[bucketNo] = pCur->_pNext;
  66.             else
  67.                 pPrev->_pNext = pCur->_pNext;
  69.             pRet = pCur->_pNext;
  70.             delete pCur;
  71.             _size--;
  72.             return pRet;
  73.          }
  74.     }
  75.     return nullptr;
  76.  }
  78.     PNode* Find(const V& data);
  79.     size_t Size()const;
  80.     bool Empty()const;
  81.     void Clear();
  82.     bool BucketCount()const;
  83.     void Swap(HashBucket<V, HF>& ht;
  84.     ~HashBucket();
  85. private:
  86.     size_t HashFunc(const V& data)
  87.     {
  89.         return data%_ht.capacity();
  90.     }
  91. private:
  92.     vector<PNode*> _ht;
  93.     size_t _size; // 哈希表中有效元素的个数
  94. }；

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

  1. void _CheckCapacity()
  2. {
  4.     size_t bucketCount = BucketCount();
  5.     if(_size == bucketCount)
  6.     {
  8.         HashBucket<V, HF> newHt(bucketCount);
  9.     for(size_t bucketIdx = 0; bucketIdx < bucketCount; ++bucketIdx)
  10.     {
  12.         PNode pCur = _ht[bucketIdx];
  13.         while(pCur)
  14.         {
  16.             // 将该节点从原哈希表中拆出来
  17.             _ht[bucketIdx] = pCur->_pNext;
  19.             // 将该节点插入到新哈希表中
  20.             size_t bucketNo = newHt.HashFunc(pCur->_data);
  21.             pCur->_pNext = newHt._ht[bucketNo];
  22.             newHt._ht[bucketNo] = pCur;
  23.             pCur = _ht[bucketIdx];
  24.          }
  25.      }
  26.      newHt._size = _size;
  27.      this->Swap(newHt);
  28.     }
  29. }

开散列的思考

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

    // 哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法

    // 整形数据不需要转化
    template
    class DefHashF
    {

    public:

    1. size_t operator()(const T& val)
    2. {
    4.     return val;
    5. }

    };
    // key为字符串类型，需要将其转化为整形
    class Str2Int
    {

    public:

    1. size_t operator()(const string& s)
    2. {
    4.     const char* str = s.c_str();
    5.     unsigned int seed = 131; // 31 131 1313 13131 131313
    6.     unsigned int hash = 0;
    7.     while (*str)
    8.     {
    10.         hash = hash * seed + (*str++);
    11.     }
    13.     return (hash & 0x7FFFFFFF);
    14. }

    };
    // 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
    template
    class HashBucket
    {

    1. // ……

    private:

    1. size_t HashFunc(const V& data)
    2. {
    4.     return HF()(data.first)%_ht.capacity();
    5. }

    };

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

    const int PRIMECOUNT = 28;
    const size_t primeList[PRIMECOUNT] =
    {

    1. 53ul, 97ul, 193ul, 389ul, 769ul,
    2. 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    3. 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    4. 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    5. 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    6. 1610612741ul, 3221225473ul, 4294967291ul

    };
    size_t GetNextPrime(size_t prime)
    {

    1. size_t i = 0;
    2. for(; i < PRIMECOUNT; ++i)
    3. {
    5.     if(primeList[i] > primeList[i])
    6.         return primeList[i];
    7. }
    8. return primeList[i];

    }

2.4.3 开散列与闭散列比较

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

3. 哈希的模拟实现

3.1 模板参数列表的改造

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

3.2 增加迭代器操作

  1. // 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
  2. template<class K, class V, class KeyOfValue, class HF>
  3. class HashBucket;
  4. // 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
  5. template <class K, class V, class KeyOfValue, class HF>
  6. struct HBIterator
  7. {
  9.     typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
  10.     typedef HashBucketNode<V>* PNode;
  11.     typedef HBIterator<K, V, KeyOfValue, HF> Self;
  12.     HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr);
  13.     Self& operator++()
  14.     {
  16.     // 当前迭代器所指节点后还有节点时直接取其下一个节点
  17.         if (_pNode->_pNext)
  18.             _pNode = _pNode->_pNext;
  19.         else
  20.         {
  22.         // 找下一个不空的桶，返回该桶中第一个节点
  23.             size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data))+1;
  24.             for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
  25.             {
  27.                 if (_pNode = _pHt->_ht[bucketNo])
  28.                     break;
  29.             }
  30.         }
  31.         return *this;
  32.     }
  33.     Self operator++(int);
  34.     V& operator*();
  35.     V* operator->();
  36.     bool operator==(const Self& it) const;
  37.     bool operator!=(const Self& it) const;
  38.     PNode _pNode; // 当前迭代器关联的节点
  39.     HashBucket* _pHt; // 哈希桶--主要是为了找下一个空桶时候方便
  40. };

3.3 增加通过key获取value操作

  1. template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
  2. class HashBucket
  3. {
  5.     friend HBIterator<K, V, KeyOfValue, HF>;
  6.     // ......
  7. public:
  8.     typedef HBIterator<K, V, KeyOfValue, HF> Iterator;
  9.  //
  10.  // ...
  11.  // 迭代器
  12.     Iterator Begin()
  13.     {
  15.         size_t bucketNo = 0;
  16.         for (; bucketNo < _ht.capacity(); ++bucketNo)
  17.         {
  19.             if (_ht[bucketNo])
  20.                 break;
  21.         }
  22.         if (bucketNo < _ht.capacity())
  23.             return Iterator(_ht[bucketNo], this);
  24.         else
  25.             return Iterator(nullptr, this);
  26.     }
  27.     Iterator End(){
  28.      return Iterator(nullptr, this);}
  29.     Iterator Find(const K& key);
  30.     Iterator Insert(const V& data);
  31.     Iterator Erase(const K& key);
  33.     // 为key的元素在桶中的个数
  34.     size_t Count(const K& key)
  35.     {
  37.         if(Find(key) != End())
  38.             return 1;
  40.         return 0;
  41.     }
  43.     size_t BucketCount()const{
  44.      return _ht.capacity();}
  45.     size_t BucketSize(size_t bucketNo)
  46.     {
  48.         size_t count = 0;
  49.         PNode pCur = _ht[bucketNo];
  50.         while(pCur)
  51.         {
  53.             count++;
  54.             pCur = pCur->_pNext;
  55.         }
  57.         return count;
  58.     }
  59.  // ......
  60. };

4. 哈希的应用

4.1 位图

4.1.1 位图的概念

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

4.1.2 位图思想解决问题步骤

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

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

4.1.3 位图的实现

  1. class bitset
  2. {
  4. public:
  5.     bitset(size_t bitCount)
  6.         : _bit((bitCount>>5)+1), _bitCount(bitCount)
  7.     {
  8.     }
  9.     // 将which比特位置1
  10.     void set(size_t which)
  11.     {
  13.         if(which > _bitCount)
  14.             return;
  15.         size_t index = (which >> 5);
  16.         size_t pos = which % 32;
  17.         _bit[index] |= (1 << pos);
  18.     }
  19.     // 将which比特位置0
  20.     void reset(size_t which)
  21.     {
  23.         if(which > _bitCount)
  24.             return;
  25.     size_t index = (which >> 5);
  26.     size_t pos = which % 32;
  27.     _bit[index] &= ~(1<<pos);
  28.     }
  29.     // 检测位图中which是否为1
  30.     bool test(size_t which)
  31.     {
  33.         if(which > _bitCount)
  34.             return false;
  35.         size_t index = (which >> 5);
  36.         size_t pos = which % 32;
  37.         return _bit[index] & (1<<pos);
  38.     }
  39.     // 获取位图中比特位的总个数
  40.     size_t size()const{
  41.      return _bitCount;}
  42.     // 位图中比特为1的个数
  43.     size_t Count()const
  44.     {
  46.         int bitCnttable[256] = {
  48.  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,
  49.  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,
  50.  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,
  51.  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,
  52.  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,
  53.  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,
  54.  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,
  55.  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,
  56.  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,
  57.  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,
  58.  6, 7, 6, 7, 7, 8};
  60.         size_t size = _bit.size();
  61.         size_t count = 0;
  62.         for(size_t i = 0; i < size; ++i)
  63.         {
  65.             int value = _bit[i];
  66.             int j = 0;
  67.             while(j < sizeof(_bit[0]))
  68.             {
  70.                 unsigned char c = value;
  71.                 count += bitCntTable[c];
  72.                 ++j;
  73.                 value >>= 8;
  74.             }
  75.         }
  76.        return count;
  77.     }
  78. private:
  79.     vector<int> _bit;
  80.     size_t _bitCount;
  81. };

4.1.4 位图的应用

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

4.2 布隆过滤器

4.2.1 布隆过滤器概念

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

4.2.2 布隆过滤器插入

在这里插入图片描述

  1. // 假设布隆过滤器中元素类型为K，每个元素对应5个哈希函数
  2. template<class K, class KToInt1 = KeyToInt1, class KToInt2 = KeyToInt2,class KToInt3 = KeyToInt3, class KToInt4 = KeyToInt4,
  3. class KToInt5 = KeyToInt5>
  4. class BloomFilter
  5. {
  7. public:
  8.     BloomFilter(size_t size) // 布隆过滤器中元素个数
  9.         : _bmp(5*size), _size(0)
  10.     {
  11.     }
  12.     bool Insert(const K& key)
  13.     {
  15.         size_t bitCount = _bmp.Size();
  16.         size_t index1 = KToInt1()(key)%bitCount;
  17.         size_t index2 = KToInt2()(key)%bitCount;
  18.         size_t index3 = KToInt3()(key)%bitCount;
  19.         size_t index4 = KToInt4()(key)%bitCount;
  20.         size_t index5 = KToInt5()(key)%bitCount;
  21.         _bmp.Set(index1); _bmp.Set(index2);_bmp.Set(index3);
  22.         _bmp.Set(index4);_bmp.Set(index5);
  23.         _size++;
  24.     }
  25. private:
  26.     bitset _bmp;
  27.     size_t _size; // 实际元素的个数
  28. }

4.2.3 布隆过滤器查找

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

  1. bool IsInBloomFilter(const K& key)
  2. {
  4.     size_t bitCount = _bmp.Size();
  5.     size_t index1 = KToInt1()(key)%bitCount;
  6.     if(!_bmp.Test(index1))
  7.         return false;
  8.     size_t index2 = KToInt2()(key)%bitCount;
  9.     if(!_bmp.Test(index2))
  10.         return false;
  11.     size_t index3 = KToInt3()(key)%bitCount;
  12.     if(!_bmp.Test(index3))
  13.         return false;
  14.     size_t index4 = KToInt4()(key)%bitCount;
  15.     if(!_bmp.Test(index4))
  16.         return false;
  17.     size_t index5 = KToInt5()(key)%bitCount;
  18.     if(!_bmp.Test(index5))
  19.         return false;
  20.     return true; // 有可能在
  21. }

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

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. 如果采用计数方式删除，可能会存在计数回绕问题

发表评论

表情：
评论列表 （有 0 条评论，465人围观）

还没有评论，来说两句吧...

相关阅读

    相关 一文彻底搞懂引用类型

    引用类型的值（对象）是引用类型的一个实例。引用类型有时也称对象定义，因为它们描述的是一类对象所具有的属性和方法。 对象是某个特定引用类型的实例，新对象是使用new操作符后跟一

    淡淡的烟草味﹌淡淡的烟草味﹌/ 0 赞/ 151 阅读