C++ map 和 hashmap 区别

几句话道出 map 和 hash_map 的区别

1. stl map is an associative array where keys are stored in sorted order using balanced trees. while hash_map is a hashed associated container, where keys are not stored in an ordered way. key, value pair is stored using a hashed function.        2. insertion and lookup takes ologn time in map, also performance would degrade as the key size increases. mainly balance operations on large key ranges would kill performance. while lookup is very efficient o(1) in hash_map.        3. map is useful where you want to store keys in sorted order, hash_map is used where keys order is not important and lookup is very efficient.        4. one more difference is map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. erasing an element from a map also does not invalidate any iterators. performance would mostly be o(lgn) due to the implementation of a balanced tree. for map custom objects you would need at the minimum the following operators to store data in a map "<" ">" "==" and of course the other stuff for deep copy.

原文地址：http://stlchina.huhoo.net/twiki/bin/view.pl/main/stldetailhashmap

0 为什么需要hash_map

1 数据结构：hash_map原理

2 hash_map 使用

2.1 一个简单实例

2.2 hash_map 的hash函数

2.3 hash_map 的比较函数

2.4 hash_map 函数

3 相关hash容器

4 其他

4.1 hash_map和map的区别在哪里？

4.2 什么时候需要用hash_map，什么时候需要用map?

4.3 如何在hash_map中加入自己定义的类型?

4.4 如何用hash_map替换程序中已有的map容器？

4.5 为什么hash_map不是标准的？

4.6 有学习使用hash_map的建议吗？

5 参考文章:

条条大路通罗马，为什么你不随便选一条？

学习stl map, stl set之 数据结构基础。 看看map的实现:

#include <map>
#include <string>
using namespace std;
...
map<string, string> namemap;
//增加。。。
namemap["岳不群"]="华山派掌门人，人称君子剑";
namemap["张三丰"]="武当掌门人，太极拳创始人";
namemap["东方不败"]="第一高手，葵花宝典";
...
//查找。。
if(namemap.find("岳不群") != namemap.end()){
        ...
}

不觉得用起来很easy吗？而且效率很高，100万条记录，最多也只要20次的string.compare的比较，就能找到你要找的记录;200万条记录事，也只要用21次的比较。

速度永远都满足不了现实的需求。如果有100万条记录，我需要频繁进行搜索时，20次比较也会成为瓶颈，要是能降到一次或者两次比较是否有可能？而且当记录数到200万的时候也是一次或者两次的比较，是否有可能？而且还需要和 map 一样的方便使用。

答案是肯定的。这时你需要 has_map. 虽然hash_map目前并没有纳入c++ 标准模板库中，但几乎每个版本的stl都提供了相应的实现。而且应用开发十分广泛。在正式使用 hash_map 之前，先看看hash_map的原理。

标准库 stl ：allocator能做什么)

stl 编程手册：hash_map，这里主要介绍几个常用函数。

hash_map(size_type n)  如果讲究效率，这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多，hash函数发生冲突的概率就越小，重新申请内存的概率就越小。n越大，效率越高，但是内存消耗也越大。

const_iterator find(const key_type& k) const.   用查找，输入为键值，返回为迭代器。

data_type& operator[](const key_type& k) .      这是我最常用的一个

此文来自: 马开东博客 转载请注明出处 网址：

函数。因为其特别方便，可像使用数组一样使用。不过需要注意的是，当你使用[key ]操作符时，如果容器中没有key元素，这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时，你可以使用find。如果你希望插入该元素时，你可以直接使用[]操作符。 insert 函数。在容器中不包含key值时，insert函数和[]操作符的功能差不多。但是当容器中元素越来越多，每个桶中的元素会增加，为了保证效率，hash_map会自动申请更大的内存，以生成更多的桶。因此在insert以后，以前的iterator有可能是不可用的。

erase函数。在insert的 开发过程 中，当每个桶的元素太多时，hash_map可能会自动扩充容器的内存。但在sgi stl中是erase并不自动回收内存。因此你调用erase后，其他元素的iterator还是可用的。

红黑树(rb tree)实现。因此其memory 数据结构是不一样的。

4.2 什么时候需要用hash_map，什么时候需要用map? 总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而 map 的查找速度是 log(n) 级别。并不一定常数就比log(n) 小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。

现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。

这里还有个关于hash_map和map的小故事，看看:http://dev.马开东/develop/article/14/14019.shtm

effective stl 25: 熟悉非标准散列容器, 另外建议查看源代码。如果还有问题，那么你可以在stl论坛上提问，会有高手回答你的。