SGI-STL30 里没有 unordered_map 和 unordered_set,C++11 才把这两个容器扶正。那一版实现的是非标准的 hash_map 和 hash_set,两个外壳都把工作交给同一份 hashtable:

// hash_set
typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
 
// hash_map
typedef hashtable<pair<const Key, T>, Key, HashFcn,
                  select1st<pair<const Key, T>>, EqualKey, Alloc> ht;

底层模板的声明是:

template<class Value, class Key, class HashFcn,
         class ExtractKey, class EqualKey, class Alloc>
class hashtable;

Value 是结点里真正存放的对象,Key 是查找时认的关键字,HashFcn 把关键字算成整数,ExtractKey 从 Value 里取出关键字,EqualKey 判等,Alloc 管内存。算桶号、比相等时,哈希表只通过 ExtractKey 问“这个元素的关键字是什么”,元素里还有哪些字段,它不关心。

容器ValueKeyExtractKey
hash_setValue(就是 K)Valueidentity<Value>
hash_mappair<const Key, T>Keyselect1st<pair<const Key, T>>

同一份底层代码因此能服务两种容器。identity 原样返回,select1st 取 pair 的 first,两个“提货员”决定哈希表从哪里读关键字。

SGI 的 hash_set 把 iterator 和 const_iterator 都 typedef 成了 ht::const_iterator,它的迭代器天生只能读。原因不在底层,而在语义:set 的元素就是 key,改了元素等于改了哈希定位。标准库的 unordered_set::iterator 在类型上不是 const_iterator,但解引用同样返回 const Key&,约束没有放松。

把元素类型和关键字类型拆开

原来的哈希桶是 HashTable<K, V, Hash>,元素和关键字被绑死成同一对类型。要同时服务 set 和 map,得把元素类型独立出来,再加一个“提 key”参数:

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable;

K 只用于哈希和判等,T 是真正存进结点的东西。结点跟着改成只依赖 T:

template<class T>
struct HashNode
{
    T _data;
    HashNode<T>* _next;
    HashNode(const T& data) : _data(data), _next(nullptr) {}
};

set 传 T = const K,map 传 T = std::pair<const K, V>。为什么 set 的元素类型要带 const,后面单独说。

外层容器各提供一个 KeyOfT:

struct SetKeyOfT
{
    const K& operator()(const K& key) const { return key; }
};
 
struct MapKeyOfT
{
    const K& operator()(const std::pair<const K, V>& kv) const { return kv.first; }
};

set 的元素本来就是 K,这个原样返回的仿函数看起来多余。它不是给容器用的,是给底层用的:哈希表只会“从 T 里取出 K”这一个动作,如果 set 省掉这一步,底层就得为“T 等于 K”和“T 是 pair”写两套分支,泛型立刻裂开。

用仿函数而不是函数指针,是因为仿函数是类型的一部分。编译器可以为 set 和 map 各实例化一份 HashTable,把 kot(x) 内联进 Find 和 Insert,省掉一次间接调用。函数指针是运行期的值,做不到这件事。

Insert 返回 pair,operator[] 才有一次查找

Insert 先判重,再扩容,最后头插,返回 std::pair<Iterator, bool>。second 表示这次到底插没插进去,first 指向已存在或刚插入的元素。operator[] 就靠它一次查找完成“有则取、无则建”:

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

只返回 bool 的话,取值时还得再 Find 一次。operator[] 永远保证键存在,所以判断键在不在不能用它;一次 dict["string"] 就会插入一条值初始化的记录。

迭代器要带一个表指针

哈希桶是“桶数组加桶内链表”的二维结构。list 的迭代器只存一个结点指针就能走完全程,因为结点自带 next;哈希表走到当前链的链尾时,_next 是空,而“下一个非空桶在哪”的信息不在结点里,只有桶数组知道。

解法是在迭代器里放两个指针:_node 指着当前结点,负责解引用和桶内前进;_pht 指着哈希表对象,负责链走完后跨到下一个非空桶。

哈希桶里的迭代器:2 号桶的 it 指向 24,沿 _next 走到 13;链走完后靠表指针跳到 8 号桶,落在 96 上,后面还有 30、19

Self& operator++()
{
    if (_node->_next != nullptr)
    {
        _node = _node->_next;
        return *this;
    }
 
    KeyOfT kot;
    Hash hs;
    std::size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
    ++hashi;
    while (hashi < _pht->_tables.size() && _pht->_tables[hashi] == nullptr)
        ++hashi;
 
    _node = (hashi == _pht->_tables.size()) ? nullptr : _pht->_tables[hashi];
    return *this;
}

