[数据结构]-哈希-阿里云开发者社区

一、unordered系列关联式容

1、undordered_map

常见的接口说明

unordered_map的构造：

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

unordered_map的容量：

函数声明	功能介绍
bool empty() const	检测unordered_map是否为空
size_t size() const	获取unordered_map的有效元素个数

unordered_map的迭代器：

函数声明	功能介绍
begin	返回unordered_map第一个元素的迭代器
end	返回unordered_map最后一个元素下一个位置的迭代器
cbegin	返回unordered_map第一个元素的const迭代器
cend	返回unordered_map最后一个元素下一个位置的const迭代器

unordered_map的元素访问:

函数声明	功能介绍
operator[]	返回与key对应的value，没有一个默认值

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回

unordered_map的查询:

函数声明	功能介绍
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数

. unordered_map的修改操作 :

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

unordered_map的桶操作:

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

undordered_map最重要的功能是他的查找能力非常厉害，时间复杂度为 O(1)。

查找的运用：

这里我们将数组的元素入哈希表，然后遍历哈希表，键值对对中的value为N即是重复数

class Solution {
public:
    int repeatedNTimes(vector<int>& nums)
    {
        sort(nums.begin(),nums.end());
        int n = nums.size()/2;
        unordered_map<int,int> counMap;
        for(auto& e:nums)
        {
            counMap[e]++;
        }
        for(auto& kv:counMap)
        {
            if(kv.second==n)
            {
                return kv.first;
            }
        }
        return -1;
    }
};

2、undordered_set

undordered_set和map接口基本相同，这里不在过多介绍，下面我们将对他们的相异点进行比对：

元素类型:

unordered_map 是一种关联容器，用于存储键-值对。每个元素都是一个包含键和值的 pair。

unordered_set 是一种关联容器，用于存储唯一的元素。每个元素就是一个单独的值。

存储方式:

unordered_map 存储键-值对，每个键唯一，值可以重复。

:unordered_set 存储唯一的元素，不包含重复值。

使用方式:

unordered_map 适用于需要通过键来查找值的场景。例如，可以使用键来表示单词，值表示单词的出现次数。

unordered_set 适用于需要存储一组唯一值的场景，而不关心这些值的顺序。例如，可以使用它来存储一组唯一的单词。

接口差异：

unordered_map 提供了 operator[]，允许通过键来访问对应的值。

unordered_set 没有类似于 operator[] 的接口，因为它不是通过键来访问元素的。

迭代器:

对于 std::unordered_map，迭代器类型是一个指向 std::pair<const Key, T> 的迭代器。

对于 std::unordered_set，迭代器类型是一个指向元素值的迭代器。

unordered_ste去重的运用

这里运用了unordered_set去重

class Solution {
public:
  vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 
    // 用unordered_set对nums1中的元素去重
    unordered_set<int> s1;
    for (auto e : nums1)
      s1.insert(e);
    // 用unordered_set对nums2中的元素去重
    unordered_set<int> s2;
    for (auto e : nums2)
      s2.insert(e);
    // 遍历s1，如果s1中某个元素在s2中出现过，即为交集
    vector<int> vRet;
    for (auto e : s1)
    {
      if (s2.find(e) != s2.end())
        vRet.push_back(e);
    }
    return vRet;
  }
};

3、有序关联容器和无序关联容器

区别总结：

有序关联容器（std::map 和 std::set）适用于需要按顺序访问元素的场景，操作的时间复杂度较为稳定，但相对于无序关联容器，性能较差。

无序关联容器（std::unordered_map 和 std::unordered_set）适用于需要快速查找、插入和删除的场景，但不关心元素的顺序。性能在平均情况下很好，但在最坏情况下可能较差。

二、哈希

1、哈希概念

从前：

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

现在：

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

结构模型：

插入元素：

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

搜索元素：

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

简单的说，就是让元素的存储位置，形成一种映射，然后我们通过映射的关系很快找到该元素。

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

下面我们通过哈希函数，将我们要存放的值，通过映射关系存放。

