数据结构（邓俊辉）学习笔记】词典 03—— 排解冲突(1)

1. 一山二虎

此前我们已经多次指出，对于需要动态维护的散列表冲突是不可避免的，无论你的散列函数设计的有多么精妙，因此我们不得不回答的第二个重要问题就是一旦发生冲突，我们应该如何加以排解？

当然任何一种可行的排解方法都应该是在事先就约定好的预案。

所谓冲突，形象地说也就是一山不容二虎。那么倘若的确有两只老虎呢？用铁丝网将这座山分成两部分，两只老虎各居一侧。这种思路也就是所谓的多槽位法。如果此前的桶单员对应于山，那么每一个 slot 就对应于在这个山中用铁丝网分割出的一个子区域。

在这幅图中，如果这是散列表，那么这就是一个又一个的桶单元。在这里我们将每个桶单元都继续细分为 a、b、c、d 四个槽位。每个桶内部的这些槽位就可以用来存放彼此冲突的若干个词条。

比如这就是一个长度为 23 的散列表，其中每一个桶都被分成了三个槽位。现在我们依次将24个词条插入其中。

可以看到这里，尽管有些词条的确会彼此冲突，但依然可以在对应的桶中和平共处。当然，查找过程需要多出一步，除了需要根据关键码确定对应的统单元地址，还需要在桶中遍历所有的槽位，直到找到目标或者失败。

当然，只要每个桶中槽位的总数能够控制在常数以内，整体的查找效率就不会有实质的降低。

不过这种方法的缺点也是显而易见的，你能看得出来吗？是的，每一桶具体应该细分为多少个槽位？在事先几乎是无法预测的。如果分得过细，就会造成空间上的浪费。而反过来，无论你分得多细，在极端情况下仍有可能在某个特定的桶中发生大规模的冲突。那么面临这一两难的抉择如何破解呢？

2. 泾渭分明

多槽位法在空间效率和时间效率之间的两难处境？我们在学习向量时也曾遇到过，还记得那时的解决办法吗？是的，改用列表。

新的策略，如这幅图（上图）所示，如果这是整个桶数组，那么其中每一个单元都将各自拥有一个对应的列表。而每一个列表都可以用来存放一组彼此冲突的词条。是的，将相互冲突的词条串接起来，也就是所谓的 separate chaining。

来看独立链法的一个实例，依然是一个长度为23的散列表。接下来我们将64个词条插入其中。请留意观察每个桶所对应的列表是如何演化的。
~  
相对于与多槽位法独立链法的优势非常明显，比如除了最初的空链表，我们无需预留任何更多的空间。而且表的长度可以根据需要自由的伸缩。只要系统的资源足够，任意多次的冲突都可以解决。

得益于此前对 List 结构的良好封装，我们只需寥寥几句即可实现相应的散列表结构。当然，这种方法的缺点也同样是很明显的。比如这里需要引入额外的指针，而为了生成或销毁节点也需要借助动态内存的申请，相对于常规的操作，此类动态申请操作的时间成本大致要高出两个数量级。

然而这种方法最大的缺陷还不仅于此，你能发现吗？是的，系统的缓存功能。在这里，每桶内部的查找都是沿着对应的列表顺序进行的。然而在此之前，不同列表中各节点的插入和销毁次序完全是随机的。比如可能会是这样(上图中的黄色线条)。

因此，对于任何一个列表而言，其中的节点在物理空间上往往不是连续分布。因此系统很难预测你的访问方向，无法通过有效的缓存加速查找过程。当散列表的规模非常之大，以至于不得不借助 IO 时，这一矛盾就显得更加突出了。 那么为了有效的激活并充分利用系统的缓存功能，我们又当如何继续改进呢？

3. 开放定址

反观独立链法，其采用的是所谓封闭定址策略 closed addressing。也就是说，对于散列表中的任何一个单元，在其所对应的列表中能够存放，而且只能够存放那些与这个桶单元的地址，比如 k ，相冲突的词条。

也就是说每个词条应该属于哪个桶所对应的列表都是在事先已经注定了的。不难理解，只要采用这种策略，就很难保证每组冲突的词条在空间上能够彼此毗邻。 因此后续我们应该放弃这种策略并反其道而行之，也就是采用所谓的开放定址策略 open addressing。

这种策略的特点是散列表所占用的空间在物理上始终是地址连续的一块，相应的所有的冲突都在这块连续的空间中加以排解，而无需向独立链法那样申请额外的空间。没错，所有的散列以及冲突排解都在这样一块封闭的空间内完成。