为什么不把“当前桶号”也存进迭代器?那会引入冗余状态,拷贝、比较、赋值时都要维护。反推桶号的代价是每条链末尾多算一次哈希,均摊很小。

begin() 找第一个非空桶,end() 用空指针当哨兵:

Iterator Begin()
{
    for (std::size_t i = 0; i < _tables.size(); ++i)
        if (_tables[i] != nullptr)
            return Iterator(_tables[i], this);
    return End();
}
 
Iterator End()
{
    return Iterator(nullptr, this);
}

迭代器类别是单向迭代器。标准里 unordered_set::iterator 是 LegacyForwardIterator,只能 ++,不能 --,也不能用在 std::reverse 这类要求双向迭代器的算法上。范围 for 只需要 begin、end、!=、++,够用。

失效规则分三种:插入触发 rehash,桶数组换了,所有迭代器失效;删除某个元素,只有指向它的迭代器失效;插入没触发扩容,已有迭代器仍然有效,新结点可能插在某个链头,遍历顺序会变。边遍历边删除要先保存下一个位置,或者用 it = erase(it) 的写法。

迭代器能靠结点反推桶号,前提是哈希函数对同一个键永远给出同一个值。如果 Hash 带可变状态,比如每次调用换一个随机种子,插入时按种子 A 挂进桶,迭代器 ++ 时按种子 B 反推,就会从错误的桶继续走,遍历漏元素。标准要求哈希函数对相等的键返回相同结果,改造品也得守住这条。

标准容器还提供 iterator 到 const_iterator 的隐式转换。这里用 Ptr 和 Ref 两个模板参数分别实例化两种迭代器:begin() const 直接返回 ConstIterator,解引用得到 const T&。unordered_set 的两种迭代器解引用结果都是 const K&,因为它的 T 本身就是 const K。

const K 与 pair<const K, V>

set 的元素类型必须是 const K。元素本身就是 key,key 的哈希值决定它落在哪个桶;允许修改的话,改完哈希值对应另一个桶,元素还物理地留在旧桶,后续 find 按新值去新桶找,永远找不到。

cppreference 的 unordered_set 页面第一条就写了:容器元素不可修改,即使通过非 const 迭代器也不行,因为修改会改变哈希、破坏容器。T = const K 让这条约束在编译期生效,*it 返回 const K&,赋值直接报错。

map 的元素是 pair<const K, V>,first 是 const,second 可变。标准里 unordered_map::value_type 就写作 std::pair<const Key, T>。it->second += 'x' 合法,it->first = "xxx" 编译失败。关键字是身份,值只是内容,这个不对称是故意的。

自定义类型当键时,哈希与相等必须一致:== 比了哪几个字段,哈希就得把哪几个字段掺进去。== 只比年份、哈希却算年月日,两个“相等”的键会落进不同桶,find 永远遇不到;反过来不会查错,但同年份的键全挤进一个桶,O(1) 退化成一个链表。

标准容器还会在类内暴露 key_type、mapped_type、value_type、hasher、key_equal、allocator_type,它们都是模板参数的别名。写自己的容器时把这几个别名照抄,按标准名字取类型的泛型代码才能复用。value_type 在 set 里是 const K,在 map 里是 pair<const K, V>,这正是两个 T 的来源。

两份容器和一张表的完整代码

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
 
template<class K>
struct HashFunc
{
    std::size_t operator()(const K& key) const
    {
        return static_cast<std::size_t>(key);
    }
};
 
template<>
struct HashFunc<std::string>
{
    std::size_t operator()(const std::string& key) const
    {
        std::size_t h = 0;
        for (unsigned char ch : key)
            h = h * 131 + ch;
        return h;
    }
};
 
inline std::size_t next_prime(std::size_t n)
{
    static const std::size_t primes[] =
    {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473u, 4294967291u
    };
    const std::size_t count = sizeof(primes) / sizeof(primes[0]);
    const std::size_t* pos = std::lower_bound(primes, primes + count, n);
    return pos == primes + count ? primes[count - 1] : *pos;
}
 
template<class T>
struct HashNode
{
    T _data;
    HashNode<T>* _next;
 
