关于hash_map和map，知道的不知道的都进来看看

wells-xu

大家都知道，map和hash_map用来处理key_value对的高效查找。

遇到这么一个问题，当系统需要存储一个key-value对达到一个很高的数量级的时候，比如千万级别，插入的时候hash-map会因为内存膨胀达到某一个2的n次方的分配点的时候话费很长时间，如果系统要求高效能的反应速度就有矛盾了。但是因为map的特殊存储方式，导致不能直接提供和vector类似的reserve事先初始化的方法，所以相当遗憾。map虽然和list一样插入不会有这样的重新分配过程，但是查找速度又比hash-map差了大概5倍，敢问有没有兄弟能帮忙一把，google烂了，都没有找到好的解决方法。

doofy

你嫌stl的map差，就自己实现hash表吧  长度选择你业务总量的1/0.6 倍 或者 1/0.8倍  网上不少现成的hash算法，直接拿就成

nicolas.shen

如果实在有困难，就直接初始化的时候把内存分配好，自己事先分配，避免动态分配

redor

原帖由 wells-xu 于 2009-9-24 15:58 发表
大家都知道，map和hash_map用来处理key_value对的高效查找。

遇到这么一个问题，当系统需要存储一个key-value对达到一个很高的数量级的时候，比如千万级别，插入的时候hash-map会因为内存膨胀达到某一个2的n ...

谨慎怀疑你插入的key／val为字符类型， 其实map不适合用来村字符串类型， 因为比较很耗时， 有个简单办法就是先把字符转换成数字。。。 然后再放到map里查找排序
字符串和数字的转换可以使用trie实现， 这个效率很高 比hash好用.
我写过一个trie实现，http://hispider.googlecode.com/s ... sk/src/utils/trie.c
http://hispider.googlecode.com/s ... sk/src/utils/trie.h
要多线程需要加一个
http://hispider.googlecode.com/s ... k/src/utils/mutex.h
编译的时候添加-DHAVE_PTHREAD
不然会不安全

map就是一个红黑树 平均查找效率就是log(N）

wells-xu

谢谢楼上的回复，将string转换成整形作为key存储的确是一个非常不错的创意，高见。

我后来发现，hashmap在release上面的表现堪称完美，因为我开始测试都是在debug下面，发现debug下面每到2^16的时候出现非常严重的时间消耗，但是release下面却快如闪电。所以基本上不用考虑这个开销，如果key替换成int的话，效率大概可以提高一倍。