C++標(biāo)準(zhǔn)庫中有關(guān)哈希表的類
C++標(biāo)準(zhǔn)庫提供了一個哈希表（Hash Table）實現(xiàn)的關(guān)聯(lián)容器，即 unordered_map 類。除了 unordered_map，還有其他與哈希表相關(guān)的類和函數(shù)，下面是它們的詳細(xì)介紹：
-
unordered_map類：-
unordered_map是一個關(guān)聯(lián)容器，用于存儲鍵值對，并基于哈希表實現(xiàn)快速的鍵值查找。 - 它支持插入、刪除和查找操作的平均時間復(fù)雜度為常數(shù)時間（O(1)）。
- 鍵和值可以是任意類型。
- 提供了許多成員函數(shù)，包括
insert、erase、find、size、empty等，用于操作和管理哈希表。 - 頭文件：
<unordered_map> - unordered_map 中的每個鍵是唯一的，而值可以重復(fù)。當(dāng)你插入一個新的鍵值對時，如果鍵已經(jīng)存在于 unordered_map 中，則新的值將覆蓋舊的值。這樣確保了每個鍵在 unordered_map 中只對應(yīng)一個值。
-
-
unordered_multimap類：-
unordered_multimap類與unordered_map類類似，但允許鍵重復(fù)。 - 即可以存儲多個鍵相同的鍵值對。
- 提供了與
unordered_map類相似的成員函數(shù)。 - 頭文件：
<unordered_map>
-
-
unordered_set類：-
unordered_set是一個存儲唯一元素的集合，基于哈希表實現(xiàn)快速的元素查找。 - 不保存重復(fù)的元素。
- 提供了插入、刪除和查找操作的平均時間復(fù)雜度為常數(shù)時間（O(1)）。
- 頭文件：
<unordered_set>
-
-
unordered_multiset類：-
unordered_multiset類與unordered_set類類似，但允許重復(fù)的元素。 - 可以存儲多個相同的元素。
- 提供了與
unordered_set類相似的成員函數(shù)。 - 頭文件：
<unordered_set>
-
-
hash函數(shù)對象：-
hash函數(shù)對象是一個用于計算哈希值的函數(shù)對象。 - 它可以通過在
unordered_map或unordered_set中使用自定義類型作為鍵時，提供哈希函數(shù)。 - 默認(rèn)情況下，C++ 標(biāo)準(zhǔn)庫已經(jīng)為常見的基本類型（例如整數(shù)、浮點數(shù)）和字符串類型提供了哈希函數(shù)。
- 如果要在自定義類型中使用哈希表，可以通過特化
std::hash結(jié)構(gòu)來提供自定義的哈希函數(shù)。
-
代碼講解
以下代碼實現(xiàn)了一個名為 RandomizedSet 的類，該類提供了常數(shù)時間復(fù)雜度的插入、刪除和獲取隨機元素的操作。
class RandomizedSet {
public:
RandomizedSet() {
srand((unsigned)time(NULL));
}
bool insert(int val) {
if (indices.count(val)) {
return false;
}
int index = nums.size();
nums.emplace_back(val);
indices[val] = index;
return true;
}
bool remove(int val) {
if (!indices.count(val)) {
return false;
}
int index = indices[val];
int last = nums.back();
nums[index] = last;
indices[last] = index;
nums.pop_back();
indices.erase(val);
return true;
}
int getRandom() {
int randomIndex = rand()%nums.size();
return nums[randomIndex];
}
private:
vector<int> nums;
unordered_map<int, int> indices;//存儲整數(shù)鍵和整數(shù)值的哈希表
};
哈希表在此的作用
在上述代碼中，unordered_map<int, int> indices; 是一個用于存儲值與其在 nums 中的索引之間的映射關(guān)系的容器。
這個映射關(guān)系的作用是為了實現(xiàn)以下兩個功能：
快速查找給定值在 nums 中的索引：通過在 indices 哈希表中查找給定值，可以快速獲取該值在 nums 中的索引，而不需要遍歷整個 nums 容器。
判斷給定值是否存在于 nums 中：通過在 indices 哈希表中查找給定值，可以快速判斷該值是否存在于 nums 中。unordered_map 的底層實現(xiàn)使用哈希表，具有快速的查找性能，平均情況下的查找時間復(fù)雜度為 O(1)。
對比內(nèi)置的數(shù)組：通過索引可以快速獲取值，但無法通過值快速獲取索引（必須遍歷）；而哈希表則實現(xiàn)了通過值快速獲取索引。
unordered_map 的關(guān)鍵成員函數(shù)
-
insert函數(shù)：-
iterator insert(const value_type& value)或iterator insert(value_type&& value) - 插入一個鍵值對到
unordered_map中。 - 接受一個鍵值對
value作為參數(shù)，可以是pair對象或通過構(gòu)造value_type創(chuàng)建。也可以直接通過類似數(shù)組的下標(biāo)進行插入,如果存在則值覆蓋，不存在則創(chuàng)建，例如:
-
indices.insert(std::make_pair(val, index));// `pair` 對象
indices[val] = index;//插入鍵值對(val, index)，如果存在則值覆蓋，不存在則創(chuàng)建
- 返回一個迭代器，指向插入的鍵值對或已存在的具有相同鍵的鍵值對。
- 如果插入成功，迭代器指向插入的鍵值對；如果鍵已存在，則迭代器指向已存在的鍵值對。
-
erase函數(shù)：-
iterator erase(iterator position)或size_type erase(const key_type& key) - 從
unordered_map中刪除一個或多個鍵值對。 -
erase函數(shù)有兩個重載形式：一種通過迭代器刪除給定位置的鍵值對，另一種通過鍵刪除具有給定鍵的鍵值對（只刪除指定鍵對應(yīng)的第一個元素，而不會刪除所有相同鍵的元素）。 - 如果使用迭代器形式的
erase函數(shù)，它返回指向已刪除元素之后元素的迭代器。 - 如果使用鍵形式的
erase函數(shù)，它返回刪除的鍵值對數(shù)量。
-
erase函數(shù)使用詳解
（1）刪除指定鍵的元素：
unordered_map<int, int> hashtable = {{1, 10}, {2, 20}, {3, 30}, {4, 40}, {5, 50}};
hashtable.erase(3); // 刪除鍵為3的元素
在這個例子中，哈希表中的鍵值對為 {1: 10, 2: 20, 3: 30, 4: 40, 5: 50}。調(diào)用 erase(3) 后，哈希表變?yōu)?{1: 10, 2: 20, 4: 40, 5: 50}，鍵為3的元素被刪除了。
（2） 刪除指定迭代器范圍內(nèi)的元素：
unordered_map<int, int> hashtable = {{1, 10}, {2, 20}, {3, 30}, {4, 40}, {5, 50}};
auto it1 = hashtable.find(2);
auto it2 = hashtable.find(4);
hashtable.erase(it1, it2); // 刪除鍵為2和鍵為4之間的元素
在這個例子中，哈希表中的鍵值對為 {1: 10, 2: 20, 3: 30, 4: 40, 5: 50}。調(diào)用 erase(it1, it2) 后，哈希表變?yōu)?{1: 10, 4: 40, 5: 50}，鍵為2和鍵為3之間的元素被刪除了。
-
find函數(shù)：iterator find(const key_type& key)- 在
unordered_map中查找具有給定鍵的鍵值對。 - 如果找到匹配的鍵值對，則返回指向該鍵值對的迭代器；如果沒有找到，則返回指向
unordered_map結(jié)尾的迭代器。
-
size函數(shù)：size_type size() const- 返回
unordered_map中鍵值對的數(shù)量。 - 時間復(fù)雜度為 O(1)。
-
empty函數(shù)：bool empty() const- 檢查
unordered_map是否為空。 - 如果
unordered_map中沒有鍵值對，則返回true；否則返回false。 - 時間復(fù)雜度為 O(1)。
-
count函數(shù)：-
size_type count(const key_type& key) const; -
key：要計算出現(xiàn)次數(shù)的鍵 -
count函數(shù)用于確定指定鍵在 unordered_map 中的出現(xiàn)次數(shù)。它返回一個整數(shù)，表示指定鍵在 unordered_map 中出現(xiàn)的次數(shù)。
-
哈希表初始值
對于 C++ 中使用 unordered_map 創(chuàng)建的哈希表，默認(rèn)情況下，鍵和值對應(yīng)的初始值如下：
- 對于基本數(shù)據(jù)類型（例如
int、double、char等），鍵和值的初始值為0。 - 對于類類型（自定義類型），鍵和值的初始值由類的默認(rèn)構(gòu)造函數(shù)確定。
以下是示例代碼來演示哈希表的默認(rèn)初始值：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> map1;
std::unordered_map<char, double> map2;
std::cout << "Default value for int: " << map1[0] << std::endl;
std::cout << "Default value for char: " << map2['a'] << std::endl;
return 0;
}
輸出結(jié)果為：
Default value for int: 0
Default value for char: 0
在上述代碼中，我們創(chuàng)建了兩個 unordered_map，分別是 map1 和 map2。對于基本數(shù)據(jù)類型的鍵和值，它們的初始值都為0。在輸出結(jié)果中，我們訪問了 map1 中鍵為0的值和 map2 中鍵為 'a' 的值，并打印出了它們的初始值，即0。
對于類類型，如果沒有提供自定義的構(gòu)造函數(shù)，它們的初始值將由類的默認(rèn)構(gòu)造函數(shù)決定。如果提供了自定義的構(gòu)造函數(shù)，則初始值將由該構(gòu)造函數(shù)中的初始化列表或默認(rèn)參數(shù)確定。
需要注意
使用 [] 運算符訪問哈希表中不存在的鍵時，會自動將該鍵插入到哈希表中，并將對應(yīng)值的初始值賦給它。因此，訪問不存在的鍵時可能會產(chǎn)生意外的結(jié)果，應(yīng)謹(jǐn)慎使用。如果只是需要判斷鍵是否存在，可以使用 count() 函數(shù)或 find() 函數(shù)來代替。
哈希表遍歷
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> cnt;
for (auto& word : words) {
++cnt[word];
}
vector<string> rec;
for (auto& [key, value] : cnt) {//哈希表遍歷，使用auto& [key,value]
rec.emplace_back(key);
}
sort(rec.begin(), rec.end(), [&](const string& a, const string& b) -> bool {
return cnt[a] == cnt[b] ? a < b : cnt[a] > cnt[b];
});
rec.erase(rec.begin() + k, rec.end());
return rec;
}
};