    HashNode(const T& data)
        : _data(data), _next(nullptr) {}
};
 
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
 
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator
{
    using Node = HashNode<T>;
    using Self = HTIterator<K, T, Ptr, Ref, KeyOfT, Hash>;
 
    Node* _node;
    const HashTable<K, T, KeyOfT, Hash>* _pht;
 
    HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
        : _node(node), _pht(pht) {}
 
    Ref operator*() const
    {
        return _node->_data;
    }
 
    Ptr operator->() const
    {
        return &_node->_data;
    }
 
    bool operator==(const Self& other) const
    {
        return _node == other._node;
    }
 
    bool operator!=(const Self& other) const
    {
        return _node != other._node;
    }
 
    Self& operator++()
    {
        if (_node->_next != nullptr)
        {
            _node = _node->_next;
            return *this;
        }
 
        KeyOfT kot;
        Hash hs;
        std::size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
        ++hashi;
        while (hashi < _pht->_tables.size() && _pht->_tables[hashi] == nullptr)
            ++hashi;
 
        _node = (hashi == _pht->_tables.size()) ? nullptr : _pht->_tables[hashi];
        return *this;
    }
};
 
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
    template<class KK, class TT, class PP, class RR, class KOT, class HH>
    friend struct HTIterator;
 
    using Node = HashNode<T>;
 
