hash_strmap & gold_hash_map update

hash_strmap

在不增加任何额外成本的情况下,string pool 中每个 string 消耗的内存,平均情况下,减少了一个字节。太不值一提。

gold_hash_map

计划新加功能:
   使用 FreeList 管理已删除的元素,这样最大的好处是:即使有元素删除,所有未被删除的元素的 id(数组下标)都不会改变。这样,就可以把 id(数组下标)作为元素的永久标识,可以把这个 id 保存在别的地方,来直接访问 gold_hash_map 的元素。这个功能看上去比较简单,但接口设计和实现都还是有不少复杂度的。
   hash_strmap 也可以实现这个功能,但是这样会在 string pool 中留下无法利用的空洞,如果把这个空洞消除,就会出现 0 长度的 string pool item,从而在 node 和 value 数组中会留下无法利用的空洞,如果要真正利用这些空洞,时间复杂度或实现复杂度会大幅增加。这比 gold_hash_map 实现该功能增加的额外复杂度要多得多得多。

Reference

hash_strmap 为什么那么快

gold_hash_map design

gold_hash_map bench mark with google sparse hash

缓存与平行数组在 hash_strmap 和 gold_hash_map 中的应用

gold_hash_map vs google sparse map by google’s time_hash_map.cc

作者:
该日志由 csdn-whinah 于2011年12月03日发表在C++分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: hash_strmap & gold_hash_map update
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。