【C++】手撕哈希表的闭散列和开散列-阿里云开发者社区

> 作者：დ旧言~

> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：手撕哈希表的闭散列和开散列

> 毒鸡汤：谁不是一边受伤，一边学会坚强。

> 专栏选自：C嘎嘎进阶

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言

谈到哈希表，大家都做过这样的题目，统计字符串的字母个数，像这样的题目可以创建一个数组，每个字母采用 a['ch']++ 计入数组中，这样的数组我们称之为哈希表，这种哈希表也是最简单的，如果说为了方便直接调用哈希表，那这个哈希表该如何模拟呢？这个问题也是今天我们所探讨的，手撕哈希表。

⭐主体

学习手撕哈希表的闭散列和开散列咱们按照下面的图解：

🌙哈希概念

知识回顾

在顺序结构以及平衡树中，由于元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较；比如顺序表中需要从表头开始依次往后比对寻找，查找时间复杂度为 O(N)，平衡树中需要从第一层开始逐层往下比对寻找，查找时间复杂度为 O(logN)；即搜索的效率取决于搜索过程中元素的比较次数。

分析探讨

如果构造一种存储结构，可以通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一对一的映射关系，那么在查找时通过该函数就可以很快找到该元素；当向该结构中：

插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放；
搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

总结归纳

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

注意事项

我们上面提到的不管是顺序搜索、平衡树搜索还是哈希搜索，其 key 值都是唯一的，也就是说，搜索树中不允许出现相同 key 值的节点，哈希表中也不允许出现相同 key 值的元素，我们下文所进行的所有操作也都是在这前提之上进行的。

🌙哈希冲突

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

哈希冲突有两种常见的解决办法：

闭散列 (开放定址法)：当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；
开散列 (链地址法)：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 (哈希冲突) 归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中；也就是说，当发生哈希冲突时，把 key 直接链接在该位置的下面。

🌙哈希函数

哈希函数有如下设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值域必须在0到m-1之间；
哈希函数计算出来的地址要尽量能均匀分布在整个空间中；
哈希函数应该比较简单。

💫直接定址法

什么是直接定址法：

直接定址就是根据 key 值直接得到存储位置，最多再进行一个简单的常数之间的转换。

分析：

直接定址法的优点是简单，且不会引起哈希冲突 ，由于直接定址法的 key 值经过哈希函数转换后得到的值一定是唯一的，所以不存在哈希冲突。
直接定址法适用于数据范围集中的情况，这样 key 值映射到哈希表后，哈希表的空间利用率高，浪费的空间较少

图解：

💫除留余数法

什么是除留余数法：

简单来说就是用 key 值除以哈希表的大小得到的余数作为哈希映射的地址，将 key 保存到该地址中

分析：

除留余数的优点是可以处理数据范围分散的数据
缺点是会引发哈希冲突

图解：

💫方法总结

