unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率很高，即使最差的情况下需要红黑树的高度次，当树中的节点非常多时，查询的效率不理想；最理想的查询是：进行很少的比较次数就能够将元素找到，因此在C++11中，STL有提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同
unordered_map
介绍
unordered_map是存储键值对pair<K,V>的关联式容器，允许通过键值key快速查找到与其对应的实值value
在unordered_map中，键值通常唯一地标识元素，而映射值是一个对象，其内容与键值关联，键值和映射对象类型可能不同
在内部，unordered_map没有将键值对按照任何特定顺序进行排序（无序），为了能在常数范围内找到键值对应的实值，unordered_map将相同哈希值的键值对存放在相同的桶中
unordered_map实现了直接访问操作符operator[]，允许使用键值作为参数直接访问实值
迭代器只能向前
底层结构
unordered系列关联式容器之所以效率高，是因为底层结构是哈希，接下来深入了解这个结构
哈希概念
顺序结构和平衡树中，元素的键值与其存储的位置无关，因此在查找某一个元素时，必须通过键值进行多次比较；搜索的效率取决于搜索过程中元素的比较次数
哈希结构提供一种搜索方式：通过数组实现的结构；不经过任何比较，直接从其结构中搜索待查找的元素；通过某种函数将元素的键值与存储位置之间建立联系也就是映射关系，在查找时便可通过该函数快速找到该元素
插入元素：根据元素的键值，通过此函数计算出该元素的存储位置并存放
查找元素：对元素的键值进行同样的计算，将求得的函数值当作元素的存储位置，在结构中此位置取元素进行比较，若键值相等，则搜索成功
哈希方法中使用的转换函数称为哈希函数：hash(key)=key%size()，结构称为哈希表
例如：
int arr[]={3,6,7,1,4}
哈希函数：hash(key)=key%size()；size()存储元素底层空间的大小
哈希冲突
按照上述哈希方式，再次向表中插入元素14结果会怎样呢？？？
从图中可以发现，在表中下标为4的格子中，同时出现两个元素，此时如果进行元素查找便可能会出现问题
对于两个元素的键值通过哈希函数计算之后相等的情景称为哈希冲突
既然问题已经存在，首先是要找到解决方法，接下来慢慢揭晓
哈希函数
造成哈希冲突的其中一个原因可能是：哈希函数设计的不合理
设计原则
哈希函数的定义域必须包括要存储的全部键值，如果表中允许有 n个地址时，其值域必须在 [0,n-1]之间
哈希函数计算出的地址能均匀分布在整个表中
常见哈希函数，这里只介绍一种除留余数法
设表中允许的地址数为 n，取一个不大于 n，但最接近或者等于 n的数 p作为除数，按照哈希函数： hash(key)=key%p(p<=n)，将键值转换为哈希地址；有点类似于基数排序
哈希冲突解决方式
解决哈希冲突的两种常见方法：闭散列和开散列
闭散列
也称开放定址法，当发生哈希冲突时，如果哈希表还未被装满，表明在表中还有空余地址，便可以将冲突的键值存放到冲突位置的“下一个”空地址中；那么又该如何去寻找空地址呢？？？
这里只简单介绍一种寻找空地址的方法：线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空地址为止
插入：通过哈希函数获取待插入元素在表中的位置；当发生哈希冲突时，使用线性探测寻找下一个空地址，插入新元素
删除
采取闭散列处理哈希冲突时，不可以随便删除表中的元素，如果直接删除元素，会影响其他元素的查找；比如，直接删除元素 4，当查找元素 14时，便会显示元素不存在，但实际上该元素是存在的，所以还表中的每个地址都需要一个标记，来表示当前位置的状态
在模拟实现之前，先介绍新的概念：负载因子，即元素个数除以表格的大小，在闭散列中负载因子永远小于1，范围是 (0,1)，这样的做法是为了保障效率；一般规定负载因子的大小为 0.7，一旦超过此大小，哈希表便需要进行扩容
//标识位置的状态 enum State { EXIST, EMPTY, DELETE, }; //表中每个位置的结构 template<class K,class V> struct Hashnode { pair<K, V> _kv; State _state = EMPTY; }; //表的结构 template<class K,class V,class Hash=HashFunc<K>> class Hashtable { typedef Hashnode<K, V> Data; public: Hashtable() :_n(0) { _table.resize(10); } Data* find(const K& key) { Hash hf; size_t hashi = hf(key) % _table.size(); while (_table[hashi]._state != EMPTY) { if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) { return &_table[hashi]; } hashi++; hashi %= _table.size(); } return nullptr; } bool insert(const pair<K, V>& kv) { if (find(kv.first)) { return false; } //大于规定负载因子，扩容 if (_n * 10 / _table.size() >= 7) { //旧表的元素，重写计算，映射到新表中 Hashtable<K, V, Hash> newht; newht._table.resize(_table.size() * 2); for (auto& e : _table) { if (e._state == EXIST) { newht.insert(e._kv); } } _table.swap(newht._table); } Hash hf; size_t hashi = hf(kv.first) % _table.size(); while (_table[hashi]._state == EXIST) { //线性探测 ++hashi; hashi %= _table.size(); } _table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n; return true; } bool erase(const K& key) { Data*ret=find(key); if(ret) { ret->_state=DELETE; --_n; return true; } else { return false; } private: vector<Data> _table; size_t _n = 0;//表中存储元素的有效个数 };
测试
void test() { int arr[] = { 3,6,7,1,4,14}; Hashtable<int, int>ht; for (auto e : arr) { ht.insert(make_pair(e,e)); } }
运行结果
上面的测试对象是整型数组，当遇到字符串又该如何呢？？？
由于哈希只能处理整型，所以需要将字符串转换成整型，之后再通过哈希函数计算位置进行各种操作；采取仿函数 HashFunc()来将各种数据类型转换成整型，也就是为什么在创建Hashtable类时模板中存在 class Hash=HashFunc<K>缺省值的原因
template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; //特化 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto e : key) { e *= 131; hash += e; } return hash; } };
总结
线性探测的优点：实现起来非常简单
线性探测的缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积，从而导致效率降低
开散列
又称地址法，首先对键值通过哈希函数计算位置，具有相同的位置的键值归于同一个子集，每一个子集称为一个桶，每个桶中的元素通过一个单链表连接起来，每个链表的头节点存储在哈希表中；此时的哈希表就是一个指针数组，此结构也称哈希桶
从上图可以发现，开散列中每个桶中存放的都是发生哈希冲突的元素；开散列的负载因子一般规定不超过1，一旦超过便会进行扩容操作
template<class K, class V> struct Hashnode { pair<K, V> _kv; Hashnode<K, V>* _next; Hashnode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) { } }; template<class K, class V, class Hash = HashFunc<K>> class Hashbucket { typedef Hashnode<K, V> node; public: Hashbucket() :_n(0) { _table.resize(10); } ~Hashbucket() { for (size_t i = 0; i < _table.size(); i++) { node* cur = _table[i]; while (cur) { node* next = cur->_next; delete cur; cur = next; } _table[i] = nullptr; } } node* find(const K& key) { size_t hashi = Hash()(key) % _table.size(); node* cur = _table[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } else { cur = cur->_next; } } return nullptr; } bool insert(const pair<K, V>& kv) { if (find(kv.first)) { return false; } if (_table.size() == n) { vector<node*> newtable; newtable.resize(2 * _table._size()); for (size_t i = 0; i < _table.size(); i++) { while (cur) { node* next = cur->_next; size_t hashi = Hash()(cur->_kv.first) % _table.size(); //头插到新表 cur->_next = newtable[hashi]; newtable[hashi] = cur; cur = next; } _table[i] = nullptr; } _table.swap(newtable); } size_t hashi = Hash()(kv.first) % _table.size(); node* newnode = new node(kv); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return true; } bool erase(const K& key) { size_t hashi = Hash()(key) % _table.size(); node* prev = nullptr; node* cur = _table[hashi]; while (cur) { if (cur->_kv.first = key) { //准备删除 //没有哈希冲突 if (cur == _table[hashi]) { _table[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } else { prev = cur; cur = cur->_next; } } return false; } private: vector<node*> _table; size_t _n = 0;//表中存储元素的有效个数 };
测试
void test() { int arr[] = { 3,6,7,1,4,14 }; Hashtable<int, int>ht; for (auto e : arr) { ht.insert(make_pair(e, e)); } }
运行结果
闭散列和开散列的比较
应用地址法处理哈希冲突，需要增设链表指针，似乎增加了存储开销；实际上：由于地址法必须保持大量的空闲空间以确保搜索效率，而哈希表所占空间又比指针大得多，所以开散列比闭散列更加地节省存储空间
