C++ 哈希表原理与冲突解决策略

设置 _kv 存储实际的键值对数据，_state 跟踪该位置的状态。

• EXIST 表示位置已被占用（存在有效元素）
• EMPTY 表示位置为空（从未被使用）
• DELETE 表示位置已删除（曾被占用，现已删除）

为什么要用状态来表示呢？ 因为用状态表示是最清晰直接的。有人说用零来表示已经删除的值不就好了，但是万一本身存储的值就是零呢？总而言之用状态表示是最方便的。

4.1.1.2 哈希表的 key 转换

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

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

除留余数法一般是对整数进行操作，但是我们并不能保证 key 一定是整数。直接强转可能不准确，可能是 double，也有可能是 string。因此最好的方法是利用仿函数进行统一操作。 整数小数等就走默认的 DefaultHashFunc 类，当 key 是 string 类型的时候，就走特化的版本 DefaultHashFunc<string>，这里特化是为了统一性。

template<class K, class V, class HashFunc = DefaultHashFunc<K>>

将仿函数设为默认类型，这样子在创建例如 HashTable<string, string> dict 的哈希表的时候就不用显式写仿函数的类型。

值得注意的是：这里的 string 特化版本的仿函数，进行了一些数学上的处理。假设有 "abc"，"bca" 两个字符串，这两个字符串其实是不一样的数据，如果没有进行 hash *= 131 的数据处理，那么这两个字符串的加和就是一样的，那么使用除留余数法的时候就会发生哈希冲突。

4.1.1.3 哈希表的插入

bool Insert(const pair<K, V>& kv) {
    // 扩容
    if (_n * 10 / _table.size() >= 7) {
        size_t newSize = _table.size() * 2;
        // 遍历旧表，重新映射到新表
        HashTable<K, V, HashFunc> 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);
    }
    // 线性探测
    HashFunc hf;
    size_t hashi = hf(kv.first) % _table.size();
    while (_table[hashi]._state == EXIST) {
        ++hashi;
        hashi %= _table.size();
    }
    _table[hashi]._kv = kv;
    _table[hashi]._state = EXIST;
    ++_n;
    return true;
}

这里的插入，解决哈希冲突的方式利用的是 线性探测 的方式：先对哈希函数计算值所带入的 key 进行处理，转换为合理的计算值。如果计算得出的位置为 EXIST，就依次往后探测，直到找到空位置为止，然后插入即可。

那么哈希表满了之后的扩容是怎么一回事呢？ 我们要知道判断一个哈希表是否应该开始扩容的标准是 负载因子，通过 size / capacity 判断哈希表的填充程度，我们这里设置为 0.7 即扩容。 既然扩容了，之前的数据就必须重新计算位置放入哈希表，不然关系就全乱了。或许会有人想为什么不直接新创建一个数组来放？而是创建一个新对象 HashTable<K, V, HashFunc> newHT，再来创建新哈希表，这是因为在对象里操作可以使用插入等便捷操作，使得新哈希表的创建更方便。

值得注意的是：

• 计算位置时除 size，而不是 capacity，因为 size 直接反映了数组的有效长度，[0, table_size-1] 是索引的合法范围。
• hashi %= _table.size() 是为了避免超出数组有效索引范围，只要大于 size 就会被除余回到数组第一个位置。
• 有人担心扩容会影响搜索效率，其实影响并不是很大，每次扩容都为之前的两倍，会比之前大很多，也就碰上扩容那一次效率不太高，整体来讲影响是不大的。

4.1.1.4 哈希表的查找

HashData<const K, V>* Find(const K& key) {
    // 线性探测
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    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;
}

循环条件为 _table[hashi]._state != EMPTY 是因为在插入的时候为空就必定插入，那么查找的过程中在找到新的空之前必定能找到想要的值（如果正确插入的话）。if 条件还必须加入 _table[hashi]._state == EXIST 是因为避免查找到的是已删除的值。

值得注意的是：返回的是 HashData<const K, V>*，而不是 HashData<K, V>*，防止 key 被错误修改。

4.1.1.5 哈希表的删除

bool Erase(const K& key) {
    HashData<const K, V>* ret = Find(key);
    if (ret) {
        ret->_state = DELETE;
        --_n;
        return true;
    }
    return false;
}

删除可以说是我们学的那么多个结构里，比插入简单的了，直接删除修改状态即可。

4.1.2 二次探测

二次探测的位置计算基于平方序列探测的，下面将给出详细的计算步骤：

