【C++杂货铺】一文带你走进哈希：哈希冲突 | 哈希函数 | 闭散列 | 开散列

enum STATE
{
  EXIST,
  EMPTY,
  DELETE
};
//存储元素的结点
template<class K, class V>
struct HashData
{
  pair<K, V> _kv;
  STATE _state = EMPTY;
};
//哈希表
template<class K, class V>
class HashTable
{
public:
  HashTable()
  {
    _table.resize(10);
  }
  bool Insert(const pair<K, V>& kv)
  {
    //检查负载因子，扩容
    /*if ((double)_n / _table.size() >= 0.7)
    {
    }*/
    if (_n * 10 / _table.size() >= 7)
    {
      size_t newsize = _table.size() * 2;
      //重新建立映射关系
      //vector<HashData<K, V>> tmp;
      //tmp.resize(newsize);
      //for (const auto& e : _table)
      //{
      //  if (e._state == EXIST)
      //  {
      //    size_t hashi = e._kv.first % tmp.size();
      //    while (tmp[hashi]._state == EXIST)
      //    {
      //      ++hashi;
      //      //当hashi == size 的时候要让它从 0 开始继续找。
      //      /*if (hashi >= _table.size())
      //      {
      //        hashi = 0;
      //      }*/
      //      hashi %= _table.size();
      //    }
      //    tmp[hashi] = e;
      //  }
      //  
      //}
      //std::swap(tmp, _table);
      HashTable<K, V> newHT;
      newHT._table.resize(newsize);
      //遍历旧表的数据插入到新表即可
      for (size_t i = 0; i < _table.size(); ++i)
      {
        if (_table[i]._state == EXIST)
        {
          newHT.Insert(_table[i]._kv);
        }
      }
      _table.swap(newHT._table);
    }
    //线性探测
    size_t hashi = kv.first % _table.size();//注意这里
    //如果下标为hashi的地方没有存元素，那么就可以直接在hashi进行插入
    //如果下标为hashi的地方存的有元素，就需要进行线性探测
    //EMPTY、DELETE都可存储元素
    while (_table[hashi]._state == EXIST)
    {
      ++hashi;
      //当hashi == size 的时候要让它从 0 开始继续找。
      /*if (hashi >= _table.size())
      {
        hashi = 0;
      }*/
      hashi %= _table.size();
    }
    //注意方括号访问，底层会去断言，下标必须小于size，所以上面模的是size。
    _table[hashi]._kv = kv;
    _table[hashi]._state = EXIST;
    ++_n;
    return true;
  }
  HashData<const K, V>* Find(const K& key)
  {
    //线性探测
    size_t hashi = key % _table.size();//注意这里
    //如果下标为hashi的地方没有存元素，那么就可以直接在hashi进行插入
    //如果下标为hashi的地方存的有元素，就需要进行线性探测
    //EMPTY、DELETE都可存储元素
    while (_table[hashi]._state != EMPTY)
    {
      if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
      {
        return (HashData<const K, V>*)&_table[hashi];//这里会涉及类型转化，有的编译器可能不支持，所以这里最好自己强转一下
      }
      ++hashi;
      hashi %= _table.size();
    }
    return nullptr;
  }
  bool Erase(const K& key)
  {
    HashData<const K, V>* ret = Find(key);
    if (ret)
    {
      ret->_state = DELETE;
      --_n;
      return true;
    }
    return false;
  }
private:
  vector<HashData<K, V>> _table;
  size_t _n = 0;//因为数据是分散存储的，所以不能用vector中的size去计算哈希表中元素的数量，这个_n存储的就是哈希表中有效数据的个数
};