因此相应的这种策略也可以称作为闭散列 closed hashing。既然是闭散列，那么每一个桶单元都应该面向所有可能的词条开放。也就是说在特定的情况下，每一个词条都有可能存放在任何一个桶中。

当然对于每一个特定的词条具体存放在哪个桶中是有不同的优先级的。其中优先级最高的自然是它本来就应该归属的那个桶。从这个桶开始，所有的桶都按照某种优先级关系排成一个序列。

而在查找对应的词条时，我们也总是从这个序列的起点出发，顺次去尝试每一个桶单元。每个词条所对应的这样一个序列，也称作试探序列、试探链或者查找链。当然，沿查找链的查找，同样有两种结果，或者在某一个特定的桶中找到目标元素，也就是所谓的成功，或者一旦抵达第一个空桶即可报告失败。

那么具体的应该如何来约定查找链呢？

4. 线性试探

查找链的第一种组织方法就是所谓的线性试探。具体来说，所谓的 linear probing 就是一旦发生冲突之后，我们会转而去试探它的后继，后继的后继，以及后继的后继的后继，诸如此类。同样的，最终可能会因为发现目标而报告成功，或者因为抵达某个空桶，而说明查找失败。

可以看到，在如此形势的散列表中，除了数据词条，无需任何附加空间。

而更重要的是，每一查找链都集中在某一局部。因此系统的缓存作用将得到充分的发挥，而对于大规模的数据集，如此更可以有效地减少 IO。当然，这种策略同样也具有它的弱点。

其中重要一点就是为了消除以往的冲突，可能会导致后续发生更多的冲突。来看这样一个实例，考察一个长度为7的散列表。

假设我们需要插入的是 0 1 2 3 7 这样 5 个词条，如果就按照这种顺序依次插入，那么首先是0就位，1 就位，2 和3 也相继就位。为了插入最后的7，我们首先去试探 0 号单元，结果发现它非空，为了排解这一冲突，我们会转而试探它的后继，也就是 1 号单元，情况一样，进而去试探 2 号 3号单元，直到最终在4号单元发现一个空桶，从而将7安置在这个桶中。在这个散列表的生命期内发生冲突的只有一个词条，也就是7。
~  
现在再来看另一插入次序，比如将 7 调整到最前端，首先插入它，我们依然开始于一个空的散列表。按照约定的次序，首先将 7 安置在0号桶，没有冲突。既然0号单元已被占用，所以接下来插入 0 必然发生一次冲突，并经过一次试探，最终将 0 安置在 1 号单元。至此1号桶也会被占用。因此接下来词条 1 的插入也会发生一次冲突，并最终将它安置在 2 号桶。这样的故事还会发生多次，具体的也需要在这个位置发现一次冲突之后，再将词条2存入到3号桶，最后依然要经过一次冲突，才能将词条 3 存入 4 号桶。在整个这样的过程中，词条0、词条1 2和3都发生了冲突。前后对比不难发现后一种插入序列所对应的很多冲突本来的确是可以不必发生的。

5. 赖惰删除

以线性试探为代表的开放定址策略在使用时若要支持词条的删除，则需格外的小心。我们来就此做一探讨。按照这种策略先后插入彼此冲突的一组词条都将存放在同一个查找序列中。而更确切地讲，他们应该按照逻辑次序构成整个查找链的一个前缀，其中不得有任何的空桶缝隙。

因此词条的删除操作需要做额外的一些处理。反之如果直接将词条删除，那么被删除的词条所留下的空桶就有可能将查找链切断，从而导致在此之后的词条丢失掉。尽管他们的确存在于散列表中，却如何也访问不到。

针对这一问题，一种简明的方法就是所谓的懒惰删除 lazy removal。也就是说如果在某个桶中此前曾有一个词条，那么在这个词条被删除之后，我们并不是简单地将这个桶清空，而是为其做上一个特殊的标记，比如说R，在这样一个桶所属的每一条查找链中，这类桶单元将根据具体情况可能扮演两种角色。

如果是针对某一特定词条的查找，那么在抵达这个桶时，根据这个标志我们就知道不应该在此中断，而因越过它继续查找下去。反过来，如果我们是为了插入新的词条而寻找一个空桶，那么在首次抵达带有这样一个标志的桶之后，就可以将它等效的视作是一个空桶，并将待插入的新词条径直的插入其中。

应该说针对开放定制策略，懒度删除不仅是不得已而为之的方法，也甚至可以说是针对这种情况的最优方法。因为毕竟在开放定址策略中，每一个同单元都同时属于多个查找链。