【C++航海王：追寻罗杰的编程之路】一篇文章带你认识哈希

#define _CRT_SECURE_NO_WARNINGS 1
 
#include <iostream>
using namespace std;
 
// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State 
{ 
  EMPTY, EXIST, DELETE 
};

#define _CRT_SECURE_NO_WARNINGS 1
 
#include <iostream>
using namespace std;
 
template<class V>
struct HashBucketNode
{
  HashBucketNode(const V& data)
    : _pNext(nullptr), _data(data)
  {}
  HashBucketNode<V>* _pNext;
  V _data;
};
 
// 所实现的哈希桶中key是唯一的
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);
    }
  }

// 哈希函数采用处理余数法，被模的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();
  }
};

#pragma once
 
//HashFunc<int>
template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key;
  }
};
 
//HashFunc<string>
template<>
struct HashFunc<string>
{
  size_t operator()(const string& key)
  {
    // BKDR
    size_t hash = 0;
    for (auto e : key)
    {
      hash *= 31;
      hash += e;
    }
 
    //cout << key << ":" << hash << endl;
    return hash;
  }
};
 
namespace open_address
{
  enum Status
  {
    EMPTY,
    EXIST,
    DELETE
  };
 
  template<class K, class V>
  struct HashData
  {
    pair<K, V> _kv;
    Status _s;          //状态
  };
 
  //struct HashFuncString
  //{
  //  size_t operator()(const string& key)
  //  {
  //    // BKDR
  //    size_t hash = 0;
  //    for (auto e : key)
  //    {
  //      hash *= 31;
  //      hash += e;
  //    }
 
  //    cout << key << ":" << hash << endl;
  //    return hash;
  //  }
  //};
 
  template<class K, class V, class Hash = HashFunc<K>>
  class HashTable
  {
  public:
    HashTable()
    {
      _tables.resize(10);
    }
 