template<class K, class V>
struct HashNode
 {
   pair<K, V> _kv;
   HashNode<K, V>* _next;
   HashNode(const pair<K, V>& kv = pair<K, V>())
     :_kv(kv)
     ,_next(nullptr)
   {}
 };
 template<class K, class V, class HashFunc = DefaultHasFunc<K>>
 class HashTable
 {
   typedef HashNode<K, V> Node;
 private:
   void swap(HashTable<K, V, HashFunc>& hbt)
   {
     std::swap(hbt._table, this->_table);
     std::swap(hbt._n, this->_n);
   }
 public:
   HashTable(size_t size = 10)
   {
     _table.resize(size, nullptr);
   }
   //拷贝构造
   HashTable(const HashTable<K, V, HashFunc>& htb)
   {
     _table.resize(htb._table.size());
     for (size_t i = 0; i < htb._table.size(); ++i)
     {
       Node* cur = htb._table[i];
       while (cur)
       {
         Insert(cur->_kv);
         cur = cur->_next;
       }
     }
    /* HashTable<K, V, HashFunc> tmp;
     tmp._table = htb._table;//这里现代写法行不通，因为_table里面存的是指针，属于内置类型，进行的是浅拷贝。
     tmp._n = htb._n;
     swap(tmp);*/
   }
   bool Insert(const pair<K, V>& kv)
   {
     //HashFunc hf;
     //先检查哈希桶中是否有这个元素，有就不能插入
     if (Find(kv.first))
     {
       return false;
     }
     //不扩容，不断插入，某些桶会越来越长，效率得不到保证
     //因此还是需要进行适当的扩容
     //这里一般把负载因子控制在1
     //这样，在理想状态下，平均每个桶一个数据
     if (_n == _table.size())
     {
       //扩容 方法一：会去创建新节点，然后还要把旧结点释放，效率低下
       /*HashTable<K, V, HashFunc> newTable(_table.size() * 2);
       for (size_t i = 0; i < _table.size(); ++i)
       {
         if (_table[i] != nullptr)
         {
           Node* cur = _table[i];
           while (cur)
           {
             newTable.Insert(cur->_kv);
             cur = cur->_next;
           }
         }
       }
       _table.swap(newTable._table);*/
       //扩容 方法二：
       vector<Node*> newtable;
       newtable.resize(_table.size() * 2, nullptr);
       for (size_t i = 0; i < _table.size(); ++i)
       {
           Node* cur = _table[i];
           while (cur)
           {
             Node* next = cur->_next;
             size_t hashi = hf(cur->_kv.first) % newtable.size();
             cur->_next = newtable[hashi];
             newtable[hashi] = cur;
             cur = next;
           }
           _table[i] = nullptr;
       }
       _table.swap(newtable);
     }
     size_t hashi = hf(kv.first) % _table.size();
     //检查当前桶里面是否已经有该元素
     Node* cur = _table[hashi];
     while (cur)
     {
       if (cur->_kv.first == kv.first)
       {
         return false;
       }
       cur = cur->_next;
     }
     //到这里说明当前桶里没有该元素，可以插入
     Node* newnode = new Node(kv);
     newnode->_next = _table[hashi];
     _table[hashi] = newnode;
     ++_n;
     return true;
   }
   //打印哈希桶
   void Print()
   {
     for (size_t i = 0; i < _table.size(); ++i)
     {
       printf("Hash[%d]:", i);
       Node* cur = _table[i];
       while (cur)
       {
         cout << cur->_kv.first << ':' << cur->_kv.second <<  "--->";
         cur = cur->_next;
       }
       cout << "nullptr" << endl;
     }
   }
   //查找
   Node* Find(const K& key)
   {
     size_t hashi = hf(key) % _table.size();
     Node* cur = _table[hashi];
     while (cur)
     {
       if (cur->_kv.first == key)
       {
         return cur;
       }
       cur = cur->_next;
     }
     return nullptr;
   }
   //删除
   bool erase(const K& key)
   {
     size_t hashi = hf(key) % _table.size();
     Node* cur = _table[hashi];
     Node* prev = nullptr;
     while (cur)
     {
       if (cur->_kv.first == key)
       {
         if (prev == nullptr)
         {
           _table[hashi] = cur->_next;
         }
         else
         {
           prev->_next = cur->_next;
         }
         delete cur;
         cur = nullptr;
         --_n;
         return true;
       }
       prev = cur;
       cur = cur->_next;
     }
     return false;
   }
   ~HashTable()
   {
     for (size_t i = 0; i < _table.size(); ++i)
     {
       Node* cur = _table[i];
       while (cur)
       {
         Node* next = cur->_next;
         delete cur;
         cur = next;
       }
       _table[i] = nullptr;
     }
   }
 private:
   vector<Node*> _table;//指针数组
   //这里的_table属于自定义类型，如果我们不写析构函数，编译器会去调用vector自己的析构函数
   //对于vector的析构函数来说，Node* 是一个指针，属于内置类型
   //因此vector的析构函数不会对 Node* 做任何处理
   //因此这里我们需要自己写析构函数，去释放哈希桶中的结点
   size_t _n = 0;//记录存储的有效数据个数
   HashFunc hf;
 };

