C++ 哈希表底层实现：unordered_map/set、位图与布隆过滤器

使用 EXIST, EMPTY, DELETE 标记状态。删除节点标记为 DELETE 而非 EMPTY，以便在查找时继续向后探测。扩容时不迁移 DELETE 状态的节点。 负载因子越大，冲突概率越高，空间利用率越高；反之亦然。

开散列的模拟实现

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

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

    const_iterator end() const { return const_iterator(nullptr, this); }

    HashTable() { _table.resize(10, nullptr); }

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

    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;
            newTable.resize(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);
    }

    Node* 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 cur;
            cur = cur->_next;
        }
        return nullptr;
    }

    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 == nullptr) _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;
};

哈希桶打印建议将链表打在一行。负载因子达到 1 时扩容。新旧表转移需重新计算哈希值。节点可优化为树结构（红黑树）。

哈希桶里面迭代器的模拟实现

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator {
    typedef HashNode<T> Node;
    typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> 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((HashTable<K, T, KeyOfT, HashFunc>*)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;
                } else {
                    ++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 的封装

namespace renshen {
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;
};
}

unordered_map 的封装

namespace renshen {
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(); }
    const_iterator begin() const { return _ht.begin(); }
    const_iterator end() const { 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;
};
}

位图

用数的比特位表达信息，库中对应 bitset。常用接口：test, set, reset。

应用

面试题： 给 40 亿个不重复无符号整数，快速判断一个数是否存在。 使用 set 或排序 + 二分查找空间过大，位图更优。一个 int 有 32 比特位，可用 32 个数表示一组状态。

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

应用场景：

1. 给定 100 亿个整数，找到只出现一次的整数。使用两个位图，同一位置分别记录出现一次和多次的状态。
2. 两个文件各 100 亿个整数，内存 1G，求交集。位图占用约 512MB，可将文件映射到位图比对。

布隆过滤器

利用多个独立哈希函数 + 位图实现的高效存在性判断结构。若所有哈希位置均为 1，则可能存在；否则一定不在。

应用场景： 快速判断昵称是否注册过。精确查询需回查数据库。

布隆过滤器的模拟实现

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

注意：布隆过滤器一般不支持删除操作，否则会导致误判。如需删除，可使用引用计数。

优化参数：k 为哈希函数个数，m 为长度，n 为元素个数。

哈希函数示例：

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

哈希切割

运用哈希函数将大文件数据分到多个小文件。

哈希切割的应用

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

• 近似算法： 布隆过滤器。
• 精确算法： 哈希切割。两文件用相同哈希函数分片，相同 query 进入同编号文件（如 A1 与 B1），逐个比对。

若内存不足：

1. 读入 set，若抛出 bad_alloc 说明冲突太多，更换哈希函数二次切分。
2. 若未报错但数据量大，可能是重复数据多。

其他题目： 100G log file 找出现次数最多的 IP。对小文件前 k 多的地址保留到堆和 map，最后汇总比较。

作业部分

1. 散列函数性质：函数值应按同等概率取其值域的每一个值。（C）
2. 解决冲突方法：线性探测法、多重散列法、链地址法。（D）
3. 平均查找长度计算：总查找长度除以元素个数。
4. 二次探测再散列至少探测次数：n(n+1)/2。（E）

力扣 350. 两个数组的交集 II 核心逻辑：统计频次后取最小值，处理重复统计。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> hash1;
        unordered_map<int, int> hash2;
        vector<int> v;
        for (auto e : nums1) hash1[e]++;
        for (auto e : nums2) hash2[e]++;
        for (auto e : nums1) {
            if (hash1.count(e) && hash2.count(e)) {
                for (int i = 0; i < min(hash1[e], hash2[e]); ++i) {
                    v.push_back(e);
                }
                hash1[e] = 0;
                hash2[e] = 0;
            }
        }
        return v;
    }
};

力扣 884. 两句话中的不常见单词 核心逻辑：统计词频，找出只出现一次的单词。

选择题：关于 unordered_map 和 unordered_set 说法错误的是（D）。 D. 它们在进行元素插入时，都得要通过 key 的比较去找待插入元素的位置。 实际上插入时通过哈希值定位 bucket，无需 key 比较即可确定位置，仅在冲突处理时才涉及比较。