C++ 哈希表原理与 STL 容器实现详解

负载因子与扩容

哈希表不能无限填充，否则效率下降。通常设定负载因子阈值（如 0.7），超过则扩容。扩容时需重新计算所有元素的哈希位置（Rehash）。

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);
}

Key 类型的泛型处理

默认哈希函数假设 Key 可取模。对于 string 等非整型，需使用仿函数特化。简单的字符串哈希可将字符 ASCII 累加，但易冲突。更优方案是结合乘法因子（如 131）进行混合。

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

拉链法——哈希桶

为避免探测带来的性能抖动，拉链法将每个桶设计为链表。冲突时直接在链表头插入新节点。

扩容优化

扩容时，直接将旧链表的节点迁移到新表，避免重复构造节点。

// 迁移节点逻辑
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;
}

迭代器封装

为了兼容 STL 风格，需要手动实现迭代器。关键在于 operator++ 的处理：当前桶遍历完后，需查找下一个非空桶。

Self& operator++() {
    if (_node->_next) {
        _node = _node->_next;
    } else {
        // 查找下一个非空桶
        size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
        ++hashi;
        while (hashi < _pht->_table.size()) {
            if (_pht->_table[hashi]) {
                _node = _pht->_table[hashi];
                return *this;
            }
            ++hashi;
        }
        _node = nullptr;
    }
    return *this;
}

Const 迭代器支持

需注意 const 对象调用成员函数时权限限制。通过重载构造函数或调整成员变量访问权限，确保 const_iterator 能正确返回只读引用。

总结

通过上述步骤，我们实现了基于哈希表的 unordered_map 和 unordered_set 基础框架。理解其底层机制有助于在开发中更好地利用标准库容器，并在特定场景下定制高性能数据结构。