//哈希表
template<class K, class T, class KeyOfT, class HashFunc = DefaultHasFunc<K>>//K的作用是为了方便查找和删除
class HashTable

//HashTable.h
//哈希桶的迭代器
 template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
 struct HTIterator
 {
   typedef HashNode<T> Node;
   typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
   typedef HashTable<K, T, KeyOfT, HashFunc> Ht;
   typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
   Node* _node;
   const Ht* _pht;
   HTIterator(Node* node = nullptr, const Ht* pht = nullptr)
     :_node(node)
     ,_pht(pht)
   {}
   HTIterator(const iterator& it)//如果是普通迭代器，这里就是拷贝构造函数
     :_node(it._node)      //如果是 const 迭代器，这里就是用一个普通迭代器来构造一个 const 迭代器。
     , _pht(it._pht)
   {}
   Self& operator++()
   {
     if (_node->_next)
     {
       _node = _node->_next;
     }
     else
     {
       //如果_node->_next == nullptr
       //说明要到下一个桶去，因此迭代器类里面需要一个哈希表的指针，指向当前迭代器维护的哈希表
       //这样才能找到下一个桶
       //先找到我当前在那个桶
       KeyOfT kot;
       HashFunc hf;
       size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
       //从下一个位置开始查找下一个不为空的桶
       ++hashi;
       while (hashi < _pht->_table.size())
       {
         if (_pht->_table[hashi])
         {
           _node = _pht->_table[hashi];
           return *this;
         }
         else
         {
           ++hashi;
         }
       }
       _node = nullptr;
     }
     return *this;
   }
   bool operator != (const Self& s) const
   {
     return _node != s._node;
   }
   Ref operator*() const
   {
     return _node->_data;
   }
   Ptr operator->() const
   {
     return &(_node->_data);
   }
 };

