一、了解

1、unordered_map(哈希)

unordered_map是借用哈希表實現的關聯容器。

• 訪問鍵值對O（1），最壞情況O（n），例如哈希沖突嚴重時。【n是一個哈希桶的元素數量】

• unordered_map特性

  • 鍵值對存儲：（key-value）每一個鍵對應一個值
  • 無序：元素順序取決于哈希函數和元素添加順序。
  • 哈希表表現：哈希表實現。鍵用哈希函數生成對應的索引。
  • 自定義哈希函數和相等函數：可以自己定義函數。

• unordered_map 性能

  • 哈希沖突解決方法：鏈表或其他數據結構解決沖突。

  • 如下圖：
    
    

  • 負載因子和重哈希：

    • 負載因子：已存儲元素數量 / 桶的總數量。。【一般為 1 】觸發哈希表擴容（rehash）。
    • 重哈希：當加載因子超過要求，就要重新分配元素并增加哈希桶數量。以保持高效性。

  • 內存開銷：哈希表需要額外內存管理桶，可能比紅黑樹占用更多總內存。

• 常見問題：

• 1、如何處理unordered_map中的哈希沖突？

  • unordered_map處理哈希沖突的一種常見方法是鏈地址法，即在沖突發生時，所有具有相同哈希值的元素會被存儲在同一個哈希桶的鏈表中。當查找一個鍵時，首先會使用哈希函數計算其哈希值，定位到對應的桶，然后通過遍歷鏈表來查找具有相應鍵的元素。

• 2、unordered_map的性能瓶頸在哪里？

  • 重哈希操作成本很高。如果使用的負載因子超出要求。發生重哈希，就容易出現瓶頸。

• 3、如何優化性能瓶頸？

  • 可以自定義哈希函數，使用質量更好的哈希函數，減少哈希沖突。負載因子低了會導致內存消耗大，負載因子打了就容易沖突。所以，當知道需要存儲的元素時，提前使用reserve預分配空間，減少重哈希。

• 使用的頭文件

#include <unordered_map>

二、初始化

unordered_map<KeyType, ValueType> myMap;
鍵類型 KeyType：必須支持 < 運算符，或傳入自定義比較函數。
值類型 ValueType：任意類型（包括自定義類型）。

int main(){pair<int,int>pair1={1,2};pair<int,int>pair2=make_pair(1,2);unordered_map<int ,int>unorderedmap1={{1,2},{1,2}};unordered_map<int ,int>unorderedmap2={pair1,pair2};unordered_map<int ,int>unorderedmap3(unorderedmap2);unordered_map<int ,int>unorderedmap4=unorderedmap3;unordered_map<int ,int>unorderedmap5{pair<int,int>(1,2)};
}

三、自定義哈希函數

• 首先了解
• 負載因子（load factor）：已存儲元素數量 / 桶的總數量。
  • 默認當負載因子超過 max_load_factor()（通常為 1.0）時觸發哈希表擴容（rehash）。
• 調整桶的數量方法 ，如下：

scores.rehash(50);      // 預分配至少容納 50 個元素的桶
scores.reserve(100);    // 預分配至少 100 個元素的容量（更友好）

• 手動設置哈希函數 , 例如：

// 示例：自定義類的哈希函數
struct Person {string name;int id;
};// 定義哈希函數
struct PersonHash {size_t operator()(const Person& p) const {return hash<string>()(p.name) ^ hash<int>()(p.id);}
};// 定義相等比較
struct PersonEqual {bool operator()(const Person& a, const Person& b) const {return a.name == b.name && a.id == b.id;}
};// 使用自定義類型的 unordered_map
unordered_map<Person, int, PersonHash, PersonEqual> customMap;

四、常用函數

1、總結

2、例子

• 首先是這里用的頭文件

#include <iostream>
#include<unordered_map>
#include <utility>
using namespace std;

2.1、插入操作

• insert({key-value})
  • 插入鍵值

int main(){unordered_map<int,int>m;m.insert({1,2});for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//1 2}
}

• insert(pair)
  • 插入pair

int main(){pair<int,int>p={1,2};unordered_map<int,int>m;m.insert(p);for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//1 2}
}

• insert(other_unordered_map_first，other_unordered_map_end)
  • 插入另一個哈希map

int main(){unordered_map<int,int>m;unordered_map<int,int>tmp{{2,3},{2,3}};m.insert(tmp.begin(),tmp.end());for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//2 3}
}

• inserrt(pos , {key-value})
  • 在pos插入鍵值

int main(){unordered_map<int,int>m={{1,2}};m.insert(m.begin(),{3,4});for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//3 4//1 2}
}

2.2、刪除操作

• erase(first , end)
  • 刪除當前這個map 在這個范圍內的鍵值對

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};m.erase(m.begin(),++m.begin());for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//2 3//1 2}
}

• erase(pos)
  • 刪除pos的鍵值對

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};m.erase(m.begin());for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//2 3//1 2}
}

2.3、訪問操作

• [key]運算符
  • 查key對應的值

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m[1]<<endl;//2}

• at(key)
• 查key對應的值

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m.at(1)<<endl;//2}

• begin()
  • 返回第一個

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m.begin()->first<<endl;//3cout<<m.begin()->second<<endl;//4
}

• end()
  • 返回最后一個

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m.end()->first<<endl;//cout<<m.end()->second<<endl;//
}

2.4、查詢操作

• find(key)
  • 找key鍵值的位置

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};auto i =m.find(1);cout<<i->first<<endl; //1cout<<i->second<<endl;//2
}

• count(key)
  • 找key的鍵值數量

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};auto i =m.count(1);cout<<i<<endl; //1}

2.5、容量操作

• size()
  • 查找map的數量

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};int num = m.size();cout<<num<<endl; //3}

• empty
  • 當前map是否為空

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};if(m.empty()==1){cout<<"m是空的"<<endl;}else{cout<<"m不是空的"<<endl;}//m不是空的}

2.6、交換操作

• swap(other_unordered_map)
  • 交換2個map

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};unordered_map<int,int>s={{3,4}};m.swap(s);for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//3 4}
}