unordered_map&&unordered_set

底层实现

​ 在STL中，C++11引入了unordered_map、unordered_set、unordered_multimap、unordered_multimap。尽管不是名字不是哈希表，但是底层仍然是。相比于map等，这个查找的平均时间更加快。看看它的底层实现（l来自《STL源码剖析》）：

//以下是基于gnu2.9版本的提取的
template<class Value, class Key, class HashFcn, 
         class ExtractKey, class EqualKey, 
         class Alloc=alloc>
class hashtable{
    public:
        typedef HashFcn hasher;
        typedef EqualKey Key_equal;
        typedef size_t size_type;
   private:
        hasher hash;//哈希函数（可以是函数指针或函数对象（仿函数），返回值需要是bool值）
        key_equal equals;//key的判断相等函数（可以是函数指针或函数对象（仿函数）返回值需要是bool值）
        ExtractKey get_key;//key的提取函数，从value_type中提取出key

        typedef _hashtable_node<Value> node;

        vector<node*，Alloc> buckets;//存储桶，可见后面的图示
        size_type num_elements;//存储桶的数量
    public:
        size_type bucket_count() const { return buckets.size()}
    ……
};
template<class Value>
struct _hashtable_node{
    _hashtable_node* next;
    Value val;
};
//hashtable的迭代器设计
template<class Value, class Key, class HashFcn, 
         class ExtractKey, class EqualKey, 
         class Alloc>
struct _hashtable_iterator{
    ……
    node* cur;
    hashtable* ht;
};      


//GNU 7.2.0 中重新分解了各种容器的实现细节。此处贴出unordered_map的模板参数部分，也就是我们经常使用的。
template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;
//7.2.0版本已经有默认的hash函数（根据key类型选择的hash函数），只需要定义key与value类型即可。

内存结构：类似deque的分段存储。采用链地址法解决冲突。

构造、析构、赋值

构造

上述的size_type n；均是指定指数据桶的数量。初始化一个哈希表的时候注意以下数据桶的数量，数据多，而数据桶少，就会使得查找效率更低。

析构

~unordered_map();

赋值

迭代器与容器大小

​ 通过迭代器访问的是值类型。注意unordered_map的值类型是pair<Key,Value>。而unordered_set的值类型就是Key。另外，unordered_map是forward_iterator_tag。单链表类似的访问方式。

​

修改

各个操作无论是传入参数，还是返回值与map类似。

notes：

对于unorder_map,每个数据桶只能装一个元素。

对于extract:(唯一一种改变元素key值而不需要重新申请内存分配的，要使用move)

extract is the only way to change a key of a map element without reallocation。

merge:从source中提取不同key的元素（是对于* this的hash函数以及key相等函数的意义上的key不同）。* this与source要求分配器类型是一致的。

另外，无论是insert，emplace等，他们如果增加了元素。会在当前size()>最大装载因子*数据桶数量的时候进行rehash。rehash的意思是：增大数据桶的数量。装载因子等于

查询

在unordered_multimap中无at，operator[ ]。

数据桶信息

哈希策略

一些仿函数

与unordered_set等的关系

​ 就像map与set一样，unordered_map与unordered_set之间最要注意的区别就是值类型不一致，一个是pair<key,map_type>，另外一个key类型就是值类型。而unordered_map与unordered_multimap，unordered_map要求相同的key的元素只有一个，而unordered_multimap,就可以有多个相同的key元素。

Reference

[1] https://www.bilibili.com/video/av45108908

[2]http://www.cplusplus.com/reference/unordered_map/

[3]候捷,《STL源码剖析》