用哈希表封装unordered_map与unordered_set

哈希表封装unordered_map与unordered_set

• 1. 源码及框架分析
• 2. 模拟实现unordered_map和unordered_set
• • 2.1 实现出复⽤哈希表的框架，并⽀持insert
  • 2.2 ⽀持iterator的实现
  • 2.3 map⽀持[]
  • 2.4 TSY::unordered_map和TSY::unordered_set代码实现

1. 源码及框架分析

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_settemplate <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_maptemplate <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.htemplate <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
• 需要注意的是源码⾥⾯跟map/set源码类似，命名⻛格⽐较乱，这⾥⽐map和set还乱，hash_set模板参数居然⽤的Value命名，hash_map⽤的是Key和T命名，可⻅⼤佬有时写代码也不规范，乱弹琴。下⾯我们模拟⼀份⾃⼰的出来，就按⾃⼰的⻛格⾛了。

2. 模拟实现unordered_map和unordered_set

2.1 实现出复⽤哈希表的框架，并⽀持insert

• 参考源码框架，unordered_map和unordered_set复⽤之前我们实现的哈希表。
• 我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，哈希表中的数据类型，我们使⽤T。
• 其次跟map和set相⽐⽽⾔unordered_map和unordered_set的模拟实现类结构更复杂⼀点，但是⼤框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K，还是pair，那么insert内部进⾏插⼊时要⽤K对象转换成整形取模和K⽐较相等，因为pair的value不参与计算取模，且默认⽀持的是key和value⼀起⽐较相等，我们需要时的任何时候只需要⽐较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K⽐较相等，具体细节参考如下代码实现。

// MyUnorderedSet.hnamespace bit{ 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, K, SetKeyOfT, Hash> _ht;};}// MyUnorderedMap.hnamespace bit{ template<class K, class V, class Hash = HashFunc<K>>class unordered_map{ struct