public:
    using Iterator = HTIterator<K, T, T*, T&, KeyOfT, Hash>;
    using ConstIterator = HTIterator<K, T, const T*, const T&, KeyOfT, Hash>;
 
    HashTable()
    {
        _tables.resize(next_prime(0), nullptr);
    }
 
    ~HashTable()
    {
        Clear();
    }
 
    HashTable(const HashTable&) = delete;
    HashTable& operator=(const HashTable&) = delete;
 
    Iterator Begin()
    {
        for (std::size_t i = 0; i < _tables.size(); ++i)
            if (_tables[i] != nullptr)
                return Iterator(_tables[i], this);
        return End();
    }
 
    Iterator End()
    {
        return Iterator(nullptr, this);
    }
 
    ConstIterator Begin() const
    {
        for (std::size_t i = 0; i < _tables.size(); ++i)
            if (_tables[i] != nullptr)
                return ConstIterator(_tables[i], this);
        return End();
    }
 
    ConstIterator End() const
    {
        return ConstIterator(nullptr, this);
    }
 
    std::pair<Iterator, bool> Insert(const T& data)
    {
        KeyOfT kot;
        Iterator it = Find(kot(data));
        if (it != End())
            return std::make_pair(it, false);
 
        Hash hs;
        if (_n == _tables.size())
        {
            std::vector<Node*> newTables(next_prime(_tables.size() + 1), nullptr);
            for (std::size_t i = 0; i < _tables.size(); ++i)
            {
                Node* cur = _tables[i];
                while (cur != nullptr)
                {
                    Node* next = cur->_next;
                    std::size_t hashi = hs(kot(cur->_data)) % newTables.size();
                    cur->_next = newTables[hashi];
                    newTables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newTables);
        }
 
        std::size_t hashi = hs(kot(data)) % _tables.size();
        Node* node = new Node(data);
        node->_next = _tables[hashi];
        _tables[hashi] = node;
        ++_n;
        return std::make_pair(Iterator(node, this), true);
    }
 
    Iterator Find(const K& key)
    {
        KeyOfT kot;
        Hash hs;
        std::size_t hashi = hs(key) % _tables.size();
        for (Node* cur = _tables[hashi]; cur != nullptr; cur = cur->_next)
        {
            if (kot(cur->_data) == key)
                return Iterator(cur, this);
        }
        return End();
    }
 
    ConstIterator Find(const K& key) const
    {
        KeyOfT kot;
        Hash hs;
        std::size_t hashi = hs(key) % _tables.size();
        for (Node* cur = _tables[hashi]; cur != nullptr; cur = cur->_next)
        {
            if (kot(cur->_data) == key)
                return ConstIterator(cur, this);
        }
        return End();
    }
 
    bool Erase(const K& key)
    {
        KeyOfT kot;
        Hash hs;
        std::size_t hashi = hs(key) % _tables.size();
        Node* prev = nullptr;
        Node* cur = _tables[hashi];
        while (cur != nullptr)
        {
            if (kot(cur->_data) == key)
            {
                if (prev == nullptr)
                    _tables[hashi] = cur->_next;
                else
                    prev->_next = cur->_next;
                delete cur;
                --_n;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }
 
private:
    void Clear() noexcept
    {
        for (std::size_t i = 0; i < _tables.size(); ++i)
        {
            Node* cur = _tables[i];
            while (cur != nullptr)
            {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
        _n = 0;
    }
 
    std::vector<Node*> _tables;
    std::size_t _n = 0;
};
 
namespace bit
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
    struct SetKeyOfT
    {
        const K& operator()(const K& key) const { return key; }
    };
 
public:
    using iterator = typename HashTable<K, const K, SetKeyOfT, Hash>::Iterator;
    using const_iterator = typename HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator;
 
    iterator begin() { return _ht.Begin(); }
    iterator end() { return _ht.End(); }
    const_iterator begin() const { return _ht.Begin(); }
    const_iterator end() const { return _ht.End(); }
 
    std::pair<iterator, bool> insert(const K& key)
    {
        return _ht.Insert(key);
    }
 
    iterator find(const K& key) { return _ht.Find(key); }
    const_iterator find(const K& key) const { return _ht.Find(key); }
 
    bool erase(const K& key)
    {
        return _ht.Erase(key);
    }
 
private:
    HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
 
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
    struct MapKeyOfT
    {
        const K& operator()(const std::pair<const K, V>& kv) const { return kv.first; }
    };
 
public:
    using iterator = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::Iterator;
    using const_iterator = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::ConstIterator;
 
    iterator begin() { return _ht.Begin(); }
    iterator end() { return _ht.End(); }
    const_iterator begin() const { return _ht.Begin(); }
    const_iterator end() const { return _ht.End(); }
 
    std::pair<iterator, bool> insert(const std::pair<const K, V>& kv)
    {
        return _ht.Insert(kv);
    }
 
    V& operator[](const K& key)
    {
        std::pair<iterator, bool> ret = _ht.Insert(std::pair<const K, V>(key, V()));
        return ret.first->second;
    }
 
    iterator find(const K& key) { return _ht.Find(key); }
    const_iterator find(const K& key) const { return _ht.Find(key); }
 
    bool erase(const K& key)
    {
        return _ht.Erase(key);
    }
 
private:
    HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
 
int main()
{
    bit::unordered_set<int> s;
    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3, 3, 15};
    for (int e : a)
        s.insert(e);
 
    for (auto e : s)
        std::cout << e << ' ';
    std::cout << '\n';
 
    bit::unordered_map<std::string, std::string> dict;
    dict.insert({"sort", "排序"});
    dict.insert({"left", "左边"});
    dict["insert"] = "插入";
    dict["string"];
 
    for (auto& kv : dict)
        std::cout << kv.first << ':' << kv.second << '\n';
 
    return 0;
}

哈希表的桶里存的是裸结点指针。默认拷贝构造会复制桶数组,两个表指向同一批结点,析构时同一块内存被 delete 两次;所以实现里把拷贝构造和拷贝赋值删除了。要真的拷贝,得逐桶遍历、为每个结点 new 一份,再按新表长重新挂链。用 vector<Node> 整体复制会让结点地址变化,桶里的 _next 和外部保存的地址都会失效。课件也提醒拷贝构造和拷贝赋值需要自己实现深拷贝。

扩容条件是 _n == _tables.size(),即负载因子到 1:桶数用 next_prime(size + 1) 找下一个质数,旧结点逐个摘下、按新表长重新算桶号、头插进新桶。全程没有 new Node,结点地址不变,指向元素的引用和指针仍然有效。

erase 在标准容器里返回删除个数;set 和 map 的键唯一,返回值只能是 0 或 1。这里的接口用 bool 承接,语义等价。count 在 unordered_set 上也是 0 或 1,只有 multi 版本才可能大于 1。

课件代码里的三处顺序问题

第一处在过渡版:if (Find(kot(data)) return false;。这里的 Find 最终返回迭代器,迭代器没有到 bool 的转换,这行按最终接口编不过,必须写成 if (Find(kot(data)) != End())。

第二处在过渡版扩容:newtables(__stl_next_prime(_tables.size()))。_tables.size() 本身就是质数,next_prime 返回的还是它,新表一点没变大;下一次插入又满足 _n == _tables.size(),整张表被反复重建。参数要传 _tables.size() + 1。

第三处出现在最终版:桶号在扩容之前算好,扩容后直接拿旧下标头插。桶数从 53 变成 97 后,同一个 key 的桶号可能从 47 变成 3,结点挂到 47 号桶,Find 按新表长去 3 号桶找,找不到。顺序是“先扩容,再用新表长算桶号”。

另外,课件里 MapKeyOfT 的形参写成 const pair<K, V>&,而 T 实际是 pair<const K, V>。它能编过,是因为 std::pair 有转换构造函数,会造一个临时对象再绑定;直接写 pair<const K, V> 少一次拷贝,也和 value_type 一致。

这套封装把变化点集中到了三个位置:元素类型 T、提取 key 的 KeyOfT、迭代器里的表指针。哈希表的 Insert、Find、Erase 只认 K,桶里躺的是 K 还是 pair<const K, V>,它们不关心。set 和 map 的外壳因此只剩类型别名和几个转发函数。