[C++] Deep into Hash Map in STL: std::unordered_map

std::unordered_map 是 C++11 後 STL 新增的 container，本質上可以想成是一個 hash map。相較於原先的 std::map 基本上是個 red-black tree ， std::unordered_map 的重點在於許多操作的 amortize complexity 基本上是 constant time。只是使用上有些許的重點要注意，不然效能可能會不如預期

std::unordered_map 提供的操作及複雜度基本上參考 C++ reference 就好，上面都有寫。這邊先來簡單帶一下 gcc 怎麼大致上的實作方向及其運作，詳細的 source code 及說明可以參考他們的 github (_Hashtable 是 std::unordered_map 真正的實作)。

簡單來說 std::unordered_map 是兩個 container 的複合體：

In terms of Standard containers the hashtable is like the aggregation of:
- std::forward_list<_Node> containing the elements
- std::vector<std::forward_list<_Node>::iterator> representing the buckets 

有別於一般想像的只要有一個 array 當作 bucket 儲存 element，這邊他們還多用了個 std::forward_list，這樣設計的主要原因是為了 iteration：
想像一下如果今天只有 std::vector 這個 bucket 來儲存，但是使用者今天想要把這個 hash map 的所有 element 都拿出來 (當然，不管順序，但就是需要把所有 element 都掃一遍)，在只有 std::vector 的情況下可能會變得非常沒效率。原因在於

1. 為了避免太容易碰撞，所以 bucket 數量相較於 element 數量可能大上許多
2. bucket 可能還有許多空位，但是我們無法快速的知道哪些 bucket 是空的

所以用兩個彼此特性獨立的 container 就能同時讓兩種不同面相操作都能以極有效率的方式運作。

這次我遇到狀況的是看起來很正常但是跑完 performance profiling 才發現事情不對勁的鬼東西...這次引起我興趣的是這個：

• memset

經過交互比對後發現這傢伙是從 clear 來的，基本上那邊幹的事情就是直接用 memset 去把儲存 element pointer 的 array 整個清空成 0 (相當於 nullptr)。看起來很正常，不過我的使用情況是這樣：

• 已知最多會用到多少 bucket，所以用了 reserve 把 bucket 拉到至少指定的大小
• 特定條件下會需要用 clear 整個清空重填 (這條件可能會被觸發極多次)

這邊先岔個題外話：基本上 STL 的 contiguous container 有個特性是 memory 不一定會被馬上釋放掉。以 std::unordered_map 的 clear 來說，他就是指有 memset 但是不會釋放 memory。

我這次出狀況的原因就在這，雖然我已知最多會用到多少 bucket，但是有時候最少會只有一個 element 然後就觸發使用 clear 的條件。又因為 bucket 被我用 reserve 撐大了 (而且無法減小!)，所以 memset 就一直套用在一塊很大的記憶體空間，然後 runtime 就炸了。

就結論來說，我的使用情況比較適合使用 erase 而非 clear，雖然乍看之下好像 erase 會比較慢，但是在 element 數量不多且 butcket 相對大的時候 erase 反而會比 clear 來得有效率。


P.S. C++ reference 上對於 clear 的 complexity 說明讓我有嚴重誤解，我當初是想說 element 數量不多的話應該 clear 的速度也會很快，現在才知道原來是跟你的 bucket size 才有關聯性 Orz (雖然其他 library 的實作可能就不是這樣就是)