深入 C++ 哈希表：从除留余数到红黑树优化

线性探测的问题是容易产生'群集'——一旦连续几个位置被占，新插入的 key 就会继续往后挤，让原本不相干的 key 也撞到一起。

插入实现：

bool Insert(const pair<K, V>& kv) {
    size_t hash0 = kv.first % _tables.size();
    size_t hashi = hash0;
    size_t i = 1;
    while (_tables[hashi]._status == EXIST) {
        hashi = (hashi + i) % _tables.size();
        i++;
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._status = EXIST;
    ++_n;
    return true;
}

扩容与素数表

当 _n / _tables.size() 超过负载因子（比如 0.7）时就需要扩容。直接 2 倍扩容会破坏除留余数法的均匀性——表长变为了 2 的幂。

STL 的做法是预先准备一个素数列表，每次扩容时从中选取下一个素数：

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

inline unsigned long __stl_next_prime(unsigned long n) {
    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;
}

扩容时创建一个新表，把旧表里 EXIST 的元素重新 Insert 进去，最后 swap：

if ((double)_n / (double)_tables.size() > 0.7) {
    HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + 1));
    for (size_t i = 0; i < _tables.size(); i++) {
        if (_tables[i]._status == EXIST) {
            newHT.Insert(_tables[i]._kv);
        }
    }
    _tables.swap(newHT._tables);
}

查找和删除都基于同样的探测规则，删除只是把状态改为 DELETE，不实际释放节点。完整代码：

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

inline unsigned long __stl_next_prime(unsigned long n) {
    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;
}

enum Status { EMPTY, EXIST, DELETE };

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

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

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
    HashTable(size_t size = __stl_next_prime(0)) :_tables(size), _n(0) {}

    bool Insert(const pair<K, V>& kv) {
        if ((double)_n / (double)_tables.size() > 0.7) {
            HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + 1));
            for (size_t i = 0; i < _tables.size(); i++) {
                if (_tables[i]._status == EXIST) {
                    newHT.Insert(_tables[i]._kv);
                }
            }
            _tables.swap(newHT._tables);
        }

        size_t hash0 = kv.first % _tables.size();
        size_t hashi = hash0;
        size_t i = 1;
        while (_tables[hashi]._status == EXIST) {
            hashi = (hashi + i) % _tables.size();
            i++;
        }
        _tables[hashi]._kv = kv;
        _tables[hashi]._status = EXIST;
        ++_n;
        return true;
    }

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

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

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

链地址法（哈希桶）

开放定址法下所有元素挤在一个数组里，冲突会互相影响。链地址法则让每个槽位变成一个链表头，冲突的元素直接挂到链表上。这样负载因子可以 > 1，空间利用率更高。

极端情况下，如果所有 key 都映射到同一个桶，链表长度变成 O(N)，查找退化为线性。常见的优化是当桶长度超过阈值（比如 8）时，把链表转成红黑树。Java 的 HashMap 就是这么做的，C++ 的 unordered_map 也类似，不过标准没强制要求。

节点定义：

template<class K, class V>
struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) :_next(nullptr), _kv(kv) {}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
    typedef HashNode<K, V> Node;
public:
    HashTable(size_t size = __stl_next_prime(0)) :_tables(size, nullptr), _n(0) {}
private:
    vector<Node*> _tables;
    size_t _n;
};

非整数 key 的处理

Key 不是整数时，比如浮点数、负数或字符串，需要把它转成 size_t。浮点数和负数可以直接强转，但字符串不行。

对字符串我们使用特化的仿函数：

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

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

这样模板参数中默认的 Hash = HashFunc<K> 就能自动适配了。

扩容：复用节点

链地址法扩容时，如果直接遍历旧桶，对每个节点重新 Insert，会涉及 new 新节点 + delete 旧节点，开销太大。更好的做法是直接把旧节点'摘'下来挂到新表的对应位置：

bool Insert(const pair<K, V>& kv) {
    if (Find(kv.first)) return false;
    
    Hash hs;
    if (_n == _tables.size()) {  // 负载因子 >= 1 时扩容
        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 hash0 = hs(cur->_kv.first) % newtables.size();
                cur->_next = newtables[hash0];
                newtables[hash0] = cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
        _tables.swap(newtables);
    }

    size_t hash0 = hs(kv.first) % _tables.size();
    Node* newnode = new Node(kv);
    newnode->_next = _tables[hash0];
    _tables[hash0] = newnode;
    ++_n;
    return true;
}

删除

bool Erase(const K& key) {
    Hash hs;
    size_t hash0 = hs(key) % _tables.size();
    Node* prev = nullptr;
    Node* cur = _tables[hash0];
    while (cur) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                _tables[hash0] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            --_n;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

完整实现带析构：

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

inline unsigned long __stl_next_prime(unsigned long n) {
    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;
}

template<class K, class V>
struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) :_next(nullptr), _kv(kv) {}
};

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

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

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
    typedef HashNode<K, V> Node;
public:
    HashTable(size_t size = __stl_next_prime(0)) :_tables(size, nullptr), _n(0) {}

    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) return false;
        
        Hash hs;
        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 hash0 = hs(cur->_kv.first) % newtables.size();
                    cur->_next = newtables[hash0];
                    newtables[hash0] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
        }

        size_t hash0 = hs(kv.first) % _tables.size();
        Node* newnode = new Node(kv);
        newnode->_next = _tables[hash0];
        _tables[hash0] = 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 hash0 = hs(key) % _tables.size();
        Node* prev = nullptr;
        Node* cur = _tables[hash0];
        while (cur) {
            if (cur->_kv.first == key) {
                if (prev == nullptr) {
                    _tables[hash0] = cur->_next;
                } else {
                    prev->_next = cur->_next;
                }
                --_n;
                delete cur;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

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

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