提高性能的利器——索引散列表

写在前面

在面试时被问到一道八股文：go语言map存储了1000个1KB大小的对象，和存储了10000个100B大小的对象，哪个占空间更大？这篇文章不仅仅是为了让读者会一道八股文，而是让读者可以从原理上读懂go语言map源码的部分设计。

408的散列

课本上散列表基本就是一个hash(key) % size 逻辑，再加上面对哈希冲突时的解决方案：

• 开放定址法 -> 非同义冲突
• 再哈希法 -> 增加计算量
• 链地址法 -> O(1) 变 O(n)

书接前文

之前有提到过辅助索引, 我们可以基于桶的方式尽量避免哈希冲突。通过使用桶，我们可以将符合某种规则的数据放入一个桶内，然后开始处理使用桶之后带来的隐患：

1. 桶内是否限制最大元素的数量？
2. 桶数量是否固定？
3. 我要如何找到对应的桶？

前两个问题其实是一个问题，数据量增大怎么办？

如果我们想通过不限制最大元素数量的方式解决问题，那么就只能不断地链地址法，这样的查询效率是不允许的。而如果放任桶的数量不断增大，那么其实也是再给第三个问题加大难度。关于如何找到对应的桶，我们可以使用一个指针数组来迅速找到key对应桶的位置，这是在数据量较大的情况下比较合适的办法。如果数据量绝对的小，我们也可以让桶本身就按照连续的方式存储（至少也是每个桶链下面的第一个桶连续存储）。

如何调整桶的数量

在思考这个问题之前，我们先确认下调整桶数量带来的影响：旧数据怎么办？每当我们新增一个桶时，我们都需要将旧数据中应该放入新桶的数据迁入到新桶中，比如说本来只有两个桶，存10个数字

[1, 3, 5, 7, 9],[2, 4, 6, 8, 0]

当我们新增一个桶

[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]

对于每个数字，我都需要重新计算一次桶的位置，这样的效率堪称没有。

为了更好的提高效率，我们基于hash(key)的二进制来确定桶的分布， 取其二进制前n位来决定元素属于2n2^n2n个桶的哪一个。这样的好处是当需要扩展时我们只需要前后n位变为n+1位即可。

这真的能解决问题吗？

虽然我们知道go语言map就是这么做的，但实际上这种办法在空间上依旧存在较大风险，假定我们设置桶内元素最多只有两个，根据前1位决定元素属于那个桶

添加元素0110 0111 以及0100

元素溢出，只能将桶数目翻倍。但我们注意到翻倍并不会解决这个问题 桶1桶2桶3全是空的情况下 桶0还是有三个元素。桶的数据不断翻倍，为存储桶的位置的指针数组的存储，增加了不少压力。

如何解决桶内元素溢出 -> 如何控制桶的增长

针对这个问题，我们可以用设置溢出桶或链地址法的方式解决，当数据量较大时，多个元素都存在一个桶内本身也不合理，这种情况也可以用重新设置hash函数来解决。当然重新设置hash函数本身并不是一个通用的解决方案，或者说他更适用于极端情况，那么在不极端的情况下，我们如何增长桶的数目，可以既缓解溢出问题，又不会造成桶的指数增长呢？

这里需要明确一个问题，单个桶的溢出在单个桶的数量级下解决，使用负载因子来量化桶内元素拥挤的程度，当负载因子过大时，再考虑增加桶的数量。

回到之前的问题，添加元素0110 0111 以及0100时，我们仅需要为桶0设置一个溢出桶，使其变为[桶00, 桶01]的链表 ，这样就可以做到线性的控制桶的增长，同时，虽然桶的数量增加了1，但实际上指针数组依旧可以没有变化，仅需要在get(0001)时找到桶0链表后，再O(n)判断元素究竟在哪个桶。

总结

最后总结下散列表的一些技巧

• 溢出区：解决哈希冲突问题
• 链地址法：在链的长度较小时，O(n)还可以接受。
• 在基于桶的前提下如果获取桶内元素的位置，可以使用数组存储元素的后几位，然后根据数组的索引计算元素存储的位置
• 在基于桶的前提下元素的大小会受到限制，过于大的元素可能会难以对齐（对齐的意义不仅仅是cpu读元素时的性能，也会让我们不能再仅仅通过数组索引来计算元素存储的位置）或者造成大量的空间浪费（比如用16KB存储一个整数1也是一种浪费），为了解决这个问题我们可以对key以及value也仅仅使用指针存储在桶中。