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

2007 年我写过一篇关于平行数组与CPU缓存文章，最近，我在 hash_strmap 和 gold_hash_map 中应用了这种设计思想。

hash value cache

　　对于一些对象，计算它们的 hash value 很昂贵，而对于另外一些对象，计算它们的 hash value 很廉价；所以，我们是否做 hash 缓存对 hash table 性能很重要。

更有意思的是，hash 缓存一般只在 hash table 的增长阶段访问（rehash），而在查找阶段，不需要访问 hash 缓存，于是，可以把 hash cache 从数据结构的结点中提取出来，放到一个分离的平行数组中。所谓平行数组，也就是：以前是访问 pNode[i].hash，现在是 pHash[i]，很简单的概念。

　　更有意思的是，我们可以随时启用(enable)或禁用(disable) hash 缓存，在 hash_strmap 的测试中，启用它大约会使插入操作的平均性能提升一倍。具体到实现上，我们甚至不需要额外的变量来表示 hash 缓存是否启用，只需要将 pHash 设成一个特殊的值来表达它是禁用的，现在设的是整数 8 （与“不”谐音），当然需要强制类型转换pHash = (size_t*)(8)。

link array

　　这个仅使用在 gold_hash_map 中，因为在 hash_strmap 中，link 和 offset (指向 strpool 的偏移)一起占用 8 字节（在64位环境中刚好一个指针宽度）。

hash table 使用开地址解决 hash 冲突，这样在同一个桶(bucket) 中的所有 Node 是用一个单向链表链接起来的，传统实现是使用指针做链接，gold_hash_map 和 hash_strmap 使用数组下标做链接，这样不但可以在任何时候重新链接（比如gold_hash_map 和 hash_strmap 都支持排序，而排序打乱了数组下标，所以排序之后需要重新链接），并且，在 64 位环境中还可以节约一半的内存。

　　传统的做法是将 link 作为 Node 的一个成员，这样很简单也很自然，gold_hash_map 一开始就是这样实现的，然而，仔细分析我们会发现，在 hash table 的查找中，对 link 访问的概率是很低的，请看代码：

	size_t find_i(const Key& key) const {
		size_t n = nElem;
		HashTp h = HashTp(hash(key));
		size_t i = h % nBucket;
		for (LinkTp p = bucket[i]; tail != p; p = pLink[p]) {
			if (equal(key, keyExtract(pElem[p])))
				return p;
		}
		return n; // not found
	}

　　只有在桶(bucket)中得到的第一个 Node 不匹配 key 的时候，才需要访问 link，而在 hash table 中，这样的第一个 Node 不匹配 Key 的概率是相对很小的，并且把它控制得很小是一个 hashfunc 优劣的评价标准。

　　另一方面，虽然内存现在很白菜价，并且会继续更加白菜价，然而CPU cache仍然非常昂贵。如果link和data成员都放在Node中，CPU加载data (代码中的Elem)时也会加载link，而加载进来的link却很少会被访问到。这就是为什么要把link分出去。

　　将link分出去还带来了一个额外的好处：hash cache 分出去了，link 也分出去了，Node 中现在就只剩下 data 了，Node 就没有存在的必要了，Node数组就是 data 数组了！这样完全省去了专门写 iterator 的代码，直接将 iterator 定义成指针就OK了。

查找失败时

查找总有找不到的时候，当查找的 Key 不存在的时候，并且 h%nBucket 刚好打进一个不空的桶：

　　在上面 find_i 函数中，调用 equal 之前先判断一下 hash 缓存会更快，因为在随机情况下h1%n == h2%n 时，h1 != h2 的可能性要大得多。

　　并且，在这种情况下，需要遍历完整个 linked list 才能知道 Key 真的不存在，所以此时至少需要访问一次 pLink 数组。

　　似乎此时变得很坏！然而再仔细分析上面的条件：只有在 Key 不存在，并且并且h%nBucket刚好打进一个不空的桶！如果我们把 hash tab 的装载因子 （load factor）设得小一些，比如（0.3），这个概率就会变小，从而对 pLink 数组的访问需求也变小了。因为 link 用的是整数，所以，如果我们知道整个 hash tab 不会装太多东西，我们可以把 LinkTp 设成较小的整数类型（比如 unsigned short，16位，这样最多可以在 gold_hash_tab 中装入 65535 条记录）。从而，相同的内存空间，我们可以把装载因子调得更小，从而使得访问 pLink 数组的概率更小，并且 hash 冲突的概率也更小了。

　　hash_strmap 的 LinkTp 是固定的(unsigned int)，无法改变，这是刻意为之，因为这种灵活性对 hash_strmap 带来的好处太小了，不值得付出那么多努力。

总结

使用了这么多的技巧和设计思想，结果如何呢？gold_hash_map 完败几乎所有 hash map 的实现！