直接定制法–(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况

除留余数法–(常用)

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

平方取中法–(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

折叠法–(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

随机数法–(了解)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

数学分析法–(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址

🌙闭散列哈希

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；那如何寻找下一个空位置呢？有两种方法 – 线性探测法和二次探测法。

💫线性探测法

什么是线性探测：

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

图解：

💫哈希表的基本框架

框架搭建步骤：

在哈希表中我们使用了 vector 来存储数据，并增加了一个变量 n 来记录表中有效数据的个数；同时，哈希表的每个下标位置存储的数据都是一个 KV 模型的键值对
当key映射的下标位置被占用时，key会向后寻找下一个空位置进行插入，但如果key走到数组尾都还没找到空位置，那么key就会从数组起始位置重新往后寻找
在哈希表的每个位置的数据中还增加了一个 state 变量来记录该位置的状态 (存在、删除、空)

代码如下：

//标识每个存储位置的状态--空、存在与删除
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 HashTable {
  typedef HashData<K, V> Data;
private:
  vector<Data> _tables;
  size_t _n;  //记录表中有效数据的个数
};

💫哈希表的插入删除与查找

插入：

通过哈希函数得到余数即数组下标，如果该下标的状态为删除或为空则插入，如果为存在则向后寻找下一个状态为删除/空的位置进行插入。

查找：

通过哈希函数得到余数即数组下标，取出小标位置的key与目标key进行比较，相等就返回该位置的地址，不相等就继续往后查找，如果查找到状态为空的下标位置就返回 nullptr。

删除：

复用查找函数，查找到就通过查找函数的返回值将小标位置数据的状态置为删除，找不到就返回 false。

代码实现：

#pragma once
 
#include <vector>
#include <utility>
using std::pair;
using std::vector;
 
//标识每个存储位置的状态--空、存在与删除
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 HashTable {
  typedef HashData<K, V> Data;
 
public:
  HashTable()
    : _n(0)
  {
    //将哈希表的大小默认给为10
    _tables.resize(10);
  }
 
  bool insert(const pair<K, V>& kv) {
    if (find(kv.first))
      return false;
 
    //除留余数法 && 线性探测法
    //将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
    size_t hashi = kv.first % _tables.size();
    //不能放在EXIST的位置，DELETE和EMPTY都能放
    while (_tables[hashi]._state == EXIST) {
      ++hashi;
      if (hashi == _tables.size()) hashi = 0;  //如果探测到末尾则从头开始重新探测
    }
 
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
 
    return true;
  }
 
    //将find的返回值定义为Data的地址，可以方便我们进行删除以及修改V
    Data* find(const K& key) {
      Hash hash;  //仿函数对象
      size_t hashi = hash(key) % _tables.size();
      //记录hashi的起始位置，避免哈希表中元素全为EXIST和DELETE时导致死循环
      size_t starti = hashi;
      //最多找到空
      while (_tables[hashi]._state != EMPTY) {
        //key相等并且state为EXIST才表示找到
        if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
          return &_tables[hashi];
        ++hashi;
        //如果找到尾还没找到，就从0重新找
        if (hashi == _tables.size()) hashi = 0;
        //如果找一圈还没找到，就跳出循环
        if (hashi == starti) break;
      }
 
      return nullptr;
    }
 
  bool erase(const K& key) {
    //找不到就不删，找到就把状态置为DELETE即可
    Data* ret = find(key);
    if (ret) {
      ret->_state = DELETE;
      return true;
    }
 
    return false;
  }
 
private:
  vector<Data> _tables;
  size_t _n;  //记录表中有效数据的个数
};

💫哈希表的扩容

哈希表的扩容和普通顺序表容器的扩容不同，它不是容器满了才扩容，而是会有一个负载因子，也叫载荷因子，当载荷因子超过一定大小时就立即扩容。

代码如下：

bool insert(const pair<K, V>& kv) {
    if (find(kv.first))
        return false;
 
    //如果大于标定的载荷因子就扩容，这里我们将载荷因子标定为0.7
    //扩容现代写法--复用insert接口
    if ((1.0 * _n / _tables.size()) >= 0.7) {
        HashTable<K, V> newHT;
        newHT._tables.resize(_tables.size() * 2);
 
        for (auto& e : _tables)
            newHT.insert(e._kv);
 
        _tables.swap(newHT._tables);
    }
 
    //除留余数法 && 线性探测法
    //将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
    size_t hashi = kv.first % _tables.size();
    //不能放在EXIST的位置，DELETE和EMPTY都能放
    while (_tables[hashi]._state == EXIST) {
        ++hashi;
        if (hashi == _tables.size()) hashi = 0;  //如果探测到末尾则从头开始重新探测
    }
 
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
 
    return true;
}

💫哈希表的仿函数

模板参数是一个仿函数，仿函数分为设计者提供的默认仿函数和用户提供的仿函数，系统默认的仿函数可以将一些常见的 key 的类型全部转化为整形，比如字符串、指针、整数；而用户提供的仿函数则可以根据用户自己的 key 类型将其转化为整形，比如 People 类 (身份证号)、Date 类等等

代码如下：

template<>
struct HashFunc<string> {
  size_t operator()(const string& key) {
    size_t sum = 0;
    for (auto ch : key)
      sum += ch;
 
    return sum;
  }
};

细节分析：

有了仿函数，解决了传字符串的问题

💫闭散列整体代码实现

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;
 
// 哈希表的仿函数 ，通过上层容器提供的仿函数获取到元素的键值
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 hash = 0;
    for (auto e : key)
    {
      hash += e;
      hash *= 131;
    }
 
    return hash;
  }
};
 
// 闭散列哈希表
namespace open_address
{
  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
  {
  public:
 
    // 默认开辟 10 个空间
    HashTable(size_t size = 10)
    {
      _tables.resize(size);
    }
 
    // 查找
    HashData<K, V>* Find(const K& key)
    {
      // 仿函数对象
      Hash hs;
      // 线性探测
      size_t hashi = hs(key) % _tables.size();
      while (_tables[hashi]._state != EMPTY)
      {
        // key相等并且state为EXIST（存在）才能表示找到
        if (key == _tables[hashi]._kv.first
          && _tables[hashi]._state == EXIST)
        {
          return &_tables[hashi];
        }
 
        ++hashi;
        hashi %= _tables.size();
      }
 
      return nullptr;
    }
 
    // 插入
    bool Insert(const pair<K, V>& kv)
    {
      // 为空就返回
      if (Find(kv.first))
        return false;
 
      // 扩容
      if (_n * 10 / _tables.size() >= 7)
      {
        // 扩容
        HashTable<K, V, Hash> newHT(_tables.size() * 2);
        // 遍历旧表，插入到新表
        for (auto& e : _tables)
        {
          if (e._state == EXIST)
          {
            newHT.Insert(e._kv);
          }
        }
        // 交换
        _tables.swap(newHT._tables);
      }
 
      // 仿函数对象
      Hash hs;
      // 线性探测，找需要插入的地方
      size_t hashi = hs(kv.first) % _tables.size();
      while (_tables[hashi]._state == EXIST)
      {
        ++hashi;
        hashi %= _tables.size();
      }
 
      _tables[hashi]._kv = kv;
      _tables[hashi]._state = EXIST;
      ++_n;
 
      return true;
    }
 
    // 删除
    bool Erase(const K& key)
    {
      // 查找
      HashData<K, V>* ret = Find(key);
      if (ret)
      {
        _n--; // 元素减一
        ret->_state = DELETE;// 状态改为删除
        return true;
      }
      else
      {
        return false;
      }
    }
 
  private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0;  // 实际存储的数据个数
  };
 
  // 测试一
  void TestHT1()
  {
    int a[] = { 1,4,24,34,7,44,17,37 };
    
    // 创建哈希表
    HashTable<int, int> ht;
    for (auto e : a)
    {
      ht.Insert(make_pair(e, e)); // 插入元素
    }
 
    for (auto e : a)
    {
      auto ret = ht.Find(e);
      if (ret)
      {
        cout << ret->_kv.first << ":E" << endl;
      }
      else
      {
        cout << ret->_kv.first << ":D" << endl;
      }
    }
    cout << endl;
 
    ht.Erase(34);
    ht.Erase(4);
 
    for (auto e : a)
    {
      auto ret = ht.Find(e);
      if (ret)
      {
        cout << ret->_kv.first << ":E" << endl;
      }
      else
      {
        cout << e << ":D" << endl;
      }
    }
    cout << endl;
  }
 
  // 测试二
  struct Date
  {
    int _year;
    int _month;
    int _day;
  };
  struct HashFuncDate
  {
    // 2024/6/3
    // 2024/3/6
    size_t operator()(const Date& d)
    {
      size_t hash = 0;
      hash += d._year;
      hash *= 131;
 
      hash += d._month;
      hash *= 131;
 
      hash += d._day;
      hash *= 131;
 
      return hash;
    }
  };
  void TestHT2()
  {
    HashTable<string, string> dict;
    dict.Insert(make_pair("sort", "排序"));
    dict.Insert(make_pair("string", "字符串"));
    HashTable<Date, string, HashFuncDate> DateHash;
  }
 
}

🌙开散列哈希

什么是开散列哈希：

开散列法又叫链地址法 (开链法)，首先对关键码集合用散列函数计算散列地址，即 key 映射的下标位置，具有相同地址的关键码 (哈希冲突) 归于同一子集合，每一个子集合称为一个桶 (哈希桶)，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中；也就是说，当发生哈希冲突时，把 key 作为一个节点直接链接到下标位置的哈希桶中。

图解：

💫开散列的节点结构

由于开散列的不同冲突之间不会互相影响，所以开散列不再需要 state 变量来记录每个下表位置的状态；同时，因为开散列每个下标位置链接的都是一个哈希桶，所以 vector 中的每个元素都是一个节点的指针，指向单链表的第一个元素，所以 _tables 是一个指针数组；最后，为了是不同类型的 key 都能够计算出映射的下标位置，所以我们这里也需要传递仿函数。

代码如下：

//开散列
namespace hash_bucket {
  //哈希表的节点结构--单链表
  template<class K, class V>
  struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* next;
 
    HashNode(const pair<K, V>& kv)
      : _kv(kv)
      , next(nullptr)
    {}
  };
 
  //哈希表的仿函数
  template<class K>
  struct HashFunc {
    size_t operator()(const K& key) {
      return key;
    }
  };
 
  //类模板特化
  template<>
  struct HashFunc<string> {
    size_t operator()(const string& key) {
      //BKDR字符串哈希算法
      size_t sum = 0;
      for (auto ch : key)
        sum = sum * 131 + ch;
 
      return sum;
    }
  };
 
  //哈希表
  template<class K, class V, class Hash = HashFunc<K>>
  class HashTable {
    typedef HashNode<K, V> Node;
          private:
    vector<Node*> _tables;  //指针数组
    size_t _n;  //表中有效数据的个数
  };
}

💫开散列的插入删除与查找

开散列的插入

开散列插入的前部分和闭散列一样，根据 key 与哈希表大小得到映射的下标位置，与闭散列不同的是，由于哈希表中每个下标位置都是一个哈希桶，即一个单链表，那么对于发现哈希冲突的元素我们只需要将其链接到哈希桶中即可，这里显然是选择将冲突元素进行头插，因为尾插还需要找尾，会导致效率降低：

// 插入函数
bool Insert(const pair<K, V>& kv)
{
  // 查看元素是否存在
  if (Find(kv.first))
    return false;
 
  // 仿函数对象
  Hash hs;
 
  // 负载因子到1就扩容
  if (_n == _tables.size())
  {
    // 扩容
    vector<Node*> newTables(_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 = hs(cur->_kv.first) % newTables.size();
        cur->_next = newTables[hashi];
        newTables[hashi] = cur;
 
        cur = next;
      }
 
      _tables[i] = nullptr;
    }
 
    _tables.swap(newTables);
  }
      
  // 调用仿函数的匿名对象来将key转换为整数
  size_t hashi = hs(kv.first) % _tables.size();
      
  // 头插
  Node* newnode = new Node(kv);
  newnode->_next = _tables[hashi];
  _tables[hashi] = newnode;
 
  ++_n;
  return true;
}