//HashTable.h
//哈希表
 template<class K, class T, class KeyOfT, class HashFunc = DefaultHasFunc<K>>//K的作用是为了方便查找和删除
 class HashTable
 {
   //模板的友元
   template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
   friend struct HTIterator;
   typedef HashNode<T> Node;
 private:
   void swap(HashTable<K, T, HashFunc>& hbt)
   {
     std::swap(hbt._table, this->_table);
     std::swap(hbt._n, this->_n);
   }
 public:
   typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
   typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
   iterator begin()
   {
     //找第一个桶
     for (size_t i = 0; i < _table.size(); ++i)
     {
       if (_table[i])
       {
         return iterator(_table[i], this);
       }
     }
     return iterator(nullptr, this);
   }
   iterator end()
   {
     return iterator(nullptr, this);
   }
   const_iterator begin() const
   {
     //找第一个桶
     for (size_t i = 0; i < _table.size(); ++i)
     {
       if (_table[i])
       {
         return const_iterator(_table[i], this);
       }
     }
     return const_iterator(nullptr, this);
   }
   const_iterator end() const
   {
     return const_iterator(nullptr, this);
   }
   HashTable(size_t size = 10)
   {
     _table.resize(size, nullptr);
   }
   //拷贝构造
   HashTable(const HashTable<K, T, HashFunc>& htb)
   {
     _table.resize(htb._table.size());
     for (size_t i = 0; i < htb._table.size(); ++i)
     {
       Node* cur = htb._table[i];
       while (cur)
       {
         Insert(cur->_data);
         cur = cur->_next;
       }
     }
    /* HashTable<K, T, HashFunc> tmp;
     tmp._table = htb._table;//这里现代写法行不通，因为_table里面存的是指针，属于内置类型，进行的是浅拷贝。
     tmp._n = htb._n;
     swap(tmp);*/
   }
   pair<iterator, bool> Insert(const T& data)
   {
     HashFunc hf;
     KeyOfT kt;
     //HashFunc hf;
     //先检查哈希桶中是否有这个元素，有就不能插入
     if (Find(kt(data)) != end())
     {
       return make_pair(Find(kt(data)), false);
     }
     //扩容
     if (_n == _table.size())
     {
       vector<Node*> newtable;
       newtable.resize(_table.size() * 2, nullptr);
       for (size_t i = 0; i < _table.size(); ++i)
       {
           Node* cur = _table[i];
           while (cur)
           {
             Node* next = cur->_next;
             size_t hashi = hf(kt(cur->_data)) % newtable.size();
             cur->_next = newtable[hashi];
             newtable[hashi] = cur;
             cur = next;
           }
           _table[i] = nullptr;
       }
       _table.swap(newtable);
     }
     size_t hashi = hf(kt(data)) % _table.size();
     //到这里说明当前桶里没有该元素，可以插入
     Node* newnode = new Node(data);
     newnode->_next = _table[hashi];
     _table[hashi] = newnode;
     ++_n;
     return make_pair(iterator(newnode, this), true);
   }
   //查找
   iterator Find(const K& key)const
   {
     HashFunc hf;
     KeyOfT kt;
     size_t hashi = hf(key) % _table.size();
     Node* cur = _table[hashi];
     while (cur)
     {
       if (kt(cur->_data) == key)
       {
         return iterator(cur, this);
       }
       cur = cur->_next;
     }
     return iterator(nullptr, this);
   }
   //删除
   bool erase(const K& key)
   {
     HashFunc hf;
     KeyOfT kt;
     size_t hashi = hf(key) % _table.size();
     Node* cur = _table[hashi];
     Node* prev = nullptr;
     while (cur)
     {
       if (kt(cur->_data) == key)
       {
         if (prev == nullptr)
         {
           _table[hashi] = cur->_next;
         }
         else
         {
           prev->_next = cur->_next;
         }
         delete cur;
         cur = nullptr;
         --_n;
         return true;
       }
       prev = cur;
       cur = cur->_next;
     }
     return false;
   }
   ~HashTable()
   {
     for (size_t i = 0; i < _table.size(); ++i)
     {
       Node* cur = _table[i];
       while (cur)
       {
         Node* next = cur->_next;
         delete cur;
         cur = next;
       }
       _table[i] = nullptr;
     }
   }
 private:
   vector<Node*> _table;//指针数组
   //这里的_table属于自定义类型，如果我们不写析构函数，编译器会去调用vector自己的析构函数
   //对于vector的析构函数来说，Node* 是一个指针，属于内置类型
   //因此vector的析构函数不会对 Node* 做任何处理
   //因此这里我们需要自己写析构函数，去释放哈希桶中的结点
   size_t _n = 0;//记录存储的有效数据个数
 };

//unorderedset.h
#include "HashTable.h"
template<class K, class HashFunc = DefaultHasFunc<K>>
class unordered_set
{
private:
  struct SetKeyOfT
  {
    const K& operator()(const K& key)
    {
      return key;
    }
  };
public:
  typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator iterator;
  typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator const_iterator;
  iterator begin() const
  {
    return _ht.begin();
  }
  iterator end() const
  {
    return _ht.end();
  }
  pair<iterator, bool> insert(const K& key)
  {
    /*pair<typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator, bool> ret = _ht.Insert(key);
    return make_pair(iterator(ret.first._node, ret.first._pht), ret.second);*/
    return _ht.Insert(key);//这种写法如果编译器检查的严格可能过不了
    //上面两种插入方法都可以，这一块是精华，好好品味
  }
  K& operator[](const K& key)
  {
    pair<typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator, bool> ret = _ht.Insert(key);
    return *(ret.first);
  }
private:
  HashTable<K, K, SetKeyOfT, HashFunc> _ht;
};

template<class K, class V, class HashFunc = DefaultHasFunc<K>>
class unordered_map
{
private:
  struct MapKeyOfT
  {
    const K& operator()(const pair<K, V>& kv)
    {
      return kv.first;
    }
  };
public:
  typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::iterator iterator;
  typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::const_iterator const_iterator;
  iterator begin()
  {
    return _ht.begin();
  }
  iterator end()
  {
    return _ht.end();
  }
  const_iterator begin() const
  {
    return _ht.begin();
  }
  const_iterator end() const
  {
    return _ht.end();
  }
  pair<iterator, bool> insert(const pair<K, V>& kv)
  {
    return _ht.Insert(kv);
  }
  V& operator[](const K& key)
  {
    pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
    return ret.first->second;
  }
private:
  HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc> _ht;
};