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 中的应用