开散列的查找

开散列的查找也很简单，根据余数找到下标，由于下标位置存储的是链表首元素地址，所以我们只需要取出首元素地址，然后顺序遍历单链表即可：

// 查找
Node* Find(const K& key)
{
  // 仿函数对象
  Hash hs;
  size_t hashi = hs(key) % _tables.size();
  Node* cur = _tables[hashi];
  while (cur)
  {
    if (cur->_kv.first == key)
    {
      return cur;
    }
 
    cur = cur->_next;
  }
 
  return nullptr;
}

开散列的删除

和闭散列不同的是，开散列的删除不能直接通过查找函数的返回值来进行删除，因为单链表在删除节点时还需要改变父节点的指向，让其指向目标节点的下一个节点，所以我们需要通过遍历单链表来进行删除：

// 删除
bool Erase(const K& key)
{
  // 仿函数对象
  Hash hs;
  size_t hashi = hs(key) % _tables.size();
  Node* prev = nullptr;
  Node* cur = _tables[hashi];
  while (cur)
  {
    // 删除还要分是否为头节点
    if (cur->_kv.first == key)
    {
      // 删除
      if (prev)
      {
        prev->_next = cur->_next;
      }
      else
      {
        _tables[hashi] = cur->_next;
      }
 
      delete cur;
 
      --_n;
      return true;
    }
 
    // 下一个结点
    prev = cur;
    cur = cur->_next;
  }
 
  return false;
}

