Hash_Table 是哈希表的模板类，支持键（K）和值（T）的任意类型。构造函数初始化了哈希表的大小和容量，并创建了存储数据的向量 _hashT，将每个位置的状态初始化为 EMPTY。 Insert 方法用于向哈希表中插入键值对，如果键已存在则返回 false。如果哈希表的负载因子超过阈值，则进行扩容操作。扩容操作会创建一个新的哈希表 tmp，将原哈希表中的数据重新插入到新哈希表中，并将新哈希表与原哈希表交换。 Find 方法用于查找指定键的位置，返回指向该位置的指针。如果找到则返回指向该位置的指针，否则返回 nullptr。 Erase 方法用于删除指定键的键值对，将其状态标记为 DELETE，并更新哈希表的大小。

私有成员变量：

vector _hashT 存储哈希表中的数据。 _size 记录哈希表中有效数据的个数。 _capacity 记录哈希表的总容量。 _hf 记录哈希函数对象。


#define DEFAULT_CAPACITY 10
namespace close_address
{
 enum State//状态的枚举常量
 {
  EMPTY,
  EXIST,
  DELETE
 };
 
 template<class K>
 struct HashFunc
 {
  size_t operator()(const K& key)
  {
   return (size_t)key;
  }
 };
 
 template<>
 struct HashFunc<string>
 {
  size_t operator()(const string& key)
  {
   size_t ret = 0;
   for (auto x : key)
   {
    ret *= 31;
    ret += x;
   }
 
   return ret;
  }
 };
 template<class K, class T>
 struct HashData
 {
  T _data;
  State _s;
 };
 
 template<class K, class T, class HashF = HashFunc<K> >
 class Hash_Table
 {
 public:
  typedef HashData<K, T> HashData;
  Hash_Table(size_t capacity = DEFAULT_CAPACITY)
   :_size(0),
   _capacity(capacity)
  {
   _hashT.resize(capacity);
   for (size_t i = 0; i < _capacity; i++)
   {
    _hashT[i]._s = EMPTY;
   }
  }
 
  bool Insert(const T& value)
  {
   if (Find(_kot(value)))
    return false;
   if (_size * 10 / _capacity >= 7)//扩容部分
   {
    size_t newCapacity = _capacity * 2;
    _capacity = newCapacity;
 
    Hash_Table<K, T> tmp(newCapacity);
 
    for (int i = 0; i < _size; i++)
    {
     tmp.Insert(_hashT[i]._data);
    }
 
    _hashT.swap(tmp._hashT);
   }
 
   size_t hashi = _hf(_kot(value)) % _capacity;
   while (_hashT[hashi]._s == EXIST)
   {
    hashi++;
    hashi %= _capacity;
   }
 
   _hashT[hashi]._data = value;
   _hashT[hashi]._s = EXIST;
   _size++;
 
   return true;
  }
 
  HashData* Find(const K& key)
  {
   size_t hashi = _hf(key) % _capacity;
 
   while (_hashT[hashi]._s != EMPTY)
   {
    if (_hashT[hashi]._s == EXIST && _hashT[hashi]._data.first == key)
     return &(_hashT[hashi]);
 
    hashi++;
    hashi %= _capacity;
   }
 
   return nullptr;
  }
 
  bool Erase(const K& key)
  {
   HashData* pos = Find(key);
   if (pos == nullptr)
    return false;
 
   pos->_s = DELETE;
   _size--;
   return true;
  }
 
 private:
  vector<HashData> _hashT;
  size_t _size;//有效数据个数
  size_t _capacity;//哈希表的总容量
  HashF _hf;
 };
}

具体实现

成员变量 _hashT：一个HashData类型的vector，用于存储哈希表中的元素。 _size：哈希表中有效数据的个数。 _capacity：哈希表的总容量。 _hf：哈希函数对象，用于计算键的哈希值。
```
private:
   vector<HashData> _hashT;
   size_t _size;//有效数据个数
   size_t _capacity;//哈希表的总容量
   HashF _hf;
```
构造函数

