STL 哈希表原理与模拟实现

（2）二次探测

为了缓解聚集问题，采用平方级跳跃探测：hc(key, i) = (hash0 ± i^2) % M。左右交替探测能让数据分布更分散。

（3）双重散列

使用第二个哈希函数计算偏移量，进一步打乱探测顺序。这通常用于对性能要求极高的场景，这里仅作了解。

7.2 开放定址法代码实现

开放定址法实现相对简单，但要注意扩容和删除逻辑。特别是删除操作，不能直接清空位置，否则会影响后续冲突数据的查找。我们需要给每个位置增加状态标识：EXIST（存在）、EMPTY（空）、DELETE（已删除）。

enum State { EXIST, EMPTY, 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 {
private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0; // 表中存储数据个数

public:
    // 获取下一个大于 n 的质数，保证扩容后仍是质数
    inline unsigned long __stl_next_prime(unsigned long n) {
        static const int __stl_num_primes = 28;
        static const unsigned long __stl_prime_list[__stl_num_primes] = {
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
            6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
            402653189, 805306457, 1610612741, 3221225473, 4294967291
        };
        const unsigned long* first = __stl_prime_list;
        const unsigned long* last = __stl_prime_list + __stl_num_primes;
        const unsigned long* pos = lower_bound(first, last, n);
        return pos == last ? *(last - 1) : *pos;
    }

    HashTable() {
        _tables.resize(__stl_next_prime(0));
    }

    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) return false; // 防止重复插入

        // 负载因子大于 0.7 时扩容
        if (_n * 10 / _tables.size() >= 7) {
            HashTable<K, V, Hash> newHT;
            newHT._tables.resize(__stl_next_prime(_tables.size() + 1));
            for (size_t i = 0; i < _tables.size(); ++i) {
                if (_tables[i]._state == EXIST) {
                    newHT.Insert(_tables[i]._kv);
                }
            }
            _tables.swap(newHT._tables);
        }

        Hash hash;
        size_t hash0 = hash(kv.first) % _tables.size();
        size_t hashi = hash0;
        size_t i = 1;
        
        // 线性探测
        while (_tables[hashi]._state == EXIST) {
            hashi = (hash0 + i) % _tables.size();
            ++i;
        }

        _tables[hashi]._kv = kv;
        _tables[hashi]._state = EXIST;
        ++_n;
        return true;
    }

    HashData<K, V>* Find(const K& key) {
        Hash hash;
        size_t hash0 = hash(key) % _tables.size();
        size_t hashi = hash0;
        size_t i = 1;
        
        while (_tables[hashi]._state != EMPTY) {
            if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) {
                return &_tables[hashi];
            }
            hashi = (hash0 + i) % _tables.size();
            ++i;
        }
        return nullptr;
    }

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

private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0;
};

7.3 链地址法

链地址法（拉链法）不直接在表中存数据，而是将哈希值相同的数据链接成链表挂在桶上。这种方式允许负载因子大于 1，且扩容时只需移动节点指针，无需重新计算所有 Key 的哈希值（虽然实际实现中通常会重哈希以平衡负载）。

（1）解决冲突的思路

哈希表存储指针数组。若某位置无数据，指针为空；若有多个 Key 映射至此，则形成链表。

（2）极端场景优化

如果某个桶特别长，查找效率会退化为 O(N)。Java 8 的 HashMap 引入了红黑树来优化这种情况。C++ STL 的 unordered_map 目前仍主要依赖链表，但在某些实现中也会考虑树化优化。

（3）链地址法代码实现

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;
    
public:
    HashTable() {
        _tables.resize(__stl_next_prime(0), nullptr);
    }

    ~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();

        // 负载因子等于 1 时扩容
        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;
    }

    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 == nullptr) {
                    _tables[hashi] = cur->_next;
                } else {
                    prev->_next = cur->_next;
                }
                delete cur;
                --_n;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

private:
    vector<Node*> _tables;
    size_t _n = 0;
};

总结

哈希表通过数学映射实现了高效的存取，但其核心挑战在于处理冲突。无论是开放定址法还是链地址法，都需要权衡空间利用率和时间复杂度。理解这些底层机制，有助于我们在实际开发中更好地选择容器类型，并在遇到性能瓶颈时进行针对性的优化。