前一段时间写了个 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 的性能测试代码了，具体的测试结果在这里。