构造函数接受一个可选的size_t类型的参数capacity，表示哈希表的初始容量。在构造函数中，哈希表的大小被初始化为指定的容量，并且所有桶的状态都被设置为EMPTY。


  Hash_Table(size_t capacity = DEFAULT_CAPACITY)
   :_size(0),
   _capacity(capacity)
  {
   _hashT.resize(capacity);
   for (size_t i = 0; i < _capacity; i++)
   {
    _hashT[i]._s = EMPTY;
   }
  }

插入函数Insert

首先，检查要插入的值是否已经存在于哈希表中。如果存在，返回false。接着，检查哈希表是否需要扩容。如果哈希表的负载因子（_size / _capacity）超过70%，则进行扩容。扩容操作是创建一个新的哈希表，将旧哈希表中的所有元素插入到新哈希表中，然后交换两个哈希表的_hashT成员。计算键的哈希值，并在哈希表中查找一个空的桶来存储新元素。如果找到，将新元素插入到该桶中，并更新哈希表的大小。


  bool Insert(const T& value)
   {
    if (Find(_kot(value)))
     return false;
    if (_size * 10 / _capacity >= 7)//扩容部分
    {
     size_t newCapacity = _capacity * 2;
     _capacity = newCapacity;
 
     Hash_Table<K, T> tmp(newCapacity);
 
     for (int i = 0; i < _size; i++)
     {
      tmp.Insert(_hashT[i]._data);
     }
 
     _hashT.swap(tmp._hashT);
    }
 
    size_t hashi = _hf(_kot(value)) % _capacity;
    while (_hashT[hashi]._s == EXIST)
    {
     hashi++;
     hashi %= _capacity;
    }
 
    _hashT[hashi]._data = value;
    _hashT[hashi]._s = EXIST;
    _size++;
 
    return true;
   }

查找函数Find

根据给定的键计算哈希值，并在哈希表中查找该键对应的元素。如果找到，返回指向该元素的指针；否则，返回nullptr。


  HashData* Find(const K& key)
   {
    size_t hashi = _hf(key) % _capacity;
 
    while (_hashT[hashi]._s != EMPTY)
    {
     if (_hashT[hashi]._s == EXIST && _hashT[hashi]._data.first == key)
      return &(_hashT[hashi]);
 
     hashi++;
     hashi %= _capacity;
    }
 
    return nullptr;
   }

删除函数Erase

首先，调用Find函数查找要删除的键对应的元素。如果找到，将该元素的状态设置为DELETE，并更新哈希表的大小。


    bool Erase(const K& key)
  {
   HashData* pos = Find(key);
   if (pos == nullptr)
    return false;
 
   pos->_s = DELETE;
   _size--;
   return true;
  }

链地址法的实现

模板类定义：

template<class K, class T, class KeyOfT, class HashF = HashFunc>：这是一个模板类，它有四个模板参数。 K：键的类型。 T：值的类型。 KeyOfT：用于从值中提取键的仿函数类型。 HashF：哈希函数的类型，默认为 HashFunc。

类型定义：

Node：HashNode 类型的别名，表示哈希表中的节点。 iterator 和 const_iterator：迭代器类型。

成员变量：

_ht：用于存储哈希表的桶，是一个存储指向节点的指针的 vector。 _size：当前哈希表中存储的元素个数。 _capacity：哈希表的容量，即桶的总数。 _hf：哈希函数对象，用于计算键的哈希值。 _kot：从值中提取键的仿函数对象。

成员函数：

begin()：返回一个迭代器，指向第一个非空桶中的第一个元素。 end()：返回一个迭代器，指向哈希表的末尾（超出最后一个桶的位置）。 Insert(const T& data)：向哈希表中插入一个值为 data 的元素。 Find(const K& key)：查找键为 key 的元素，并返回指向该元素的迭代器。 Erase(const K& key)：删除键为 key 的元素。析构函数 ~HashTable()：释放哈希表占用的内存。

哈希冲突处理：

使用链地址法解决冲突，即在哈希表的每个桶中使用链表来存储具有相同哈希值的元素。当哈希表的负载因子达到1时，会进行扩容操作，将桶的数量扩大为当前容量的两倍，并重新哈希所有元素到新的桶中。