但是如果我们继续按照上面的逻辑存放，44发生什么：

计算位置：hash(44) =44%10=4,但是4的位置，我们不是已经存放了4了，这种现象我们称为

哈希冲突：

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

2、哈希函数

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

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见的哈希函数：

直接定址法：

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

优点：简单、均匀

缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况

除留余数法：

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3、哈希冲突解决

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

3.1 闭散列

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

闭散列是通过线性探测的方法来解决哈希冲突的，那什么又是线性探测，这里我们还是以上面我们通过哈希函数重新插入44为例子：

插入：

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素

线性探测的实现模拟实现：

 
//这里是为了保证进入哈希表的数据能够正常取模
//通用
template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key;
  }
};
namespace closehash
{
  enum State
  {
    EMPTY,//空
    EXIST,//存在
    DELETE,//删除
  };
 
  template<class K, class V>
  struct HashData
  {
    pair<K, V> _kv;
    State _state = EMPTY;//默认为空
  };
 
  template<class K, class V, class Hash = HashFunc<K>>
  class HashTable
  {
    typedef HashData<K, V> Data;
  public:
    HashTable()
      :_n(0)
    {
      _tables.resize(10);//默认哈希表中开10个空间
    }
    bool Insert(const pair<K, V>& kv)
    {
      //哈希表中存在相同的数就，不在插入
      if (Find(kv.first))
        return false;
      //当负载因子大于等于0.7，为了避免哈希冲突带来更多的消耗要扩容
      if (_n * 10 / _tables.size() >= 7)
      {
        HashTable<K, V, Hash> newHT;
        newHT._tables.resize(_tables.size() * 2);
        //插入数据到新的哈希表中
        for (auto& e : _tables)
        {
          if (e._state == EXIST)
          {
            newHT.Insert(e._kv);
          }
        }
        //交换新旧表指针
        _tables.swap(newHT._tables);
      }
 
      //找映射位置，存在就向后找空位置
      Hash hf;
      size_t hashi = hf(kv.first) % _tables.size();
      //找到空位置
      while (_tables[hashi]._state == EXIST)
      {
        ++hashi;
        hashi %= _tables.size();
      }
      _tables[hashi]._kv = kv;
      _tables[hashi]._state = EXIST;
      ++_n;
      return true;
    }
    Data* Find(const K& key)
    {
      Hash hf;
      size_t hashi = hf(key) % _tables.size();
      while (_tables[hashi]._state != EMPTY)
      {
        if (_tables[hashi]._state == EXIST &&
          _tables[hashi]._kv.first == key)
        {
          return &_tables[hashi];
        }
        //不在映射位置就在没有被占用的下一个位置
        hashi++;
        //控制在数组范围内找
        hashi %= _tables.size();
      }
      //到这里就没找到
      return nullptr;
    }
    bool Erase(const K& key)
    {
      Data* ret = Find(key);
      if (ret)
      {
        ret->_state = DELETE;
        --_n;
        return true;
      }
      else
      {
        false;
      }
    }
  private:
    vector<Data> _tables;
    size_t _n = 0;//表中有效数据的个数
  };
}

测试：

对于上面的模拟实现，我们要注意一下细节：

1、负载因子是什么？

负载因子 = 填入表中的元素个数 / 闲散列的长度

负载因子的作用是衡量散列表的空间利用率。当负载因子较小时，表可能会有大量的空闲位置，而当负载因子较大时，可能导致哈希冲突的概率增加，影响性能。

对于散列表，通常有一个合适的负载因子范围，通常在 0.5 到 0.8 之间。当负载因子超过某个阈值时，可能触发重新哈希（rehashing）操作，即重新调整表的大小，并重新将元素分布到新的表中。这有助于保持较低的负载因子，提高性能。

2、闲散列扩容

哈希表在达到一定的负载因子阈值时通常会触发扩容操作

线性探测优点：实现非常简单，

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

为解决堆积问题的出现，可以进行二次探测：思想是探测相隔较远的单元，而不是和原始位置相邻的单元

