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

unordered 系列关联式容器

unordered_map、unordered_set、unordered_multimap、unordered_multiset 均使用哈希表实现，接口与 set 类似，支持范围 for 遍历。

与 set 的区别：

1. 迭代器为单向迭代器。
2. 中序遍历结果无序。
3. 性能通常优于 set，但在有序数据插入场景下 set 表现更好。

注意：性能比较应在 Release 模式下进行。

哈希

哈希（散列）是建立值与存储位置对应关系的方法，以空间换时间。常用方法包括直接定址法和除留余数法。

哈希冲突

不同值映射到相同位置即发生冲突。解决策略：

1. 闭散列（开放定址法）：当前位置被占用时按规则寻找下一个位置（如线性探测、二次探测）。
2. 开散列（链地址法/哈希桶）：每个位置挂一个链表。

闭散列的模拟实现

采用除留余数法加线性探测。状态标记使用 EXIST、EMPTY、DELETE。

enum State { EXIST, EMPTY, DELETE };

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

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

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable {
public:
    HashTable() { _table.resize(10); }

    bool  {
         (_n *  / _table.() >= ) {
             newSize = _table.() * ;
            HashTable<K, V, HashFunc> newHT;
            newHT._table.(newSize);
             ( i = ; i < _table.(); ++i) {
                 (_table[i]._state == EXIST) {
                    newHT.(_table[i]._kv);
                }
            }
            _table.(newHT._table);
        }

        HashFunc hf;
         hashi = (kv.first) % _table.();
         (_table[hashi]._state == EXIST) {
            ++hashi;
            hashi %= _table.();
        }
        _table[hashi]._kv = kv;
        _table[hashi]._state = EXIST;
        ++_n;
         ;
    }

    {
        HashFunc hf;
         hashi = (key) % _table.();
         (_table[hashi]._state != EMPTY) {
             (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
                 (HashData< K, V>*)&_table[hashi];
            }
            ++hashi;
            hashi %= _table.();
        }
         ;
    }

    {
        HashData< K, V>* ret = (key);
         (ret) {
            ret->_state = DELETE;
            --_n;
             ;
        }
         ;
    }

:
    vector<HashData<K, V>> _table;
     _n = ;
};