1. 核心计算公式 给定初始哈希位置 h₀ 和探测次数 i，下一个探测位置为：

h(i) = (h₀ + i * i) % table_size

• h₀：初始哈希值（例如 hash(key) % table_size）
• i：探测次数，从 1 开始递增
• table_size：哈希表的大小（必须为素数，否则可能无法覆盖所有槽位）

2. 计算步骤示例 假设哈希表大小 table_size = 7（素数），初始哈希位置 h₀ = 3，插入时发生冲突，则二次探测的位置序列为： | 探测次数 i | 计算公式 | 结果 h(i) | | --- | --- | --- | | 1 | (3 + 1²) % 7 | 4 | | 2 | (3 + 2²) % 7 | 0 | | 3 | (3 + 3²) % 7 | 5 | | 4 | (3 + 4²) % 7 | 2 | | 5 | (3 + 5²) % 7 | 6 | | 6 | (3 + 6²) % 7 | 1 |

序列： 3 → 4 → 0 → 5 → 2 → 6 → 1，覆盖所有 7 个槽位

3. 为什么表大小必须是素数？ 若 table_size 为合数，可能无法覆盖所有槽位。例如，当 table_size = 4（合数）时： | 探测次数 i | 计算公式 | 结果 h(i) | | --- | --- | --- | | 1 | (h₀ + 1²) % 4 | h₀ + 1 | | 2 | (h₀ + 2²) % 4 | h₀ | | 3 | (h₀ + 3²) % 4 | h₀ + 1 |

序列： h₀ → h₀+1 → h₀ → h₀+1，只能访问 2 个槽位，导致死循环。

4. 代码实现示例

bool Insert(const pair<K, V>& kv) {
    // 扩容逻辑（略）
    HashFunc hf;
    size_t h0 = hf(kv.first) % _table.size();
    // 二次探测
    for (size_t i = 1; i < _table.size(); ++i) {
        size_t hashi = (h0 + i * i) % _table.size();
        if (_table[hashi]._state != EXIST) {
            _table[hashi]._kv = kv;
            _table[hashi]._state = EXIST;
            ++_n;
            return true;
        }
    }
    return false; // 表满（实际不会触发，因提前扩容）
}

4.1.3 线性探测和二次探测对比

4.2 开散列

4.2.1 哈希桶

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。 闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。那么有没有办法不把数据只局限在数组里？有的，可以使用 拉链法，也叫 哈希桶，将数据以单链表的形式挂起来。

4.2.1.1 哈希表的基本数据结构

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, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable {
    typedef HashNode<K, V> Node;
public:
    HashTable() { _table.resize(10, nullptr); }
    ~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; // 指针数组
    size_t _n = 0; // 存储了多少个有效数据
};

vector<Node*> 或者 vector<list> 都是可以的，节点都是指针需要释放，析构函数需要自己实现。

4.2.1.2 哈希表的插入

bool Insert(const pair<K, V>& kv) {
    if (Find(kv.first)) {
        return false;
    }
    HashFunc hf;
    // 负载因子到 1 就扩容
    if (_n == _table.size()) {
        size_t newSize = _table.size() * 2;
        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(cur->_kv.first) % newSize;
                cur->_next = newTable[hashi];
                newTable[hashi] = cur;
                cur = next;
            }
            _table[i] = nullptr;
        }
        _table.swap(newTable);
    }
    size_t hashi = hf(kv.first) % _table.size();
    // 头插
    Node* newnode = new Node(kv);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_n;
    return true;
}

由于每个哈希桶可以挂多个数据以节省空间，负载因子可以扩大到 1，平均下来一个桶一个数据。 这里悬挂操作是以如图头插的方式进行的，在扩容时，把原先的桶挂到新表上的时候，由于是头插，原先的单链表会在新表上倒置，但是这不影响查找元素，每条桶的元素还是固定的，只是顺序不一样而已。

4.2.1.3 哈希表的查找

Node* Find(const K& key) {
    HashFunc hf;
    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;
}

当查找的节点为头节点时，prev 为空。

4.2.1.4 哈希表的删除

bool Erase(const K& key) {
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    Node* prev = nullptr;
    Node* cur = _table[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                _table[hashi] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

当查找的节点为头节点时，prev 为空，直接让下一个节点成为头节点即可。 当查找的节点为其他节点时，让前一个节点和下一个节点链接。 记得释放删除的节点。

4.3 开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。

事实上： 由于开放地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子 a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。