3.2 开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

开散列实现：

template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key;
  }
};
namespace buckethash
{
  template<class T>
  struct HashNode
  {
    T _data;
    HashNode<T>* _next;
 
    HashNode(const T& data)
      :_data(data)
      , _next(nullptr)
    {}
  };
 
  // 前置声明
  template<class K, class T, class Hash, class KeyOfT>
  class HashTable;
  //迭代器
  template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
  struct __HTIterator
  {
    typedef HashNode<T> Node;
    typedef __HTIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
 
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    Node* _node;
    HT* _ht;
 
    //构造函数
    __HTIterator(Node* node, HT* ht)
      :_node(node)
      , _ht(ht)
    {}
 
    Ref operator*()
    {
      return _node->_data;
    }
 
    Ptr operator->()
    {
      return &_node->_data;
    }
 
    bool operator != (const Self& s) const
    {
      return _node != s._node;
    }
    //++
    Self& operator++()
    {
      if (_node->_next)
      {
        _node = _node->_next;
      }
      else
      {
        //当前桶找完了
        KeyOfT kot;
        Hash hash;
        size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
        ++hashi;
        while (hashi < _ht->_tables.size())
        {
          if (_ht->_tables[hashi])
          {
            _node = _ht->_tables[hashi];
            break;//++完成
          }
          else
          {
            ++hashi;
          }
        }
        //后面没有桶数据
        if (hashi == _ht->_tables.size())
        {
          _node = nullptr;
        }
      }
      return *this;
    }
  };
 
  //哈希表
  //K: 表示哈希表中键（Key）的类型。
  //T: 表示哈希表中值（Value）的类型。
  //Hash: 表示用于计算哈希值的哈希函数对象的类型。
  //KeyOfT: 表示一个用于从值 T 中提取键 K 的函数对象的类型。
  template<class K, class T, class Hash, class KeyOfT>
  class HashTable
  {
    typedef HashNode<T> Node;
    template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
    friend struct __HTIterator;
 
  public:
    typedef __HTIterator<K, T, T&, T*, Hash, KeyOfT> iterator;
    typedef __HTIterator<K, T, const T&, const T*, Hash, KeyOfT> const_iterator;
 
    iterator begin()
    {
      for (size_t i = 0; i < _tables.size(); i++)
      {
        if (_tables[i])
        {
          return iterator(_tables[i], this);
        }
      }
      return iterator(nullptr, this);
    }
 
    iterator end()
    {
      return iterator(nullptr, this);
    }
 
    //构造函数
    HashTable()
      :_n(0)
    {
      _tables.resize(__stl_next_prime(0));//开默认的空间
    }
 
    //析构函数
    ~HashTable()
    {
      for (int i = 0; i < _tables.size(); i++)
      {
        Node* cur = _tables[i];
        //释放桶
        while (cur)
        {
 
 
          Node* next = cur->_next;
          delete cur;
          cur = next;
        }
        _tables[i] = nullptr;
      }
    }
 
    pair<iterator, bool> Insert(const T& data)
    {
      KeyOfT kot;
      //表中有数据就不插入
      iterator it = Find(kot(data));
      if (it != end())
        return make_pair(it, false);
      // 负载因子控制在1，超过就扩容
      if (_tables.size() == _n)
      {
        vector<Node*> newTables;
        newTables.resize(__stl_next_prime(_tables.size()), nullptr);
        //给新表中插入相应的元素
        for (size_t i = 0; i < _tables.size(); i++)
        {
          Node* cur = _tables[i];
          while (cur)
          {
            Node* next = cur->_next;
            size_t hashi = Hash()(kot(cur->_data)) % newTables.size();
            //头插入到新链表
            cur->_next = newTables[hashi];
            newTables[hashi] = cur;
            cur = next;
          }
          _tables[i] = nullptr;
        }
        _tables.swap(newTables);
      }
      //插入
      size_t hashi = Hash()(kot(data)) % _tables.size();
      Node* newnode = new Node(data);
      //继续头插
      newnode->_next = _tables[hashi];
      _tables[hashi] = newnode;
      ++_n;
      return make_pair(iterator(newnode, this), true);
    }
    //查找
    iterator Find(const K& key)
    {
      KeyOfT kot;
      size_t hashi = Hash()(key) % _tables.size();
      Node* cur = _tables[hashi];
      while (cur)
      {
        if (kot(cur->_data) == key)
        {
          return iterator(cur, this);//this 指针代表当前对象（即哈希表对象）的地址
        }
        else
        {
          cur = cur->_next;
        }
      }
      return end();
    }
 
