目录

1.unordered_map和unordered_set简介

2.unordered_map和unordered_set设计图

3.迭代器的设计

4.哈希表的设计

5.my_unordered_map和my_unordered_set代码

1.unordered_map和unordered_set简介

unordered_map和unordered_set的使用非常类似于map和set，两者之间的差异在于底层的数据结构不同，unordered_map和unordered_set的底层使用的数据结构是哈希表，map和set底层使用的数据结构是红黑树。哈希表和红黑树都是查找效率非常高的数据结构，红黑树的查找效率是O(logN)，哈希表的查找效率是O(1)，总体来说哈希表的查找效率略胜一筹，但是红黑树是接近平衡的二叉搜索树，具有隐藏技能 —— 中序遍历，数据有序(升序)，map和set的遍历采用的就是中序遍历；也就是说，遍历map和set得到的数据是有序的，而哈希表的遍历是无序的，所以，为了区分功能相同而底层数据结构的不同的关联式容器，以哈希表为底层数据结构的map和set前加上unordered，unordered其实就是无序的意思。

2.unordered_map和unordered_set设计图

unordered_map和unordered_set底层是开散列方式实现的哈希表，要想实现unordered_map和unordered_set，需要在内部封装哈希表；但是，STL中的容器都提供统一的访问方式 —— 迭代器，所以我们还需要实现unordered_map和unordered_set的迭代器。说白了，unordered_map和unordered_set就是通过组合 哈希表 和 迭代器 来实现的。而unordered_map和unordered_set实现上的区别就是内部存储的数据不同(一个存储键值对，一个存储元素本身)，但是整体的设计框架是相同的。

unordered_map和unordered_set的设计图如下：

一个问题：unordered_map中存储的是键值对，unordered_set中存储的是一个个的元素，而二者的底层使用的数据结构都是 开散列实现的哈希表，那我们需要将哈希表实现两份吗？这个问题和map和set中数据存储的问题相同，如果实现两份的话，就会造成代码重复和冗余；解决方案也是和map、set中解决该问题的方式相同。请看下图：

可以看出，在使用上，unordered_set传递一个模板参数，unordered_map传递两个模板参数，但是在unordered_map和unordered_set中封装的哈希表都需要传递两个参数；所以unordered_map中将K类型传给底层哈希表的第一个参数，用 K 和 V封装出pair<K,V>类型传给 底层哈希表的第二个参数；unordered_set中传递给底层哈希表的第一个和第二个参数的类型都是K。这样，哈希表中第二个模板参数T就是哈希表中实际存储的数据类型。于是，就实现了复用同一个 哈希表的类模板。

那第一个模板参数是不是没用呢？并不是，因为，unordered_map和unordered_set的使用上是以Key值  (K类型的数据) 为主的，并且有些操作也是根据Key值来进行的，比如：查找操作。所以我们也是需要单独的K类型的数据的。

获取数据中的Key值问题

由于同一个类模板的哈希表中经常涉及数据的比较，unordered_set中数据的比较是按照Key值来比较的，unordered_map中数据的比较也是按照Key值来比较的。但是在同一个类模板的哈希表中不能使用同样的方式获取Key值，所示实现一个获取Key值的仿函数，该仿函数作为参数传递给哈希表。

实现代码如下：

<code>// unordered_map中获取Key值的仿函数

struct MapKeyOfT

{

const K& operator()(const pair<K, V>& kv)

{

return kv.first;

}

};

// unordered_set中获取Key值的仿函数

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

3.迭代器的设计

unordered_map和unordered_set迭代器的设计不同于map和set，map和set的迭代器的操作主要是是在一棵二叉搜索树上进行，所以封装结点的指针即可；但是unordered_map和unordered_set的迭代器的操作是在哈希表上进行的，而哈希表是由 _table 和 _table下挂的一个个的结点组成的，所以 unordered_map 和 unordered_set 的迭代器需要封装 哈希表 和 结点的指针 (对于哈希表的封装，也采用指针的形式) 。

迭代器总体设计图如下：

迭代器的那些操作

operator* 和 operator->操作：迭代器模仿的是指针的操作，指针常用的操作就是 解引用 * 和 箭头访问操作符 ->；operator* 用于取出结点中的数据，operator->用于返回节点中数据的地址。代码如下：

<code>T& operator*()

{

return _node->_data;

}

T* operator->()

{

return &(_node->_data);

}

迭代器的++操作：迭代器的++操作用于实现 用迭代器遍历哈希表中的数据，所以我们需要依次遍历桶，如果桶不为空，就遍历桶中的数据，遍历完当前桶中的数据之后，再遍历下一个桶中的数据；如果桶为空，直接遍历下一个桶；迭代器++操作代码如下：

Self& operator++()

