C++ 哈希表与位图实战：unordered_map/set 底层原理及实现

这里的关键点在于扩容时的重新哈希（Rehash）。旧表中的有效数据需逐个取出并插入新表，DELETE 状态的数据不应迁移，否则会导致逻辑错误。

开散列（链地址法）

每个哈希桶维护一个链表，冲突元素挂在对应桶后。这种方式避免了闭散列的聚集问题，且扩容只需调整桶指针。

template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable {
    struct HashNode {
        T _data;
        HashNode* _next;
        HashNode(const T& data) : _data(data), _next(nullptr) {}
    };

    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;
                delete cur;
                --_n;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

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

开散列的迭代器需要跨越多个桶，因此 operator++ 的逻辑较为复杂：先遍历当前桶链表，若到头则跳转到下一个非空桶。

封装 unordered_set 与 unordered_map

基于上述哈希表，我们可以轻松封装标准库风格的容器。关键在于定义 KeyOfT 提取器，以便统一处理键值对。

namespace hash_lib {
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;
    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;
    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）

利用比特位表示状态，极大节省空间。例如判断 40 亿个无符号整数中是否存在某数，使用 bitset 仅需约 500MB 内存。

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

应用场景包括：海量数据去重、交集计算等。例如两个文件各含 100 亿整数，求交集时可将其中一个映射到位图，遍历另一个比对。

布隆过滤器（Bloom Filter）

布隆过滤器是位图的扩展，使用多个独立哈希函数将元素映射到位图中。若所有对应位均为 1，则认为元素可能存在；若任一为 0，则一定不存在。

优点：空间效率极高，查询速度快。 缺点：存在误判率（False Positive），不支持直接删除（除非使用计数位图）。

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

常用于缓存穿透防护、URL 黑名单过滤等场景。实际使用时，若判定存在，建议再查数据库确认。

哈希切割与大数据处理

当数据量超过单机内存限制时（如 100G 日志文件），可采用哈希切割技术。通过相同哈希函数将大文件分流到多个小文件，确保相同 Key 落入同一文件，从而分治处理。

典型问题：两个 100 亿 Query 文件，1G 内存，求交集。

• 近似算法：使用布隆过滤器过滤掉肯定不在的元素。
• 精确算法：哈希切割。将两个文件分别切分为 N 个小文件，相同编号的小文件内用 set 或 map 求交集。

若某个小文件仍过大，说明哈希冲突严重，需更换哈希函数进行二次切割。

实战案例

两数组的交集 II

核心思路是利用哈希表统计频次，注意处理重复元素的匹配数量。

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

不常见单词

利用 unordered_map 统计词频，找出只出现一次的单词。

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string, int> hash1, hash2;
        auto parse = [&](string& s, unordered_map<string, int>& m) {
            string a;
            for (char c : s) {
                if (c == ' ') {
                    m[a]++;
                    a.clear();
                } else {
                    a += c;
                }
            }
            m[a]++;
        };
        parse(s1, hash1);
        parse(s2, hash2);
        vector<string> v;
        for (auto& p : hash1) {
            if (p.second == 1 && hash2.find(p.first) == hash2.end()) v.push_back(p.first);
        }
        for (auto& p : hash2) {
            if (p.second == 1 && hash1.find(p.first) == hash1.end()) v.push_back(p.first);
        }
        return v;
    }
};

掌握这些底层原理与数据结构，能帮助我们在面对海量数据和高并发场景时，做出更合理的架构决策。