    bool Erase(const K& key)
    {
      KeyOfT kot;
      size_t hashi = Hash()(key) % _tables.size();
      Node* prev = nullptr;
      Node* cur = _tables[hashi];
      //删除
      while (cur)
      {
        if (kot(cur->_data) == key)
        {
          //删除
          if (cur == _tables[hashi])
          {
            _tables[hashi] = cur->_next;
          }
          else
          {
            prev->_next = cur->_next;
          }
          //找到删除 
          delete cur;
          --_n;
          return true;
        }
        else
        {
          prev = cur;
          cur = cur->_next;
        }
      }
      return false;
    }
    //确保哈希表的大小是一个质数，从而提高散列性能。
    inline unsigned long __stl_next_prime(unsigned long n)
    {
      static const int __stl_num_primes = 28;
      static const unsigned long __stl_prime_list[__stl_num_primes] =
      {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291
      };
 
      for (int i = 0; i < __stl_num_primes; ++i)
      {
        if (__stl_prime_list[i] > n)
        {
          return __stl_prime_list[i];
        }
      }
 
      return __stl_prime_list[__stl_num_primes - 1];
    }
  private:
    vector<Node*> _tables;//指针数组
    size_t _n;
 
  };
}

上面一连串的模拟实现，大家可能会看的有点费劲，其实的实现思路是非常简单的，就是创建一个指针数组，指针数组中放定义的哈希桶。但是实现起来细节却是非常多的，

细节问题

1、哈希表怎样进行正常的取模？

大家心里可能会想，不直接对数据进行取模不就行了，数据如果是整形进行取模，但是如果数据是字符、字符串、自定义对象呢？

这里我们就要进行复杂的hashfun进行取模值的获取

可隐式类型转换哈希函数

template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key;
  }
};

字符串哈希函数

template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        size_t hashValue = 0;
 
        for (char c : key) {
            // 加法哈希
            hashValue = (hashValue * 31) + static_cast<size_t>(c);
        }
 
        return hashValue;
    }
};

2、开散列在什么情况下进行扩容

开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

3.3 开散列与闭散列比较

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

三、哈希的应用

1、位图操作

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

我们先看一道面试题目：

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

思路：

1. 遍历，时间复杂度O(N)

2. 排序(O(NlogN))，利用二分查找: logN

3. 位图解决

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

位图的实现:

template<size_t N>
  class bitset
  {
  public:
    bitset()
    {
      //初始化位图空间
      _bits.resize((N >> 3) + 1, 0);
    }
    void set(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      _bits[i] |= (1 << j);
    }
    void reset(size_t x)
    {
      size_t i = x / 8;//x位于第几个字符
      size_t j = x % 8;//x位于第i个字符的第j位
      _bits[i] &= (~(1 << j));//1 << j 会创建一个只有第 j 位为 1 的数值
    }
    //测试
    bool test(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
 
      return _bits[i] & (1 << j);
    }
 
  private:
    vector<char> _bits;
  };

在这段代码中，使用位操作 (N >> 3)（等价于 N / 8）而不是直接的除法操作是因为这样的做法更为高效。使用位操作在某些情况下能够提高代码的执行效率，尤其是在涉及到计算机底层的位运算时。