    bool Insert(const pair<K, V>& kv)
    {
      if (Find(kv.first))
        return false;
 
      // 负载因子0.7就扩容
      if (_n * 10 / _tables.size() == 7)
      {
        size_t newSize = _tables.size() * 2;
        HashTable<K, V, Hash> newHT;
        newHT._tables.resize(newSize);
 
        // 遍历旧表
        for (size_t i = 0; i < _tables.size(); i++)
        {
          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<K, V>* Find(const K& key)
    {
      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 NULL;
    }
 
    // 伪删除法
    bool Erase(const K& key)
    {
      HashData<K, V>* ret = Find(key);
      if (ret)
      {
        ret->_s = DELETE;
        --_n;
 
        return true;
      }
      else
      {
        return false;
      }
    }
 
    void Print()
    {
      for (size_t i = 0; i < _tables.size(); i++)
      {
        if (_tables[i]._s == EXIST)
        {
          //printf("[%d]->%d\n", i, _tables[i]._kv.first);
          cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
        }
        else if (_tables[i]._s == EMPTY)
        {
          printf("[%d]->\n", i);
        }
        else
        {
          printf("[%d]->D\n", i);
        }
      }
 
      cout << endl;
    }
 
  private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0; // 存储的关键字的个数
  };
 
  void TestHT1()
  {
    HashTable<int, int> ht;
    int a[] = { 4,14,24,34,5,7,1 };
    for (auto e : a)
    {
      ht.Insert(make_pair(e, e));
    }
 
    ht.Insert(make_pair(3, 3));
    ht.Insert(make_pair(3, 3));
    ht.Insert(make_pair(-3, -3));
    ht.Print();
 
    ht.Erase(3);
    ht.Print();
 
    if (ht.Find(3))
    {
      cout << "3存在" << endl;
    }
    else
    {
      cout << "3不存在" << endl;
    }
 
    ht.Insert(make_pair(3, 3));
    ht.Insert(make_pair(23, 3));
    ht.Print();
  }
 
  void TestHT2()
  {
    string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    //HashTable<string, int, HashFuncString> ht;
    HashTable<string, int> ht;
    for (auto& e : arr)
    {
      //auto ret = ht.Find(e);
      HashData<string, int>* ret = ht.Find(e);
      if (ret)
      {
        ret->_kv.second++;
      }
      else
      {
        ht.Insert(make_pair(e, 1));
      }
    }
 
    ht.Print();
 
    ht.Insert(make_pair("apple", 1));
    ht.Insert(make_pair("sort", 1));
 
    ht.Insert(make_pair("abc", 1));
    ht.Insert(make_pair("acb", 1));
    ht.Insert(make_pair("aad", 1));
 
    ht.Print();
  }
}
 
namespace hash_bucket
{
  template<class T>
  struct HashNode
  {
    HashNode<T>* _next;
    T _data;
 
    HashNode(const T& data)
      :_data(data)
      , _next(nullptr)
    {}
  };
 
  // 前置声明
  template<class K, class T, class KeyOfT, class Hash>
  class HashTable;
 
  template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
  struct __HTIterator
  {
    typedef HashNode<T> Node;
    typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
    Node* _node;
    const HashTable<K, T, KeyOfT, Hash>* _pht;
 
    // vector<Node*> * _ptb;
 
    size_t _hashi;
 
    __HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
      :_node(node)
      , _pht(pht)
      , _hashi(hashi)
    {}
 
    __HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
      :_node(node)
      , _pht(pht)
      , _hashi(hashi)
    {}
 
    Self& operator++()
    {
      if (_node->_next)
      {
        // 当前桶还有节点，走到下一个节点
        _node = _node->_next;
      }
      else
      {
        // 当前桶已经走完了，找下一个桶开始
        //KeyOfT kot;
        //Hash hf;
        //size_t hashi = hf(kot(_node->_data)) % _pht._tables.size();
        ++_hashi;
        while (_hashi < _pht->_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;
    }
  };
 
  // unordered_set -> Hashtable<K, K>
  // unordered_map -> Hashtable<K, pair<K, V>>
  template<class K, class T, class KeyOfT, class Hash>
  class HashTable
  {
    typedef HashNode<T> Node;
 
    template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
    friend struct __HTIterator;
 
  public:
    typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
    typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
 
    iterator begin()
    {
      for (size_t i = 0; i < _tables.size(); i++)
      {
        if (_tables[i])
        {
          return iterator(_tables[i], this, i);
        }
      }
 
      return end();
    }
 
    iterator end()
    {
      return iterator(nullptr, this, -1);
    }
 
    const_iterator begin() const
    {
      for (size_t i = 0; i < _tables.size(); i++)
      {
        if (_tables[i])
        {
          return const_iterator(_tables[i], this, i);
        }
      }
 
      return end();
    }
 
    // this-> const HashTable<K, T, KeyOfT, Hash>*
    const_iterator end() const
    {
      return const_iterator(nullptr, this, -1);
    }
 
    HashTable()
    {
      _tables.resize(10);
    }
 
    ~HashTable()
    {
      for (size_t 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)
    {
      Hash hf;
      KeyOfT kot;
 
      iterator it = Find(kot(data));
      if (it != end())
        return make_pair(it, false);
 
      // 负载因子最大到1
      if (_n == _tables.size())
      {
        vector<Node*> newTables;
        newTables.resize(_tables.size() * 2, nullptr);
        // 遍历旧表
        for (size_t i = 0; i < _tables.size(); i++)
        {
          Node* cur = _tables[i];
          while (cur)
          {
            Node* next = cur->_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);
    }
 
    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();
    }
 
    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;
    }
 
    void Some()
    {
      size_t bucketSize = 0;
      size_t maxBucketLen = 0;
      size_t sum = 0;
      double averageBucketLen = 0;
 
      for (size_t i = 0; i < _tables.size(); i++)
      {
        Node* cur = _tables[i];
        if (cur)
        {
          ++bucketSize;
        }
 
        size_t bucketLen = 0;
        while (cur)
        {
          ++bucketLen;
          cur = cur->_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<Node*> _tables;
    size_t _n = 0;
  };
}