内存管理：

在插入元素时，通过 new 创建新的节点，并使用链表的头插法将节点插入到相应的桶中。在删除元素时，释放被删除节点的内存。


namespace hash_bucket
{
 template<class T>
 struct HashNode
 {
  HashNode(const T& data)
   :_sizeext(nullptr),
   _data(data)
  {}
  T _data;
  HashNode* _sizeext;
 };
 
 template<class K>
 struct HashFunc
 {
  size_t operator()(const K& key)
  {
   return (size_t)key;
  }
 };
 
 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* _sizeode;
  const HashTable<K, T, KeyOfT, Hash>* _pht;
 
  size_t _hashi;
 
  __HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
   :_sizeode(node)
   , _pht(pht)
   , _hashi(hashi)
  {}
 
  __HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
   :_sizeode(node)
   , _pht(pht)
   , _hashi(hashi)
  {}
 
  Self& operator++()
  {
   if (_sizeode->_sizeext)
   {
    // 当前桶还有节点，走到下一个节点
    _sizeode = _sizeode->_sizeext;
   }
   else
   {
    // 当前桶已经走完了，找下一个桶开始
    //KeyOfT kot;
    //Hash hf;
    //size_t hashi = hf(kot(_sizeode->_data)) % _pht._capacity;
    ++_hashi;
    while (_hashi < _pht->_capacity)
    {
     if (_pht->_ht[_hashi])
     {
      _sizeode = _pht->_ht[_hashi];
      break;
     }
 
     ++_hashi;
    }
 
    if (_hashi == _pht->_capacity)
    {
     _sizeode = nullptr;
    }
   }
 
   return *this;
  }
 
  Ref operator*()
  {
   return _sizeode->_data;
  }
 
  Ptr operator->()
  {
   return &_sizeode->_data;
  }
 
  bool operator!=(const Self& s)
  {
   return _sizeode != s._sizeode;
  }
 };
 template<>
 struct HashFunc<string>
 {
  size_t operator()(const string& key)
  {
   size_t ret = 0;
   for (auto c : key)
   {
    ret *= 31;
    ret += c;
   }
   return ret;
  }
 };
 template<class K, class T, class KeyOfT, class HashF = HashFunc<K>>
 class HashTable
 {
 public:
  typedef HashNode<T> Node;//将pair改成T
  typedef __HTIterator<K, T, T&, T*, KeyOfT, HashF> iterator;
  typedef __HTIterator<K, T, const T&, const T*, KeyOfT, HashF> const_iterator;
 
  iterator begin()
  {
   for (size_t i = 0; i < _capacity; ++i)
   {
    if (_ht[i] != nullptr)
     return iterator(_ht[i], this, i);
   }
   return end();
  }
 
  iterator end()
  {
   return iterator(nullptr, this, _capacity);
  }
 
  HashTable(size_t capacity = DEFAULT_CAPACITY)
   :_size(0),
   _capacity(capacity)
  {
   _ht.resize(_capacity);
   for (int i = 0; i < _capacity; i++)
   {
    _ht[i] = nullptr;
   }
  }
 
  pair<iterator, bool> Insert(const T& data)
  {
 
   iterator it = Find(_kot(data));
   if (it != end())
    return make_pair(it, false);
 
   // 负载因子最大到1
   if (_size == _capacity)
   {
    vector<Node*> newTables;
    newTables.resize(_capacity * 2, nullptr);
    // 遍历旧表
    for (size_t i = 0; i < _capacity; i++)
    {
     Node* cur = _ht[i];
     while (cur)
     {
      Node* next = cur->next;
 
      // 挪动到映射的新表
      size_t hashi = hf(kot(cur->_data)) % newTables.size();
      cur->_sizeext = newTables[i];
      newTables[hashi] = cur;
 
      cur = next;
     }
 
     _ht[i] = nullptr;
    }
 
    _ht.swap(newTables);
   }
 
   size_t hashi = hf(kot(data)) % _capacity;
   Node* newnode = new Node(data);
 
   // 头插
   newnode->_sizeext = _ht[hashi];
   _ht[hashi] = newnode;
   ++_size;
 
   return make_pair(iterator(newnode, this, hashi), true);
  }
 
  iterator Find(const K& key)
  {
   
 
   size_t hashi = _hf(key) % _capacity;
   Node* cur = _ht[hashi];
   while (cur)
   {
    if (kot(cur->_data) == key)
    {
     return iterator(cur, this, hashi);
    }
 
    cur = cur->_sizeext;
   }
 
   return end();
  }
 
  
 
  bool Erase(const K& key)
  {
   size_t hashi = _hf(key) % _capacity;
 
   Node* cur = _ht[hashi];
   Node* preT = nullptr;
   while (cur)
   {
    if (_kot(cur->_data) == key)
    {
     if (preT == nullptr)
     {
      delete _ht[hashi];
      _ht[hashi] = nullptr;
     }
     else
     {
      preT->_sizeext = cur->_sizeext;
      delete cur;
      cur = nullptr;
     }
     return true;
    }
    preT = cur;
    cur = cur->_sizeext;
   }
   return false;
  }
  ~HashTable()
  {
   for (auto x : _ht)
   {
    Node* cur = x;
    if (cur)
    {
     while (cur)
     {
      Node* next = cur->_sizeext;
      delete cur;
      cur = next;
     }
    }
   }
  }
 private:
  vector<Node*> _ht;
  size_t _size;//有效数据个数
  size_t _capacity;//桶的总数
  HashF _hf;
  KeyOfT _kot;
 };
}