💫开散列整体代码实现

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;
 
// 哈希表的仿函数 ，通过上层容器提供的仿函数获取到元素的键值
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 hash = 0;
    for (auto e : key)
    {
      hash += e;
      hash *= 131;
    }
 
    return hash;
  }
};
 
// 开散列哈希表
namespace hash_bucket
{
  // 哈希表的节点结构 -- 单链表
  template<class K, class V>
  struct HashNode
  {
    HashNode<K, V>* _next;
    pair<K, V> _kv;
 
    // 初始化列表
    HashNode(const pair<K, V>& kv)
      :_next(nullptr)
      , _kv(kv)
    {}
  };
 
  // 哈希表
  template<class K, class V, class Hash = HashFunc<K>>
  class HashTable
  {
    typedef HashNode<K, V> Node;
  public:
 
    // 构造函数
    HashTable()
    {
      _tables.resize(10, nullptr); // 开空间
      _n = 0;
    }
 
    // 析构函数
    ~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;
      }
    }
 
    // 插入函数
    bool Insert(const pair<K, V>& kv)
    {
      // 查看元素是否存在
      if (Find(kv.first))
        return false;
 
      // 仿函数对象
      Hash hs;
 
      // 负载因子到1就扩容
      if (_n == _tables.size())
      {
        // 扩容
        vector<Node*> newTables(_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 = hs(cur->_kv.first) % newTables.size();
            cur->_next = newTables[hashi];
            newTables[hashi] = cur;
 
            cur = next;
          }
 
          _tables[i] = nullptr;
        }
 
        _tables.swap(newTables);
      }
 
      // 调用仿函数的匿名对象来将key转换为整数
      size_t hashi = hs(kv.first) % _tables.size();
 
      // 头插
      Node* newnode = new Node(kv);
      newnode->_next = _tables[hashi];
      _tables[hashi] = newnode;
 
      ++_n;
      return true;
    }
 
    // 查找
    Node* Find(const K& key)
    {
      // 仿函数对象
      Hash hs;
      size_t hashi = hs(key) % _tables.size();
      Node* cur = _tables[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          return cur;
        }
 
        cur = cur->_next;
      }
 
      return nullptr;
    }
 
    // 删除
    bool Erase(const K& key)
    {
      // 仿函数对象
      Hash hs;
      size_t hashi = hs(key) % _tables.size();
      Node* prev = nullptr;
      Node* cur = _tables[hashi];
      while (cur)
      {
        // 删除还要分是否为头节点
        if (cur->_kv.first == key)
        {
          // 删除
          if (prev)
          {
            prev->_next = cur->_next;
          }
          else
          {
            _tables[hashi] = cur->_next;
          }
 
          delete cur;
 
          --_n;
          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("load factor:%lf\n", (double)_n / _tables.size());
      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; // 元素个数
  };
 
  // 测试一
  void TestHT1()
  {
    HashTable<int, int> ht;
    int a[] = { 1,4,24,34,7,44,17,37 };
    for (auto e : a)
    {
      ht.Insert(make_pair(e, e));
    }
 
    ht.Insert(make_pair(5, 5));
    ht.Insert(make_pair(15, 15));
    ht.Insert(make_pair(25, 25));
 
    ht.Erase(5);
    ht.Erase(15);
    ht.Erase(25);
    ht.Erase(35);
 
    for (auto e : a)
    {
      auto ret = ht.Find(e);
      if (ret)
      {
        cout << ret->_kv.first << ":E" << endl;
      }
      else
      {
        cout << ret->_kv.first << ":D" << endl;
      }
    }
    cout << endl;
 
    HashTable<string, string> dict;
    dict.Insert(make_pair("sort", "排序"));
    dict.Insert(make_pair("string", "字符串"));
  }
 
  // 测试二
  void TestHT2()
  {
    const size_t N = 30000;
 
    unordered_set<int> us;
    set<int> s;
    HashTable<int, int> ht;
 
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; ++i)
    {
      //v.push_back(rand()); // N比较大时，重复值比较多
      v.push_back(rand() + i); // 重复值相对少
      //v.push_back(i); // 没有重复，有序
    }
 
    size_t begin1 = clock();
    for (auto e : v)
    {
      s.insert(e);
    }
    size_t end1 = clock();
    cout << "set insert:" << end1 - begin1 << endl;
 
    size_t begin2 = clock();
    for (auto e : v)
    {
      us.insert(e);
    }
    size_t end2 = clock();
    cout << "unordered_set insert:" << end2 - begin2 << endl;
 
    size_t begin10 = clock();
    for (auto e : v)
    {
      ht.Insert(make_pair(e, e));
    }
    size_t end10 = clock();
    cout << "HashTbale insert:" << end10 - begin10 << endl << endl;
 
    size_t begin3 = clock();
    for (auto e : v)
    {
      s.find(e);
    }
    size_t end3 = clock();
    cout << "set find:" << end3 - begin3 << endl;
 
    size_t begin4 = clock();
    for (auto e : v)
    {
      us.find(e);
    }
    size_t end4 = clock();
    cout << "unordered_set find:" << end4 - begin4 << endl;
 
    size_t begin11 = clock();
    for (auto e : v)
    {
      ht.Find(e);
    }
    size_t end11 = clock();
    cout << "HashTable find:" << end11 - begin11 << endl << endl;
 
    cout << "插入数据个数：" << us.size() << endl << endl;
    ht.Some();
 
    size_t begin5 = clock();
    for (auto e : v)
    {
      s.erase(e);
    }
    size_t end5 = clock();
    cout << "set erase:" << end5 - begin5 << endl;
 
    size_t begin6 = clock();
    for (auto e : v)
    {
      us.erase(e);
    }
    size_t end6 = clock();
    cout << "unordered_set erase:" << end6 - begin6 << endl;
 
    size_t begin12 = clock();
    for (auto e : v)
    {
      ht.Erase(e);
    }
    size_t end12 = clock();
    cout << "HashTable Erase:" << end12 - begin12 << endl << endl;
  }
}

🌟结束语

今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

【C++】手撕哈希表的闭散列和开散列

🌟前言

⭐主体

🌙哈希概念

🌙哈希冲突

🌙哈希函数

💫直接定址法

💫除留余数法

💫方法总结

🌙闭散列哈希

💫线性探测法

💫哈希表的基本框架

💫哈希表的插入删除与查找

💫哈希表的扩容

💫哈希表的仿函数

💫闭散列整体代码实现

🌙开散列哈希

💫开散列的节点结构

💫开散列的插入删除与查找

💫开散列整体代码实现

🌟结束语

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++】手撕哈希表的闭散列和开散列

🌟前言

⭐主体

🌙哈希概念

🌙哈希冲突

🌙哈希函数

💫直接定址法

💫除留余数法

💫方法总结

🌙闭散列哈希

💫线性探测法

💫哈希表的基本框架

💫哈希表的插入删除与查找

💫哈希表的扩容

💫哈希表的仿函数

💫闭散列整体代码实现

🌙开散列哈希

💫开散列的节点结构

💫开散列的插入删除与查找

💫开散列整体代码实现

🌟结束语

热门文章

最新文章

相关课程

相关电子书