一、源码及框架分析
SGI-STL30 版本源代码中没有 unordered_map 和 unordered_set，SGI-STL30 版本是 C++11 之前的 STL 版本，这两个容器是 C++11 之后才更新的。但是 SGI-STL30 实现了哈希表，只容器的名字是 hash_map 和 hash_set，他是作为非标准的容器出现的，非标准是指非 C++ 标准规定必须实现的，源代码在 hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h 中 hash_map 和 hash_set 的实现结构框架核心部分截取出来如下：
// stl_hash_set
template<class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = alloc>
class hash_set {
private:
typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
};
// stl_hash_map
template<class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc>
class hash_map {
private:
typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class hashtable {
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*, Alloc> buckets;
size_type num_elements;
public:
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
pair<iterator, bool> insert_unique(const value_type& obj);
const_iterator find(const key_type& key) const;
};
template<class Value>
struct __hashtable_node {
__hashtable_node* next;
Value val;
};
- 这里我们就不再画图分析了，通过源码可以看到，结构上 hash_map 和 hash_set 跟 map 和 set 的完全类似，复用同一个 hashtable 实现 key 和 key/value 结构，hash_set 传给 hash_table 的是两个 key，hash_map 传给 hash_table 的是 pair<const key, value>。
- 需要注意的是源码里面跟 map/set 源码类似，命名风格比较乱，这里比 map 和 set 还乱，hash_set 模板参数居然用的 Value 命名，hash_map 用的是 Key 和 T 命名。下面我们模拟一份自己的出来，就按自己的风格走了。
二、模拟实现 unordered_map 和 unordered_set
1、实现出复用哈希表的框架，并支持 insert
- 参考源码框架，unordered_map 和 unordered_set 复用之前我们实现的哈希表。
- 我们这里相比源码调整一下，key 参数就用 K，value 参数就用 V，哈希表中的数据类型，我们使用 T。
- 其次跟 map 和 set 相比而言 unordered_map 和 unordered_set 的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为 HashTable 实现了泛型不知道 T 参数导致是 K，还是 pair<K, V>，那么 insert 内部进行插入时要用 K 对象转换成整形取模和 K 比较相等，因为 pair 的 value 不参与计算取模，且默认支持的是 key 和 value 一起比较相等，我们需要时的任何时候只需要比较 K 对象，所以我们在 unordered_map 和 unordered_set 层分别实现一个 MapKeyOfT 和 SetKeyOfT 的仿函数传给 HashTable 的 KeyOfT，然后 HashTable 中通过 KeyOfT 仿函数取出 T 类型对象中的 K 对象，再转换成整形取模和 K 比较相等，具体细节参考如下代码实现。
// MyUnorderedSet.h
namespace xz {
template <class K, class Hash = HashFunc<K>>
class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) { return key; }
};
public:
bool insert(const K& key) { return _ht.Insert(key); }
private:
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}
// MyUnorderedMap.h
namespace xz {
template <class K, class V, class Hash = HashFunc<K>>
class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
public:
bool insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
// HashTable.h
template <class K>
struct HashFunc {
size_t operator()(const K& key) { return (size_t)key; }
};
namespace hash_bucket {
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 {
typedef HashNode<T> Node;
inline unsigned long __stl_next_prime(unsigned long n) {
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_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, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
public:
HashTable() { _tables.resize(__stl_next_prime(_tables.size()), nullptr); }
~HashTable() {
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
bool Insert(const T& data) {
KeyOfT kot;
if (Find(kot(data))) return false;
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();
// 负载因子==1 扩容
if (_n == _tables.size()) {
vector<Node*> newtables(__stl_next_prime(_tables.size()), nullptr);
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hs(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
}
2、支持 iterator 的实现
iterator 核心源代码
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
node* cur;
hashtable* ht;
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>& __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++() {
const node* old = cur;
cur = cur->next;
if (!cur) {
size_type bucket = ht->bkt_num(old->val);
while (!cur && ++bucket < ht->buckets.size()) cur = ht->buckets[bucket];
}
return *this;
}
iterator 实现思路分析
- iterator 实现的大框架跟 list 的 iterator 思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
- 这里的难点是 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点是反而是结构设计的问题，参考上面的源码，我们可以看到 iterator 中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶即可。
- begin() 返回第一个桶中第一个节点指针构造的迭代器，这里 end() 返回迭代器可以用空表示。
- unordered_set 的 iterator 也不支持修改，我们把 unordered_set 的第二个模板参数改成 const K 即可，
HashTable<K, const K, SetKeyOfT, Hash> _ht; - unordered_map 的 iterator 不支持修改 key 但是可以修改 value，我们把 unordered_map 的第二个模板参数 pair 的第一个参数改成 const K 即可，
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht; - 支持完整的迭代器还有很多细节需要修改，具体参考下面的代码。
3、map 支持 []
- unordered_map 要支持 [] 主要需要修改 insert 返回值支持，修改 HashTable 中的 insert 返回值为
pair<Iterator, bool> Insert(const T& data)。 - 有了 insert 支持 [] 实现就很简单了，具体参考下面 4 的代码实现。
V& operator[](const K& key) {
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
4、xz::unordered_map 和 xz::unordered_set 代码实现
完整代码可参考相关开源仓库实现。