unordered_map的实现-hashmap_c++ unordermap hash的实现

C++STL中map包含两大类

• map:采取红黑树方式，map中的元素有序，读写都是O(LogN)的时间复杂度
• unordered_map:元素无序，采取hashmap的实现方式，即连续存放的桶，数组+链表方式，一般的认为读写都是O(1)复杂度

unordered_map是典型的采取空间换时间的方式达到一个良好的性能，

• 初始化一定大小的vector(连续存储的数组)vector中index位置下标元素为一个bucket(桶)
• 针对一个（key,value）根据hash函数（常见的如 取模%）定位到所在的index位置，
• 然后在bucket的中进行查找或者插入，具体实现为当元素个数较少时，采取List方式，较多时采取红黑树存储冲突的节点

构造函数：

   HashMap(int size = 4, double loadFactor = 0.75) : mLoadFactor(loadFactor), mBucketNum(0)
    {
        mHashMap.resize(size);//调整为size初始化大小
    }

首先是hashmap的空间问题，一种较优的做法是其空间大小为2的倍数，而根据Key  采取以下的方式定位

index=(len-1)&key   其中len为hashmap的大小  即vector的大小 总共桶的数量

如4大小的空间   key=5    那么按位与运算如下： 101&11 =》 01 即存放在index=1位置

 
    int idx(int key)
    {
       
        return (mHashMap.size() - 1)& key;
 
    }

 另外一点是扩容问题，当已经使用的桶的数量超过总数量的一定比例时，按照一定的倍数（常见的设定为2）扩大桶的总数

称为扩容因子： loadFactor   其不能过小，否则造成过早扩容，也不能过大，造成扩容不及时。

一般设定大小为0.75                               因此 load=use_bucketnum/hashmap.size()  > loadFactor ?  resize:do_nothing

由于总的桶的数目增加两倍，原先index位置的元素可能在新的空间中仍然是index 也可能是 index+原先桶的总数

（将原先存在内容的桶分散到 两部分（旧的部分、新的部分））

    void expand()
    {
       
        vector < list<Pair<K,V>>> oldHashMap;
        mHashMap.swap(oldHashMap);//将原先的hashmap先转移出
        mHashMap.resize(oldHashMap.size()*2);
        for (int i = 0; i < oldHashMap.size(); i++)