C++ 哈希表核心机制：unordered 系列容器、位图与布隆过滤器实战

提示：类模板按需编译，未使用的成员函数不会生成代码。

开散列模拟实现

开散列使用指针数组存储链表头节点。负载因子达到 1 时触发扩容，将旧节点重新映射到新表。

template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable {
    typedef HashNode<T> Node;
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
    friend struct HTIterator;

public:
    typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
    typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;

    iterator begin() {
        for (size_t i = 0; i < _table.size(); ++i) {
            Node* cur = _table[i];
            if (cur) return iterator(cur, this);
        }
        return iterator(nullptr, this);
    }

    iterator end() { return iterator(nullptr, this); }

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

    pair<iterator, bool> Insert(const T& data) {
        KeyOfT kot;
        iterator it = Find(kot(data));
        if (it != end()) return make_pair(it, false);

        HashFunc hf;
        if (_n == _table.size()) {
            size_t newSize = _table.size() * 2;
            vector<Node*> newTable(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(kot(cur->_data)) % newSize;
                    cur->_next = newTable[hashi];
                    newTable[hashi] = cur;
                    cur = next;
                }
                _table[i] = nullptr;
            }
            _table.swap(newTable);
        }

        size_t hashi = hf(kot(data)) % _table.size();
        Node* newnode = new Node(data);
        newnode->_next = _table[hashi];
        _table[hashi] = newnode;
        ++_n;
        return make_pair(iterator(newnode, this), true);
    }

    iterator Find(const K& key) {
        HashFunc hf;
        KeyOfT kot;
        size_t hashi = hf(key) % _table.size();
        Node* cur = _table[hashi];
        while (cur) {
            if (kot(cur->_data) == key) return iterator(cur, this);
            cur = cur->_next;
        }
        return end();
    }

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

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

迭代器模拟实现

迭代器需处理跨桶遍历逻辑。若当前桶链表结束，则查找下一个非空桶。

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator {
    typedef HashNode<T> Node;
    typedef HTIterator Self;
    typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;

    Node* _node;
    HashTable<K, T, KeyOfT, HashFunc>* _pht;

    HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
        : _node(node), _pht(const_cast<HashTable*>(pht)) {}

    HTIterator(const Iterator& it) : _node(it._node), _pht(it._pht) {}

    Ref operator*() { return _node->_data; }
    Ptr operator->() { return &_node->_data; }

    Self& operator++() {
        if (_node->_next) {
            _node = _node->_next;
        } else {
            KeyOfT kot;
            HashFunc hf;
            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;
    }

    bool operator!=(const Self& s) { return _node != s._node; }
    bool operator==(const Self& s) { return _node == s._node; }
};

unordered_set 与 unordered_map 封装

基于上述哈希桶实现标准库容器。

namespace my_hash {
template<class K>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) { return key; }
    };
public:
    typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
    typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;

    iterator begin() { return _ht.begin(); }
    iterator end() { return _ht.end(); }

    pair<const_iterator, bool> insert(const K& key) {
        pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
        return pair<const_iterator, bool>(ret.first, ret.second);
    }

private:
    hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};

template<class K, class V>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) { return kv.first; }
    };
public:
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

    iterator begin() { return _ht.begin(); }
    iterator end() { return _ht.end(); }

    pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }

    V& operator[](const K& key) {
        pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
        return ret.first->second;
    }

private:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}

位图（Bitmap）

利用比特位表示信息，常用于海量数据去重或存在性判断。标准库中对应 bitset。

应用场景

面试题：40 亿个无符号整数，快速判断某数是否存在。

• 使用 set 或排序二分查找空间开销过大。
• 位图仅需约 500MB 内存（40 亿 bit）。int 类型 32 位，每 32 个数占一个 int 单元。

template<size_t N>
class bitset {
public:
    bitset() { _a.resize(N / 32 + 1); }

    void set(size_t x) {
        size_t i = x / 32;
        size_t j = x % 32;
        _a[i] |= (1 << j);
    }

    void reset(size_t x) {
        size_t i = x / 32;
        size_t j = x % 32;
        _a[i] &= (~(1 << j));
    }

    bool test(size_t x) {
        size_t i = x / 32;
        size_t j = x % 32;
        return _a[i] & (1 << j);
    }

private:
    vector<int> _a;
};

注意：位图主要用于数值型数据的映射，字符串映射易冲突。

布隆过滤器（Bloom Filter）

利用多个独立哈希函数将元素特性映射到位图中。若所有对应位均为 1，则可能存在；若任一为 0，则一定不存在。

模拟实现

template<size_t N, class K, class Hash1, class Hash2, class Hash3>
class BloomFilter {
public:
    void Set(const K& key) {
        size_t hash1 = Hash1()(key) % N;
        _bs.set(hash1);
        size_t hash2 = Hash2()(key) % N;
        _bs.set(hash2);
        size_t hash3 = Hash3()(key) % N;
        _bs.set(hash3);
    }

    bool Test(const K& key) {
        size_t hash1 = Hash1()(key) % N;
        if (!_bs.test(hash1)) return false;
        size_t hash2 = Hash2()(key) % N;
        if (!_bs.test(hash2)) return false;
        size_t hash3 = Hash3()(key) % N;
        if (!_bs.test(hash3)) return false;
        return true;
    }

private:
    bitset<N> _bs;
};

限制：不支持直接删除（会导致误判），如需删除需引入引用计数。

哈希切割

将大文件数据根据哈希特征分片到多个小文件，解决单机内存不足问题。

应用案例

问题：两个 100 亿 query 文件，内存仅 1G，求交集。

• 近似算法：布隆过滤器过滤。
• 精确算法：哈希切割。两文件用相同哈希函数分片（A1-A10, B1-B10），相同 query 必落入同编号文件，逐对比较。

扩展：日志文件中找 Top K IP。

• 分片后，每片维护一个小顶堆或 Map，最后汇总比较。

练习题

1. 散列函数应使函数值按（ ）取其值域的每一个值。

   • A.最大概率 B.最小概率 C.同等概率 D.平均概率
   • 答案：C

2. 解决散列冲突常采用的方法是（ ）。

   • A.数字分析法、除余法、平方取中法
   • B.数字分析法、除余法、线性探测法
   • C.数字分析法、线性探测法、多重散列法
   • D.线性探测法、多重散列法、链地址法
   • 答案：D

3. 已知关键字序列（19, 14, 23...）散列存储于 H(key)=key%7 的表中，采用链地址法，等概率下查找成功的平均查找长度为（ ）。

   • 答案：A (1.5)

4. 关于位图说法错误的是（ ）。

   • A.用比特位表示状态
   • B.可求集合交集
   • C.是哈希变形思想的应用
   • D.方便进行字符串映射及查找
   • 答案：D

5. 关于 unordered_map/set 说法错误的是（ ）。

   • A.存储类型不同
   • B.底层结构相同
   • C.查找复杂度平均 O(1)
   • D.插入时都必须通过 key 比较找位置
   • 答案：D

参考题目：力扣 350. 两个数组的交集 II；力扣 884. 两句话中的不常见单词。