map vs hash_map in C++

Question

我對C++中的hash_map和map有疑問。我明白map在STL中，但hash_map不是標準。兩者有什麼區別？

Answer 1

它們以非常不同的方式實現。

hash_map（unordered_map在TR1和Boost中;用它們代替）使用散列表，其中密鑰被散列到表中的一個槽中，並且該值存儲在與該密鑰相關的列表中。

map實現爲平衡二叉搜索樹（通常是紅/黑樹）。

unordered_map應該爲訪問集合的已知元素提供稍好的性能，但map將具有其他有用的特性（例如，它以按排序順序存儲，允許從開始到結束遍歷）。 unordered_map的插入和刪除速度比map快。

Answer 2

C++規範並沒有明確說明您必須使用哪種算法來處理STL容器。但是，它確實會對其性能施加一定的限制，從而排除了map和其他關聯容器的哈希表的使用。 （它們通常用紅色/黑色樹來實現。）這些約束要求這些容器比散列表可以提供更好的最差情況。

然而，許多人確實需要散列表，所以基於散列的STL關聯容器已經成爲多年來的常見擴展。因此，他們將unordered_map等添加到更高版本的C++標準中。

Answer 3

hash_map是許多庫實現提供的常見擴展。這正是爲什麼當它作爲TR1的一部分添加到C++標準中時，它被重命名爲unordered_map。地圖通常使用像紅黑樹這樣的平衡二叉樹來實現（實現方式各不相同）。通常使用散列表來實現hash_map和unordered_map。因此訂單不被維護。 unordered_map插入/刪除/查詢將是O（1）（常數時間）其中映射將是O（log n）其中n是數據結構中項目的數量。所以unordered_map是更快，如果你不關心的項目的順序應優先於map。有時候你想要維護秩序（按鍵排序），因此map將是您的選擇。

Answer 4

一些關鍵的區別在於複雜性要求。

映射需要O（log（N））時間來插入和查找。

unordered_map需要O（1）的「平均」時間用於插入和查找，但允許其最壞情況時間爲O（N）。

因此，通常unordered_map會更快，但取決於您存儲的密鑰和散列函數，可能會變得更糟。

Answer 5

我不知道給出了什麼，但是，hash_map需要超過20秒才能清除（）150K無符號整數鍵和浮點值。我只是在跑步和閱讀別人的代碼。

這是它如何包含hash_map。

#include "StdAfx.h" 
#include <hash_map> 

我讀這這裏 https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

說清楚（）是O（N）的順序。對我來說，這很奇怪，但是，事情就是這樣。