C + + 中的 map 与 hash_map

C + + 规范没有明确说明必须用于 STL 容器的算法。然而，它们的性能确实受到某些限制，这就排除了对 map和其他关联容器使用哈希表的可能性。(它们通常是用红/黑树来实现的。)这些约束要求这些容器具有比散列表所能提供的更好的最坏情况性能。

Many people really do want hash tables, however, so hash-based STL associative containers have been a common extension for years. Consequently, they added unordered_map and such to later versions of the C++ standard.

它们以完全不同的方式实现。

hash_map(TR1和 Boost 中的 unordered_map; 使用它们代替)使用一个散列表，其中键被散列到表中的一个槽中，值存储在与该键绑定的列表中。

map实现为一个平衡二叉查找树(通常是红/黑树)。

在访问集合的已知元素方面，unordered_map应该提供稍好的性能，但是 map还有其他有用的特征(例如，它按排序顺序存储，这允许从开始到结束的遍历)。在插入和删除时，unordered_map会比 map快。

hash_map是许多库实现提供的常见扩展。这就是为什么当它作为 TR1的一部分被添加到 C + + 标准时，它被重命名为 unordered_map。Map 通常使用红黑树这样的平衡二叉搜索树来实现(实现当然有所不同)。hash_map和 unordered_map通常使用散列表实现。因此，秩序没有得到维护。unordered_map插入/删除/查询将是 O (1)(常量时间) ，其中 map 将是 O (log n) ，其中 n 是数据结构中的项数。因此，unordered_map是更快的，如果你不关心项目的顺序应优先于 map。有时你想维持秩序(按键订购) ，因此 map将是选择。

一些关键的区别在于复杂性需求。

• A map requires O(log(N)) time for inserts and finds operations, as it's implemented as a 红黑树 data structure.

• 一个 unordered_map需要一个“平均”时间的 O(1)插入和发现，但允许有一个最坏的情况下的时间的 O(N)。这是因为它是使用 哈希表数据结构实现的。

因此，通常情况下，unordered_map会更快，但是取决于您存储的键和散列函数，可能会变得更糟。

我不知道是什么原因，但是 hash _ map 需要20多秒才能清除()150K 无符号整数键和 float 值。我只是运行和阅读别人的代码。

这就是它包含 hash _ map 的方式。

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

I read this here https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

说 clear ()是 O (N)的次序，这对我来说很奇怪，但事实就是如此。

map is implemented from balanced binary search tree(usually a rb_tree), since all the member in balanced binary search tree is sorted so is map;

hash_map是从 hashtable实现的。因为 hashtable中的所有成员都是未排序的，所以 hash_map(unordered_map)中的成员也是未排序的。

hash_map不是一个 C++标准程式库，但是现在它被重命名为 unordered_map(你可以想到它被重命名了) ，并且因为 c + + 11而变成了 C++标准程式库。

下面我将从源代码中给出一些如何实现这两种类型映射的核心接口。

地图:

下面的代码只是为了说明，map 只是 balanced binary search tree的一个包装器，几乎所有它的函数都只是调用 balanced binary search tree函数。

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
// used for rb_tree to sort
typedef Key    key_type;


// rb_tree node value
typedef std::pair<key_type, value_type> value_type;


typedef Compare key_compare;


// as to map, Key is used for sort, Value used for store value
typedef rb_tree<key_type, value_type, key_compare> rep_type;


// the only member value of map (it's  rb_tree)
rep_type t;
};


// one construct function
template<typename InputIterator>
map(InputIterator first, InputIterator last):t(Compare()){
// use rb_tree to insert value(just insert unique value)
t.insert_unique(first, last);
}


// insert function, just use tb_tree insert_unique function
//and only insert unique value
//rb_tree insertion time is : log(n)+rebalance
// so map's  insertion time is also : log(n)+rebalance
typedef typename rep_type::const_iterator iterator;
std::pair<iterator, bool> insert(const value_type& v){
return t.insert_unique(v);
};

返回文章页面

hash_map是从 hashtable实现的，它的结构有点像这样:

在下面的代码中，我将给出 hashtable的主要部分，然后给出 hash_map。

// used for node list
template<typename T>
struct __hashtable_node{
T val;
__hashtable_node* next;
};


template<typename Key, typename Value, typename HashFun>
class hashtable{
public:
typedef size_t   size_type;
typedef HashFun  hasher;
typedef Value    value_type;
typedef Key      key_type;
public:
typedef __hashtable_node<value_type> node;


// member data is buckets array(node* array)
std::vector<node*> buckets;
size_type num_elements;


public:
// insert only unique value
std::pair<iterator, bool> insert_unique(const value_type& obj);


};

像 map's只有一个成员是 rb_tree，hash_map's只有一个成员是 hashtable。它的主要代码如下:

template<typename Key, typename Value, class HashFun = std::hash<Key>>
class hash_map{
private:
typedef hashtable<Key, Value, HashFun> ht;


// member data is hash_table
ht rep;


public:
// 100 buckets by default
// it may not be 100(in this just for simplify)
hash_map():rep(100){};


// like the above map's insert function just invoke rb_tree unique function
// hash_map, insert function just invoke hashtable's unique insert function
std::pair<iterator, bool> insert(const Value& v){
return t.insert_unique(v);
};


};

下面的图片显示了当一个 hash _ map 有53个桶，并且插入一些值时，它的内部结构。

下图显示了 map 和 hash _ map (unorder _ map)之间的一些区别，该图来自 如何选择 map 和 unorder _ map？: