系列文章目錄

STL源碼剖析筆記——迭代器
STL源碼剖析筆記——vector
STL源碼剖析筆記——list
STL源碼剖析筆記——deque、stack，queue
STL源碼剖析筆記——Binary Heap、priority_queue
STL源碼剖析筆記——AVL-tree、RB-tree、set、map、mutiset、mutimap
STL源碼剖析筆記——哈希表、unordered_set、unordered_map、unordered_mutiset、unordered_mutimap

---

1. hashtable

??哈希表（hashtable）是一種常見的數據結構，它和紅黑樹、AVL一樣是用來存儲數據的。紅黑樹和AVL查找數據的時間復雜度是O(lgN) ，是對數平均時間。但哈希表的查找效率具有常數平均時間，復雜度是O(1)；
??哈希表的底層是通過數組+hash function來實現常數時間查找效率。首先我們假設哈希表創建了一個大小為10的空間。

數據的存放通過hash function來決定，具體采用除留余數法：

根據這個規則，可以將7，9，11對應存入數組；

但此時如果再想插入17，會發現位置已經被7給占了，這就是發生了哈希沖突。主要有三種方式來解決哈希沖突：
??1.線性探測
??2.二次探測
??3.開鏈法
線性探測和二次探測屬于閉散列，開鏈法屬于開散列。

線性探測

線性探測就是發現當前位置被占之后，順序向后找，直到找到一個空的位置（如果到數組尾部仍未找到，則回到頭部從頭找）；


但線性探測有一些無法避免的缺點：
聚集： 線性探測法容易導致聚集（clustering）現象。聚集指的是哈希表中形成連續的、緊密聚集的元素，這使得在插入元素時，發生沖突的概率進一步增加。聚集可能導致更多的線性探測，進而影響性能。

性能下降： 隨著哈希表的填充因子增加，線性探測法的性能可能下降。填充因子是指已經存儲的元素數量與哈希表大小的比率。填充因子增加會導致沖突的概率上升，進而增加線性探測的次數。

刪除困難： 在使用線性探測法的散列表中刪除元素可能比較困難。刪除操作通常需要標記被刪除的元素，否則會影響后續查找。而線性探測法對刪除操作的支持相對較弱。

不適用于高負載因子： 當哈希表的負載因子較高時，即填充因子接近1，線性探測法的性能可能急劇下降。高負載因子會導致更頻繁的沖突，線性探測的探測次數增多，使得查找、插入和刪除的效率都降低。

二次探測

??二次探測的思路和線性探測一樣，但這次查找的步長變為了指數：如果hash function計算出來的位置為H并且發生了沖突，就依次嘗試H + 12、H + 22、H + 32、H + 42······

二次探測緩解了線性探測的聚集問題，但也有一定的缺點：

周期性聚集： 二次探測法可能導致周期性聚集問題。如果哈希表的大小是某個4k+3形式的素數，而二次探測的步長為2的冪（例如1, 4, 9, 16等），那么在一定條件下會形成周期性的聚集。這可能導致更多的沖突和性能下降。

容易形成死循環： 在某些情況下，特定的哈希表狀態可能導致二次探測進入死循環。例如，如果哈希表中的某個位置發生沖突，而附近的位置也都被占用，那么二次探測可能永遠無法找到空槽。

刪除困難： 與線性探測法一樣，二次探測法在刪除操作上也可能比較困難。刪除元素可能需要特殊的標記，以確保在查找時能夠正確地處理已刪除的槽。

不適用于高負載因子： 當哈希表的負載因子較高時，二次探測法的性能可能下降。高負載因子增加了沖突的概率，進而增加了二次探測的次數。

開鏈法

??STL中的哈希表采用開鏈法解決哈希沖突問題，開鏈法在每個單元維護一個單向鏈表，發生沖突的元素直接接到鏈表上。同時將數組替換為vector，方便空間擴充。hashtable只有前向迭代器，一個單元的list最后的元素指向下一個單元（即下一個list的頭）。

哈希表擴容

閉散列

??我們定義一個負載因子來表示當前散列表的滿溢程度：

????????????????負載因子α = 元素個數 / 數組長度

??負載因子越高，當前散列表發生哈希沖突的概率越高，則整體效率越低。一般來說，負載因子超過0.5時要考慮增容。擴容后，由于數組長度發生變化，原數組中的所有元素要重新插入到新哈希表中。

開散列

??桶的個數是一定的，隨著元素的不斷插入，每個桶中元素的個數不斷增多，極端情況下，可能會導致一個桶中鏈表節點非常多，會影響的哈希表的性能，因此在一定條件下需要對哈希表進行增容。開散列最好的情況是：每個哈希桶中剛好掛一個節點，再繼續插入元素時，每一次都會發生哈希沖突，因此，在元素個數剛好等于桶的個數時，可以給哈希表增容。
??擴容后，由于桶的長度發生變化，原數組中的所有元素要重新插入到新哈希表中。

??對于整形數據可以直接進行取模運算，但是如果要存的數據是字符串的類型呢？我們要自己配套實現一個仿函數，如果是int就自己實現int類型的仿函數，如果是string就自己實現string類型的仿函數。然后用仿函數去計算。

2. unordered_set

