google开源了hashtables的包,包括两个部分:

  • sparse, 比较节省空间space-efficient;
  • dense, 高效的查询效率 time-efficient;

同时接口兼容SCI的hash_map和hash_set, 并且提供了序列化的功能,非常赞~

下面是其官方的性能测试数据:可以看到sparse_hash_map比stl::map和hash_map节省2/3的空间,而dense_hash_map具备较高的查询,删除, insert性能,可以根据具体的应用

来使用不同的数据结构。

下载地址:http://code.google.com/p/sparsehash/

doc : http://google-sparsehash.googlecode.com/svn/trunk/doc/

SPARSE_HASH_MAP:
map_grow                  665 ns
map_predict/grow          303 ns
map_replace               177 ns
map_fetch                 117 ns
map_remove                192 ns
memory used in map_grow    84.3956 Mbytes

DENSE_HASH_MAP:
map_grow                   84 ns
map_predict/grow           22 ns
map_replace                18 ns
map_fetch                  13 ns
map_remove                 23 ns
memory used in map_grow   256.0000 Mbytes

STANDARD HASH_MAP:
map_grow                  162 ns
map_predict/grow          107 ns
map_replace                44 ns
map_fetch                  22 ns
map_remove                124 ns
memory used in map_grow   204.1643 Mbytes

STANDARD MAP:
map_grow                  297 ns
map_predict/grow          282 ns
map_replace               113 ns
map_fetch                 113 ns
map_remove                238 ns
memory used in map_grow   236.8081 Mbytes