一、整体结构

实现方式	命名空间	核心思想
开放定址法（闭散列）	open_adress	冲突时在数组中找空位
拉链法（开散列）	hash_bucket	每个桶是一个链表

---

二、闭散列（开放定址法）

• 所有元素存储在一个数组中

• 发生冲突 → 线性探测

• 删除使用 标记删除（DELETE）

状态设计

enum STATE
{
    EXIST,
    EMPTY,
    DELETE
};

为什么需要 DELETE？

• 如果直接删除，会影响查找路径

• DELETE 表示“曾经有数据，但现在删了”

数据结构

template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    STATE _state = EMPTY;
};

插入流程

size_t hash = hf(kv.first) % _table.size();
​
while (_table[hash]._state == EXIST)
{
    ++hash;
    hash %= _table.size();
}

• 使用 线性探测

• 遇到 EXIST 才继续走

• DELETE 可以复用

扩容机制

if ((double)_n / _table.size() >= 0.7)

负载因子控制在 0.7

扩容方式：

• 创建新表

• 重新插入（rehash） ：将旧表重新插入新表中

查找

while (_table[hash]._state != EMPTY)

• 遇到 EMPTY 才能停止

• DELETE 不能停止（因为可能后面有数据）

---

三、开散列（拉链法）

• 每个桶是一个链表

• 冲突 → 挂链表

节点结构

template<class K, class V>
struct HashNode
{
    pair<K, V> _kv;
    HashNode<K, V>* _next;
};

插入（头插法）

size_t hash = hf(kot(data)) % _table.size();
​
Node* newnode = new Node(kv);
newnode->_next = _table[hash];
_table[hash] = newnode;

扩容

if (_n == _table.size())

负载因子 = 1 时扩容

扩容过程：

• 遍历所有链表

• 重新计算 hash

• 挂到新桶

  if (_n == _table.size())
  {
      //size_t newSize = _table.size() * 2;
      size_t newSize = GetNextPrime(_table.size());
      vector<Node*> newTable;
      newTable.resize(newSize, nullptr);
  ​
      // 遍历旧表，顺手牵羊，把节点牵下来挂到新表
      for (size_t i = 0; i < _table.size(); i++)
      {
          Node* cur = _table[i];
          while (cur)
          {
              Node* next = cur->_next;
  ​
              // 头插到新表
              size_t hashi = hf(kot(cur->_data)) % newSize;
              cur->_next = newTable[hashi];
              newTable[hashi] = cur;
  ​
              cur = next;
          }
  ​
          _table[i] = nullptr;
      }
  ​
      _table.swap(newTable);
  }

查找

Node* cur = _table[hash];
while (cur)
{
    if (kot(cur->_data) == key)
        return cur;
​
    cur = cur->_next;
}

四、仿函数（HashFunc）

默认哈希函数

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

• 重载 operator()的类对象

• 让对象像函数一样调用

string 特化

template<>
struct DefaultHashFunc<string>
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (auto ch : str)
        {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

采用了BKDR 哈希：

hash = hash * 131 + ch

为什么用仿函数？

1.支持泛型

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
HashFunc hf;
hf(key);

HashTable 不关心 K 怎么 hash，直接交给HashFunc处理

2.可扩展

用户可以自定义：

struct MyHash
{
    size_t operator()(const MyType& t)
    {
        ...
    }
};

五、KeyOfT（提取 key）

KeyOfT 是一个仿函数，用于从存储的数据 T 中提取出 key。

在泛型哈希表设计中，存储的数据类型 T 不一定是 key 本身，比如 map 存的是 pair<K,V>，而 set 存的是 K。如果直接在哈希表内部写死 key 的获取方式，就会导致代码无法复用。

因此引入 KeyOfT，将“如何从数据中提取 key”这一逻辑抽象出来，实现数据结构与数据内容的解耦。

这样同一套 HashTable 可以通过不同的 KeyOfT 支持 map 和 set，体现了策略模式的思想，提高了代码的通用性和扩展性。

struct KeyOfT
{
    const K& operator()(const T& data)
    {
        // 从 data 中提取 key
    }
};

为什么需要 KeyOfT？

因为：

template<class K, class T>

这里 T 不一定是 pair<K, V>

例如：

容器	T	K
map	pair<K,V>	K
set	K	K

使用方式

KeyOfT kot;
HashFunc hf;
​
size_t hash = hf(kot(data)) % _table.size();

data → kot(data) → key → hf(key) → hash值

map 的 KeyOfT

template<class K, class V>
struct MapKeyOfT
{
    const K& operator()(const pair<K, V>& kv)
    {
        return kv.first;
    }
};

---

set 的 KeyOfT

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

六、封装

模板解耦

template<class K, class T, class KeyOfT, class HashFunc>

参数	作用
K	key类型
T	存储数据
KeyOfT	如何取key
HashFunc	如何hash

---

行为可插拔

用户可以自定义：

• hash函数

• key提取方式

---

复用性

同一套 HashTable 可以支持：

• map

• set

• unordered_map

• unordered_set