C++：map、hash

您所在的位置：网站首页 › hashmap的时间复杂度 › C++：map、hash

C++：map、hash

2024-01-16 06:26| 来源: 网络整理| 查看: 265

面试经常被问的问题之一，便是map和hash_map的区别，以及什么时候用map什么时候用hash_map。另外也了解到还有C++11的unordered_map，所以这里一并介绍三个了。用法就不介绍了，主要介绍区别。

1. 三者的区别

map底层是用红黑树实现的，空间复杂度为O(n)，是随着节点的增加才增加，而查找的时间时间复杂度则固定是O(log(n))了。因为红黑树本来就是一种二叉搜索树，所以从begin()遍历到end()得到的key值是有序的，这也是map的一个特点。

hash_map是SGI实现，而unordered_map是C++11标准中新增的。它们都是用hash表实现的，使用开链法解决冲突问题。但是由于用的是hash表，其特性已经决定使用的空间基本到会比实际需要的空间大。保存的数据不是有序的，不能像map那样子通过遍历得到一个有序的结果。查找的时间复杂度可以达到O(1)，基本上都是比map快的。在unordered_map中，链表节点用的是称为bucket（桶）的数据结构。

虽然大多数情况下hash table实现的map都会比红黑树实现的map查找快，但不是绝对的，因为冲突过多的话，可能耗费时间比map还要多。所以对于前者基本上都会有个rehash的操作，而由于rehash的处理不一样，也导致了hash_map和unordered_map的性能有一些差别，这是下后面会讲到的。

2. 使用的场景

使用场景基本上就是用各自的特性决定了。

map一般就是用在数据量小于1000或者对内存使用要求比较高的情况下。因为hash table需要申请的空间比较大，而红黑树则是新增一个节点就申请一个节点的空间。

如果数据量大的话并且需要频繁查找的话，就可以使用hash table实现的map了。这个时候内存已经不是主要的问题所在，而是查找时间了，这种情况下hash table的查找速度是常数而红黑树是O(log(n))，对于后者1024个数据最坏情况下要10次比较，在频繁查找的情况下这种时间耗费是很大的。

总结下来就是三个权衡点：查找速度、数据量、内存使用。

3. hash_map与unordered_map的性能区别

hash_map和unordered_map底层都是hash table实现的，所以特意搜索了下二者的区别，但是没有找到相关的介绍，基本上都只说两者都是hash table实现以及unordered_map性能比hash_map要好很多，并且unordered_map已经成为标准，不建议再使用hash_map。

为了了解为什么unordered_map性能比hash_map好，简单的扒了下两者实现的部分源码，发现两者rehash的处理是不一样的。

对于unordered_map，主要源码是在“/usr/include/c++/4.8.2/tr1/”目录下。使用的是unordered_map.h文件，而实际底层使用的hash table则是在hashtable.h文件中。通过查看hashtable.sh中insert函数的实现，可以看到每次插入前都会调用如下代码：

size_type __n_elt = __detail::__distance_fw(__first, __last); std::pair __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, __n_elt); if (__do_rehash.first) _M_rehash(__do_rehash.second);

即unordered_map在插入前都会调用_M_rehash_policy._M_need_rehash都会判断是否需要rehash，如果需要则会调用_M_rehash进行操作。_M_rehash_policy是在同目录下的hashtable_policy.h中实现的，_M_need_rehash代码如下：

// __n_bkt is current bucket count, __n_elt is current element count, // and __n_ins is number of elements to be inserted. Do we need to // increase bucket count? If so, return make_pair(true, n), where n // is the new bucket count. If not, return make_pair(false, 0). inline std::pair _Prime_rehash_policy:: _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const { if (__n_elt + __n_ins > _M_next_resize) { float __min_bkts = ((float(__n_ins) + float(__n_elt)) / _M_max_load_factor); if (__min_bkts > __n_bkt) { __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + _S_n_primes, __min_bkts); _M_next_resize = static_cast (__builtin_ceil(*__p * _M_max_load_factor)); return std::make_pair(true, *__p); } else { _M_next_resize = static_cast (__builtin_ceil(__n_bkt * _M_max_load_factor)); return std::make_pair(false, 0); } } else return std::make_pair(false, 0); }

