C++ unordered_map/set 底层原理与位图布隆过滤器实现

注意：扩容时 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); }

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

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

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(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 algo_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;
    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 algo_lib {
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 亿个不重复无符号整数，快速判断某数是否存在。 使用位图节省空间。int 类型 32 位，需 size_t 范围的比特位。

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 亿整数，内存 1G。可用位图存 42 亿多整数（约 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) == false) return false;
        size_t hash2 = Hash2()(key) % N;
        if (_bs.test(hash2) == false) return false;
        size_t hash3 = Hash3()(key) % N;
        if (_bs.test(hash3) == false) return false;
        return true;
    }

private:
    bitset<N> _bs;
};

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

优化参数 k（哈希函数个数）、m（长度）、n（元素个数）。

哈希切割

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

哈希切割的应用

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

• 近似算法： 布隆过滤器。
• 精确算法： 哈希切割。相同 query 进入相同编号文件（如 A1 和 B1）。若内存不足，可二次切分。

求 Top K IP： 每个小文件保留前 K 多地址到堆和 map，最后汇总比较。

作业部分

1. 散列函数应同等概率取值域每一个值。（C）
2. 解决冲突方法：线性探测、多重散列、链地址法。（D）
3. 平均查找长度计算：总查找长度除以元素个数。
4. 二次探测再散列 n 个关键字至少探测次数：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;
    }
};

位图说法错误： D. 位图可以很方便的进行字符串的映射以及查找（易冲突）。

力扣 884. 两句话中的不常见单词 注意空字符串处理，count 返回出现次数仅适用于 multimap/multiset。

unordered_map/set 说法错误： D. 插入时都得通过 key 的比较去找待插入元素的位置（哈希表直接定位）。