位移操作的效率更高： 在许多计算机体系结构中，位移操作（>> 和 <<）通常比除法操作更为高效。对于2的幂次方的除法，位移操作是特别快速的。因此，将 N 右移3位（相当于除以8）可以更有效地计算出 N 除以8的结果。
代码的可读性： 通过使用位操作，可以传达一种意图，即在这里我们只关心字节的偏移，而不是简单的数学除法。这种表达方式更能突显代码的目的，即在位图中存储位信息。

那这里我们是如何将数据和位图进行映射的呢，假设输入的数据为x怎么在位图是表示？

首先我们x/8,确定该数据在那个字符位置。

然后我们x%8,确实该数据在那字符的那一位。

最后将该位置1._bits[i] |= (1 << j);

位图的应用

1.快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记

2、布隆过滤器

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？

对于去重，我们肯定会想到，用哈希表去存放，用户看过的信息，但是这样会造成大量的空间浪费，而位图又一般只能处理整形。

这时候有人就想到将哈希与位图结合，即布隆过滤器。

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

布隆过滤器插入：

布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。比如：在布隆过滤器中查找"你好"时，假设3个哈希函数计算的哈希值为：3、5、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

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

布隆过滤器优点:

1.增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

2. 哈希函数相互之间没有关系，方便硬件并行运算

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

布隆过滤器缺陷 :

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题

简单实现：

struct BKDRHash
{
  size_t operator()(const string& s)
  {
    // BKDR
    size_t value = 0;
    for (auto ch : s)
    {
      value *= 31;
      value += ch;
    }
    return value;
  }
};
struct APHash
{
  size_t operator()(const string& s)
  {
    size_t hash = 0;
    for (long i = 0; i < s.size(); i++)
    {
      if ((i & 1) == 0)
      {
        hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
      }
      else
      {
        hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
      }
    }
    return hash;
  }
};
struct DJBHash
{
  size_t operator()(const string& s)
  {
    size_t hash = 5381;
    for (auto ch : s)
    {
      hash += (hash << 5) + ch;
    }
    return hash;
  }
};
template<size_t N,
  size_t X = 5,
  class K = string,
  class HashFunc1 = BKDRHash,
  class HashFunc2 = APHash,
  class HashFunc3 = DJBHash>
class BloomFilter
{
public:
  void Set(const K& key)
  {
    size_t len = X * N;
    size_t index1 = HashFunc1()(key) % len;
    size_t index2 = HashFunc2()(key) % len;
    size_t index3 = HashFunc3()(key) % len;
    /* cout << index1 << endl;
    cout << index2 << endl;
    cout << index3 << endl<<endl;*/
    _bs.set(index1);
    _bs.set(index2);
    _bs.set(index3);
  }
  bool Test(const K& key)
  {
    size_t len = X * N;
    size_t index1 = HashFunc1()(key) % len;
    if (_bs.test(index1) == false)
      return false;
    size_t index2 = HashFunc2()(key) % len;
    if (_bs.test(index2) == false)
      return false;
    size_t index3 = HashFunc3()(key) % len;
    if (_bs.test(index3) == false)
      return false;
    return true;  // 存在误判的
  }
  // 不支持删除，删除可能会影响其他值。
  void Reset(const K& key);
private:
  bitset<X* N> _bs;
};

[数据结构]-哈希

一、unordered系列关联式容

1、undordered_map

2、undordered_set

3、有序关联容器和无序关联容器

二、哈希

1、哈希概念

2、哈希函数

3、哈希冲突解决

3.1 闭散列

3.2 开散列

3.3 开散列与闭散列比较

三、哈希的应用

1、位图操作

2、布隆过滤器

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

[数据结构]-哈希

一、unordered系列关联式容

1、undordered_map

2、undordered_set

3、 有序关联容器和无序关联容器

二、哈希

1、哈希概念

2、哈希函数

3、哈希冲突解决

3.1 闭散列

3.2 开散列

3.3 开散列与闭散列比较

三、哈希的应用

1、位图操作

2、布隆过滤器

热门文章

最新文章

相关课程

相关电子书

3、有序关联容器和无序关联容器