{

if (_node->_next)

{

// 当前桶还是节点

_node = _node->_next;

}

else

{

// 当前桶走完了，找下一个桶

KeyOfT kot;

Hash hs;

size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();

// 找下一个桶

hashi++;

while (hashi < _ht->_tables.size())

{

if (_ht->_tables[hashi])

{

_node = _ht->_tables[hashi];

break;

}

hashi++;

}

// 后面没有桶了

if (hashi == _ht->_tables.size())

{

_node = nullptr;

}

}

return *this;

}

判断相等和不相等操作：迭代器判断相等和不相等，只需要判断迭代器中 结点的指针是否相等。代码如下所示：

bool operator!=(const Self& s)

{

return _node != s._node;

}

bool operator==(const Self& s)

{

return _node == s._node;

}

4.哈希表的设计

哈希表的实现有闭散列和开散列两种方式，我们采用开散列的方式实现，哈希表的设计图如下所示：

哈希函数

哈希表主要通过哈希函数来计算出 存储的数据 和 数据存储的位置 之间的映射关系。在该设计中，我们采用 除留余数法 来计算 存储元素 和 存储位置 之间的映射关系；但是，该方法只适用于整形的数据，因为并不是所有类型的数据都能进行取余运算，所以，对于一些不能取余的类型的数据，我们需要提供一个仿函数来计算出其哈希值，方便其进行取余运算，从而计算出数据的存储位置。

哈希函数示例代码如下：

<code>template<class K>

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

// 特化

template<>

struct HashFunc<string>

{

size_t operator()(const string& s)

{

size_t hash = 0;

for (auto e : s)

{

hash += e;

hash *= 131;

}

return hash;

}

};

哈希表中的操作

begin()和end()操作：begin()用于返回哈希表中第一个结点的迭代器，end()用于返回最后一个结点的下一个位置的迭代器，其实就是空。

代码实现如下：

iterator begin()

{

for (size_t i = 0; i < _tables.size(); i++)

{

// 找到第一个桶的第一个节点

if (_tables[i])

{

return iterator(_tables[i], this);

}

}

return end();

}

iterator end()

{

return iterator(nullptr, this);

}

数据的插入：哈希表中插入数据是哈希表的精髓，因为数据的插入位置和数据之间通过哈希函数建立一 一映射的关系，通过数据的值，就可以很快的判断出数据存储的位置；并且通过限制负载因子来防止桶中的数据过多，从而为飞速的查找效率打下基础。

开散列的哈希表中的数据的插入采用头插的方式，代码实现如下：

bool Insert(const T& data)

{

KeyOfT kot;

if (Find(kot(data)))

return false;

Hash hs;

// 负载因子到1就扩容

if (_n == _tables.size())

{

vector<Node*> newTables(_tables.size() * 2, 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);

}

size_t hashi = hs(kot(data)) % _tables.size();

Node* newnode = new Node(data);

// 头插

newnode->_next = _tables[hashi];

_tables[hashi] = newnode;

++_n;

return true;

}

数据的查找：在哈希表中查找一个值，首先通过哈希函数计算出该元素在哈希表中的第几个桶，然后遍历该桶下的数据，找到了就返回该结点的地址，没找到就返回空。

代码如下：

Node* Find(const K& key)

{

KeyOfT kot;

Hash hs;

size_t hashi = hs(key) % _tables.size();

Node* cur = _tables[hashi];

while (cur)

{

if (kot(cur->_data) == key)

{

return cur;

}

cur = cur->_next;

}

return nullptr;

}

数据的删除：删除一个数据的时候，首先要找到该数据所在的结点，找到该结点之后，删除即可。如果不存在该数据，则返回false。

删除代码如下：

bool Erase(const K& key)

{

KeyOfT kot;

Hash hs;

size_t hashi = hs(key) % _tables.size();

Node* prev = nullptr;

Node* cur = _tables[hashi];

while (cur)

{

if (kot(cur->_data) == key)

{

// 删除

if (prev)

{

prev->_next = cur->_next;

}

else

{

_tables[hashi] = cur->_next;

}

delete cur;

--_n;

return true;

}

prev = cur;

cur = cur->_next;

}

return false;

}

5.my_unordered_map和my_unordered_set代码

my_unordered_map代码如下：

#include "Open_HashTable.h"

namespace wall

{

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:

typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

bool insert(const pair<K, V>& kv)

{

return _ht.Insert(kv);

}

bool erase(const K& key)

{

_ht.Erase(key);

}

iterator find(const K& key)

{

Node* ret = Find(key);

return iterator(ret);

}

private:

hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;

};

}

my_unordered_set代码如下：

#include "Open_HashTable.h"

namespace wall

{

template<class K, class Hash = HashFunc<K>>

class unordered_set

{

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

public:

typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

bool insert(const K& key)

{

return _ht.Insert(key);

}

bool erase(const K& key)

{

_ht.Erase(key);

}

iterator find(const K& key)

{

Node* ret = Find(key);

return iterator(ret);

}

private:

hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;

};

}

总结：可以看出，模拟实现的unordered_map和unordered_set主要是对 哈希表 和 迭代器进行了组合和封装，通过添加一些操作来更加方便的使用底层的数据结构。