??unordered_set的底層實現容器是hashtable（哈希表），可以進行高效的搜索、插入和刪除操作，時間復雜度是O(1)，unordered_set不允許兩個元素有相同的鍵值。

??unordered_set與set相比，擁有更高的操作效率（set的操作效率是O(logn)），但存入unordered_set是無序的，不能保證輸入進來數據的順序！！！

??unordered_set的操作基本上都是對底層哈希表操作的引用：

begin() 和 end()：返回指向容器中第一個元素和最后一個元素之后的位置的迭代器。size()：返回容器中元素的數量。empty()：檢查容器是否為空。如果為空，返回 true，否則返回 false。max_size()：返回容器可以容納的最大元素數量。insert()：將元素插入到容器中。如果元素已經存在，則不會插入。emplace()：構造并插入元素。與 insert() 類似，但可以直接使用構造函數參數，避免額外的復制或移動操作。erase()：從容器中刪除指定的元素。clear()：刪除容器中的所有元素。find()：查找容器中是否存在具有指定鍵的元素。如果找到，則返回指向該元素的迭代器；否則，返回指向容器結尾的迭代器。count()：返回具有指定鍵的元素的數量。對于 unordered_set，結果只能是 0 或 1。bucket_count()：返回容器中的桶數量。load_factor()：返回容器的負載因子。負載因子是元素數量與桶數量的比值。max_load_factor()：返回或設置容器的最大負載因子。當實際負載因子超過最大負載因子時，容器會自動增加桶數量。rehash()：設置容器的桶數量。當桶數量增加時，容器將重新分配其元素，以保持合適的負載因子。reserve()：設置容器的最小桶數量，以便容納指定數量的元素，而無需重新哈希。

3. unordered_mutiset

??unordered_multiset的特性以及用法和unordered_set完全相同，唯一的差別在于它允許鍵值重復(即插入重復的值)。

4. unordered_map

??unordered_map的的底層實現容器是hashtable（哈希表），可以進行高效的搜索、插入和刪除操作，時間復雜度是O(1)，map的所有元素都是pair,同時擁有實值(value)和鍵值(key)。pair的第一元素被視為鍵值, 第二元素被視為實值。map不允許兩個元素擁有相同的鍵值。

??unordered_map與map相比，擁有更高的操作效率（map的操作效率是O(logn)），但存入unordered_map是無序的，不能保證輸入進來數據的順序！！！

??unordered_map的操作基本上都是對底層哈希表操作的引用：

begin()	返回指向容器中第一個鍵值對的正向迭代器。
end() 	返回指向容器中最后一個鍵值對之后位置的正向迭代器。
cbegin()	和 begin() 功能相同，只不過在其基礎上增加了 const 屬性，即該方法返回的迭代器不能用于修改容器內存儲的鍵值對。
cend()	和 end() 功能相同，只不過在其基礎上，增加了 const 屬性，即該方法返回的迭代器不能用于修改容器內存儲的鍵值對。
empty()	若容器為空，則返回 true；否則 false。
size()	返回當前容器中存有鍵值對的個數。
max_size()	返回容器所能容納鍵值對的最大個數，不同的操作系統，其返回值亦不相同。
at(key)	返回容器中存儲的鍵 key 對應的值，如果 key 不存在，則會拋出 out_of_range 異常。 
find(key)	查找以 key 為鍵的鍵值對，如果找到，則返回一個指向該鍵值對的正向迭代器；反之，則返回一個指向容器中最后一個鍵值對之后位置的迭代器（如果 end() 方法返回的迭代器）。
count(key)	在容器中查找以 key 鍵的鍵值對的個數。
equal_range(key)	返回一個 pair 對象，其包含 2 個迭代器，用于表明當前容器中鍵為 key 的鍵值對所在的范圍。
emplace()	向容器中添加新鍵值對，效率比 insert() 方法高。
emplace_hint()	向容器中添加新鍵值對，效率比 insert() 方法高。
insert() 	向容器中添加新鍵值對。
erase()	刪除指定鍵值對。
clear() 	清空容器，即刪除容器中存儲的所有鍵值對。
swap()	交換 2 個 unordered_map 容器存儲的鍵值對，前提是必須保證這 2 個容器的類型完全相等。
bucket_count()	返回當前容器底層存儲鍵值對時，使用桶（一個線性鏈表代表一個桶）的數量。
max_bucket_count()	返回當前系統中，unordered_map 容器底層最多可以使用多少桶。
bucket_size(n)	返回第 n 個桶中存儲鍵值對的數量。
bucket(key)	返回以 key 為鍵的鍵值對所在桶的編號。
load_factor()	返回 unordered_map 容器中當前的負載因子。負載因子，指的是的當前容器中存儲鍵值對的數量（size()）和使用桶數（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()	返回或者設置當前 unordered_map 容器的負載因子。
rehash(n)	將當前容器底層使用桶的數量設置為 n。
reserve()	將存儲桶的數量（也就是 bucket_count() 方法的返回值）設置為至少容納count個元（不超過最大負載因子）所需的數量，并重新整理容器。
hash_function()	返回當前容器使用的哈希函數對象。

5. unordered_mutimap

??unordered_multimap的特性以及用法和unordered_map完全相同，唯一的差別在于它允許鍵值重復(即插入重復的值)。