具体实现

哈希表的具体实现

begin()：

功能：返回指向哈希表中第一个非空桶的迭代器。实现：遍历哈希表，找到第一个非空桶，并返回对应迭代器；如果没有非空桶，则返回 end() 的迭代器。


iterator begin()
   {
    for (size_t i = 0; i < _capacity; ++i)
    {
     if (_ht[i] != nullptr)
      return iterator(_ht[i], this, i);
    }
    return end();
   }

end()：

功能：返回表示哈希表末尾的迭代器。实现：直接返回一个表示末尾的迭代器。


iterator end()
   {
    return iterator(nullptr, this, _capacity);
   }

HashTable(size_t capacity = DEFAULT_CAPACITY)：

功能：构造函数，初始化哈希表。参数：可选的容量参数，默认为 DEFAULT_CAPACITY。实现：根据指定容量初始化 _ht，并将每个桶置为空指针。


HashTable(size_t capacity = DEFAULT_CAPACITY)
    :_size(0),
    _capacity(capacity)
   {
    _ht.resize(_capacity);
    for (int i = 0; i < _capacity; i++)
    {
     _ht[i] = nullptr;
    }
   }

Insert(const T& data)：

功能：向哈希表中插入数据。参数：要插入的数据。返回值：返回一个 pair 对象，其中 pair.first 是指向插入数据的迭代器，pair.second 表示插入是否成功。实现：首先查找是否已存在相同键值的数据，若存在则返回失败；若哈希表容量已满，则进行扩容；然后计算插入位置的哈希值，执行头插法插入数据。


  pair<iterator, bool> Insert(const T& data)
   {
 
    iterator it = Find(_kot(data));
    if (it != end())
     return make_pair(it, false);
 
    // 负载因子最大到1
    if (_size == _capacity)
    {
     vector<Node*> newTables;
     newTables.resize(_capacity * 2, nullptr);
     // 遍历旧表
     for (size_t i = 0; i < _capacity; i++)
     {
      Node* cur = _ht[i];
      while (cur)
      {
       Node* next = cur->next;
 
       // 挪动到映射的新表
       size_t hashi = hf(kot(cur->_data)) % newTables.size();
       cur->_sizeext = newTables[i];
       newTables[hashi] = cur;
 
       cur = next;
      }
 
      _ht[i] = nullptr;
     }
 
     _ht.swap(newTables);
    }
 
    size_t hashi = hf(kot(data)) % _capacity;
    Node* newnode = new Node(data);
 
    // 头插
    newnode->_sizeext = _ht[hashi];
    _ht[hashi] = newnode;
    ++_size;
 
    return make_pair(iterator(newnode, this, hashi), true);
   }

