gold_hash_map design
前一段时间写了个 hash_strmap, 效果不错,其中的一些设计思想可以扩展。于是,昨天到今天两天写了一个通用的 hash_map, 起了个名字叫gold_hash_map。
内存使用
和 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 的性能测试代码了,具体的测试结果在这里。