gold_hash_map design

前一段时间写了个 hash_strmap, 效果不错,其中的一些设计思想可以扩展。于是,昨天到今天两天写了一个通用的 hash_map, 起了个名字叫gold_hash_map

hash_strmap 的介绍文章一介绍文章二

内存使用

和 hash_strmap 一样,使用连续的内存块,不过更简单,只需要两块内存( hash_strmap 需要 3 块或 4 块 )。

支持排序

和 hash_strmap 一样,排序只是对数组排序然后再对 bucket 和 hash_link 进行重新链接,无需额外内存。

不一样的地方

缓存 hash value

一般情况下,hash value 的计算比较昂贵,所有有效的方式就是将这个计算出来的 hash value 缓存起来,但是,缓存是需要空间的!所以,对于简单的 Key,就不缓存它的 hash value, 比如象 int, long 等等,是否缓存的默然条件就是:没有 trivial destructor 并且尺寸小于指针宽度。

删除元素更简单

只需要在被删除的那个元素占的位置,用末尾的那个(有效)元素替换,然后再重新链接,一切就 OK 了。但是,如果希望 id 不变,就把这个空位保留下来,并且用链表(数组下标做指针)链接到空闲链表上,以后插入时优先使用空闲链表,空闲链表为空时,在数组后面 append,相当于 vector::push_back……

gold_hash_map::operator[]

使用有效的方式传递参数(Key),如果参数比较复杂,就用引用传,如果比较简单,就直接拷贝。

性能测试

这个 map 和通用的 hash_map 接口非常相似,所以就直接用 google sparse hash map 的性能测试代码了,具体的测试结果在这里

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

您可能感兴趣的文章:

发表评论

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