[C++] STL里面的map - Eric‘s Little Hut

[C++] STL里面的map

STL里面的map并不是哈希表，这对于习惯了MFC里面CMap的人可能有点不习惯。STL里面的map仅仅是棵红黑树。
除非你对程序的效率毫不关心，否则你就应该使用stlex里面的hash_map代替stl里面的map。因为他们做着非常类似的工作，而且他们的调用方法几乎一样。

hash_map需要对key取hash值，我想这应该不会是问题。我们在实际应用中，通常只会用数值、指针或者字符串作为key，这些东西都是很容易hash的。实际上，用object作为key反而容易出现问题，大多数人并不鼓励在C++里面用object做key。

说远一点，C#里面倒是非常开心的一直用object做着哈希表的key，这是为什么呢？这是因为C#是一个单根体系，所有的class都是从System.Object派生出来的，而System.Object实现了GetHashCode方法。这迫使C#中所有的对象，要么采用基类的GetHashCode方法，要么实现自己的GetHashCode方法。

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=525824

[推荐本文] [点击此处收藏本文]   发表于 2005年11月09日 10:16 AM

 

http://blog.vckbase.com/bruceteen/ 发表于2005-11-09 1:05 PM  IP: 221.6.3.*

当初制定CPP98时，时间紧迫，要想知道为什么选用RB-Tree而不是hash的原因必须先了解RB-Tree和hash的差别：
a. RB-Tree的查找和删除时间复杂度是log(o)，而hash呢，快的时候是常数级，慢的时候（碰撞）也关系不大。
b. 插入：RB-Tree仍然是log(o)，而hash快的时候同样是常数级，但最慢的时候可能需要重新分配内存和重新构造hash。
结论是：
RB-Tree效率稳定，而hash在基于随即统计上比RB-Tree要快。
所以：
a. 首先从需求上考虑到底使用哪个容器，比如某个用户查询，用RB-Tree一万次，每次需要花费2秒；用hash，9999次每次花费1秒，但有一次需要花费10000秒。此时，你应该选用哪个？虽然总体时间上还是hash快，但哪个花费了10000秒的用户可不同意这种说法。
b. 对于既可以使用RB-TREE又可以使用hash的情况下，要根据数据量，已经这些数据的统计学特性来选择相应的容器。

 

Eric 发表于2005-11-09 5:24 PM  IP: 218.109.35.*

RB-Tree未必总是效率稳定的。比如查找长度1000的string key和查找长度为1的string key的时候，RB tree显然将由于string.compare的工作量差异而出现总体上的效率差异；而此时hash表反而可以表现出稳定的效率。
再者，tree中存放的具体内容，会影响每次string.compare的工作量，从而影响RB-Tree的总体效率。而hash表受具体内容的影响就比较小，因为hash表的compare次数比较少。

以上都是理论分析。在对程序效率有要求的实际应用中，我还没遇到红黑树比哈希表更优秀的情况。
能不能请楼上举一个具体的例子呢？

PS：我承认我在逻辑上处于不利地位，因为我是要证明“命题总是成立”，而楼上只需要举一个例子反证就可以了。不过我仍然对此跃跃欲试。