Find(const K& key)：

功能：在哈希表中查找指定键值的数据。参数：要查找的键值。返回值：如果找到指定键值的数据，则返回对应的迭代器；否则返回末尾迭代器。实现：根据键值计算哈希值，然后在对应桶中线性查找是否存在相同键值的数据。


  iterator Find(const K& key)
   {
    
 
    size_t hashi = _hf(key) % _capacity;
    Node* cur = _ht[hashi];
    while (cur)
    {
     if (kot(cur->_data) == key)
     {
      return iterator(cur, this, hashi);
     }
 
     cur = cur->_sizeext;
    }
 
    return end();
   }

Erase(const K& key)：

功能：从哈希表中删除指定键值的数据。参数：要删除的键值。返回值：如果成功删除则返回 true，否则返回 false。实现：根据键值计算哈希值，然后在对应桶中线性查找并删除数据。


  bool Erase(const K& key)
   {
    size_t hashi = _hf(key) % _capacity;
 
    Node* cur = _ht[hashi];
    Node* preT = nullptr;
    while (cur)
    {
     if (_kot(cur->_data) == key)
     {
      if (preT == nullptr)
      {
       delete _ht[hashi];
       _ht[hashi] = nullptr;
      }
      else
      {
       preT->_sizeext = cur->_sizeext;
       delete cur;
       cur = nullptr;
      }
      return true;
     }
     preT = cur;
     cur = cur->_sizeext;
    }
    return false;
   }

~HashTable()：

功能：析构函数，释放哈希表占用的内存。实现：遍历每个桶，释放其中节点占用的内存。


  ~HashTable()
   {
    for (auto x : _ht)
    {
     Node* cur = x;
 
     while (cur)
     {
      Node* next = cur->_sizeext;
      delete cur;
      cur = next;
     }
    }
   }

迭代器的具体实现

成员类型定义：

Node：哈希表中节点的类型，HashNode 模板类的实例。 Self：迭代器自身的类型。

成员变量：

_node：指向当前节点的指针。 _pht：指向哈希表的指针。 _hashi：当前节点所在桶的索引。

构造函数：

__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)：

参数：当前节点指针、哈希表指针、当前节点所在桶的索引。实现：初始化 _node、_pht 和 _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、_pht 和 _hashi。


  __HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
    :_node(node)
    , _pht(pht)
    , _hashi(hashi)
   {}

迭代器操作：

operator++()：

功能：迭代器自增操作，将迭代器指向下一个节点。实现：首先检查当前桶是否还有节点，如果有，则将迭代器指向下一个节点；如果当前桶已经走完，则将迭代器指向下一个非空桶的第一个节点。


  Self& operator++()
   {
    if (_node->_sizeext)
    {
     // 当前桶还有节点，走到下一个节点
     _node = _node->_sizeext;
    }
    else
    {
     // 当前桶已经走完了，找下一个桶开始
     //KeyOfT kot;
     //Hash hf;
     //size_t hashi = hf(kot(_node->_data)) % _pht._capacity;
     ++_hashi;
     while (_hashi < _pht->_capacity)
     {
      if (_pht->_ht[_hashi])
      {
       _node = _pht->_ht[_hashi];
       break;
      }
 
      ++_hashi;
     }
 
     if (_hashi == _pht->_capacity)
     {
      _node = nullptr;
     }
    }
 
    return *this;
   }

operator*()：

功能：获取当前节点的引用。实现：返回当前节点的数据引用。


  Ref operator*()
   {
    return _node->_data;
   }

operator->()：

功能：获取当前节点的指针。实现：返回当前节点的数据指针。


  Ptr operator->()
   {
    return &_node->_data;
   }

operator!=()：


 bool operator!=(const Self& s)
   {
    return _node != s._node;
   }

功能：比较两个迭代器是否相等。实现：比较两个迭代器的 _node 是否相等。

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/1010593