哈希表核心原理与 C++ 实战实现

开放定址法

所有元素都放入哈希表中。当发生冲突时，按某种规则寻找下一个空位存储。此方法要求负载因子严格小于 1。

线性探测

从冲突位置开始，依次向后探测，直到找到空位。若到达表尾则回绕到表头。

问题：容易产生'群集'现象。多个连续冲突的数据会抢占后续数据的存储位置，导致后续数据需要遍历更多空位才能找到存放处。因此实际中通常保持负载因子小于 0.7，超过则扩容。

开放定址法的结构与查找设计

由于删除操作会影响查找逻辑（直接清空位置会导致后续冲突数据无法被找到），我们需要给每个位置增加状态标识：EXIST（存在）、EMPTY（空）、DELETE（已删除）。查找时遇到 EMPTY 才停止，遇到 DELETE 则继续。

enum State { EXIST, EMPTY, DELETE };
template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;
};

仿函数与 Key 转换

当 Key 为 string 等非整型时，需要仿函数将其转换为可取模的整形。STL 的 unordered 系列针对 string 做了特化，我们实现时也可以自定义仿函数。常用的 BKDR 哈希思路是将字符串字符累加并乘上质数（如 31 或 131），以减少不同顺序字符串的冲突。

template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // 默认强转
    }
};

// 针对 string 的特化
template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto e : key) {
            hash *= 131;
            hash += e;
        }
        return hash;
    }
};

插入、删除与扩容

插入时需检查是否已存在。若负载因子过高（如大于 0.7），需扩容。扩容通常将表大小翻倍，并将旧数据重新映射到新表。

bool Insert(const pair<K, V>& kv) {
    if (Find(kv.first)) return false;
    
    // 负载因子控制，避免浮点数比较
    if (_n * 10 / _tables.size() >= 7) {
        HashTable<K, V, Hash> newHT;
        newHT._tables.resize(_tables.size() * 2);
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]._state == EXIST) {
                newHT.Insert(_tables[i]._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;
}

二次探测与双重散列

线性探测容易聚集，二次探测通过平方级跳跃（±i²）来缓解这一问题。双重散列则使用第二个哈希函数计算偏移量，进一步打乱探测序列。这两种方法都能在一定程度上改善堆积现象，但实现复杂度略高。

链地址法

开放定址法中所有元素竞争同一块空间，而链地址法（拉链法）将哈希表中的每个位置视为一个桶（Bucket）。若有多个数据映射到同一位置，则将这些数据链接成链表挂在下面。

结构设计与扩容

链地址法对负载因子限制较少，理论上可以大于 1。但因子过大导致链表过长，查找效率下降。通常控制在 1 左右进行扩容。

扩容时，为了避免重复创建节点，可以将旧表的节点直接移动到新表重新映射位置，这样效率更高。

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, class V, class Hash = HashFunc<K>>
class HashTable {
    typedef HashNode<K, V> Node;
    vector<Node*> _tables;
    size_t _n = 0;
    
public:
    ~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) {
        Hash hs;
        size_t hashi = hs(kv.first) % _tables.size();
        
        if (_n == _tables.size()) {
            // 扩容逻辑：移动旧节点到新表
            vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    size_t newHashi = hs(cur->_kv.first) % newtables.size();
                    cur->_next = newtables[newHashi];
                    newtables[newHashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
            hashi = hs(kv.first) % _tables.size();
        }
        
        // 头插法
        Node* newnode = new Node(kv);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return true;
    }
    
    // Find 和 Erase 实现类似，遍历链表查找匹配项
    // ... (省略具体遍历代码)
};
} // namespace hash_bucket

极端场景处理

如果某个桶特别长，查找效率会急剧下降。Java 8 的 HashMap 引入了红黑树机制，当链表长度超过阈值（如 8）时将链表转为红黑树。当然，在一般工程实践中，合理控制负载因子和扩容策略，极少会遇到这种情况。