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方法。
除非你对程序的效率毫不关心,否则你就应该使用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
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的情况下,要根据数据量,已经这些数据的统计学特性来选择相应的容器。
RB-Tree未必总是效率稳定的。比如查找长度1000的string key和查找长度为1的string key的时候,RB tree显然将由于string.compare的工作量差异而出现总体上的效率差异;而此时hash表反而可以表现出稳定的效率。
再者,tree中存放的具体内容,会影响每次string.compare的工作量,从而影响RB-Tree的总体效率。而hash表受具体内容的影响就比较小,因为hash表的compare次数比较少。
以上都是理论分析。在对程序效率有要求的实际应用中,我还没遇到红黑树比哈希表更优秀的情况。
能不能请楼上举一个具体的例子呢?
PS:我承认我在逻辑上处于不利地位,因为我是要证明“命题总是成立”,而楼上只需要举一个例子反证就可以了。不过我仍然对此跃跃欲试。