_M_max_load_factor是整个hash table的负载因子，默认为1，_M_growth_factor是bucket数的增长因子，默认为2，而__prime_list则是素数列表。从上面的代码可以看出每次insert时，先判断最后需要的数据大小是否超过了预设的最大值_M_next_resize，是则判断需要的bucket数是否大于当前的bucket数，如果是则需要rehash操作了。

rehash的时候先将当前的bucket数乘以负载因子得到新的bucket数，在与__min_bkts对比得到最大的bucket数更新到__min_bkts中。接下来，再从__prime_list中选出比__min_bkts大的最小素数（素数的hash效果比较好），更新_M_max_load_factor后将该素数返回。

从_M_need_rehash中返回的结果是需要rehash了，则调用_M_rehash并将传回的素数传给该函数：

template void _Hashtable:: _M_rehash(size_type __n) { _Node** __new_array = _M_allocate_buckets(__n); __try { for (size_type __i = 0; __i < _M_bucket_count; ++__i) while (_Node* __p = _M_buckets[__i]) { std::size_t __new_index = this->_M_bucket_index(__p, __n); _M_buckets[__i] = __p->_M_next; __p->_M_next = __new_array[__new_index]; __new_array[__new_index] = __p; } _M_deallocate_buckets(_M_buckets, _M_bucket_count); _M_bucket_count = __n; _M_buckets = __new_array; } __catch(...) { ... } }

该函数就是重新申请__n个成员的bucket数组，并将旧bucket数组的节点重新hash到新bucket数组上，比较容易理解。

那，hash_map中是怎么实现rehash的呢。这里我看的源码主要是在“/usr/local/include/boost/asio/detail/”目录下的hash_map.hpp。insert函数内容如下：

// Insert a new entry into the map. std::pair insert(const value_type& v) { if (size_ + 1 >= num_buckets_) rehash(hash_size(size_ + 1)); size_t bucket = calculate_hash_value(v.first) % num_buckets_; iterator it = buckets_[bucket].first; ... }

可以看到插入的时候只要判断当前节点大小大于bucket数目，就会进行rehash的操作，而rehash函数内容如下：

// Re-initialise the hash from the values already contained in the list. void rehash(std::size_t num_buckets) { if (num_buckets == num_buckets_) return; num_buckets_ = num_buckets; BOOST_ASIO_ASSERT(num_buckets_ != 0); iterator end_iter = values_.end(); // Update number of buckets and initialise all buckets to empty. bucket_type* tmp = new bucket_type[num_buckets_]; delete[] buckets_; buckets_ = tmp; for (std::size_t i = 0; i < num_buckets_; ++i) buckets_[i].first = buckets_[i].last = end_iter; ... }

这里hash_map的rehash简单粗暴，直接就是更新bucket数目为需要的数目就行了，而不会像unordered_map那样子进行数量的优化。

此外，我也看了下boost里面的unordered_map的实现，在“/usr/local/include/boost/unordered”目录下的unordered_map.hpp，代码里面的rehash操作也是像上面的unordered_map一样会将新bucket数目转换成一个素数，但是似乎在插入新元素的时候并没有判断是否需要rehash，看起来是需要手动rehash操作的。

通过上面的对比，可以看到unordered_map在rehash的操作上比hash_map要很好多，这应该也就是unordered_map效率由于hash_map的原因之一吧。有什么说错的，也希望大家可以指点下。

下面有一些链接可以参考：

map/unordered_map原理和使用整理

STL中的map、unordered_map、hash_map

【本文地址】

C++：map、hash

C++：map、hash

今日新闻

推荐新闻