哈希表放不进内存时
内存中的哈希连接先为左表建立哈希表,再用右表逐条查找。若左表太大,整张表就放不进内存。分割法把问题拆小:将两个文件中键相同的记录送往同一个编号的分割区;第二趟再逐对连接分割区。这常称为 Grace 哈希连接。其优点取决于分割区是否真的放得下;热门键或不均匀的分布都可能使某个分割区过大。
我们研究有限的内等值连接,采用多重集语义;键不为空值,且比较是精确的。
定义 20.3.1
(多重集等值连接与分割函数)
文件中每个位置都是一个不同的记录实例,即使两条记录看起来完全相同。 与 的多重集内等值连接,对每个键相等的左记录实例 与右记录实例 恰好含一个有序对 ,此外没有其他配对;输出无须排序。分割函数是把键映到 ()的映射 ,在整次运行中固定不变;因此相同的键必有相同的哈希值,而不同的键可以碰撞。
概念视角代数
把连接大小看成内积
以 、 表示键 在 、 中的实例数。多重集等值连接是对所有键 ,把键为 的 对取不相交并集,所以 正是两个重数向量的内积。分割函数把键集分成各类 ,这个和式也随之分成每个分割一项;这正是对应分割可以各自独立连接的原因。在下面第一个例题中,。
两趟算法与内存条件
设文件 分别占 个块。读取或写入一个块都算一次传输。分割时使用一个输入缓冲区及 个输出缓冲区;每条记录送往其分割区,最后把每个非空的未满缓冲区写出。各分割文件分别紧密存储、保留全部记录实例,并写到新的存储空间。设两侧第 个分割文件各占 个块,令 、。由于各分割文件须各自写出最后的未满块, 可以大于 , 也可以大于 ;空分割区不占块。
第二趟将每个 的全部记录实例读入内存哈希表,然后读取 一次。每次查找都将实际键与相应哈希桶中的所有候选记录比较,并对每个键相等的左记录实例输出一对。表可以用第二个哈希函数组织;它同样必须把相同的键送往同一个哈希桶,而表内碰撞必须用键的相等比较来处理。所有分割区共用一个输出缓冲区,只在写满或最后结束时写出。
每个 的表连同索引开销都必须放进 个内存块,另留一块读取 、一块用于输出。因此本模型的预算至少是 个块;小型控制描述信息不计。这里没有假设分割文件仍在缓存中,也不计压缩、索引访问或跨趟沿用输入缓冲区。
定理 20.3.2
(多重集语义下的正确性)
在上述条件下,若两个文件使用同一个分割函数,算法的输出恰为多重集等值连接:每对键相等的记录实例恰好输出一次,此外没有其他配对。
证明
(每对键相等的配对恰好相遇一次)
每个输入记录实例恰好送进一个分割区,并被保留。对任意键相等的 ,由于函数固定且相同的键有相同的值,两者都进入同一个分割区 。建表时 被读入一次;查找时 被读取一次,并检查相应哈希桶中的所有候选。实际的键比较接受 ,故这一对被输出一次。每个记录实例只有一个分割区,每个查找记录实例只处理一次,因此不会在别处再输出同一对。反过来,输出前必须通过实际的键比较,所以不同键之间的碰撞不会产生错误配对。这个论证逐一计算记录实例,而不是只计算不同的值。
这个证明用了两种不同的机制,各自处理对方无法处理的失误。
证明透视
两种检查各有用途
分割函数决定哪些记录可以相遇;实际键的相等比较决定哪次相遇会产生输出。完整性只用到前者:由于两个文件使用同一个固定的 ,相同的键必定落在同一分割区,所以没有相配的一对会被分开。可靠性只用到后者:哈希可能碰撞,同在一个分割区或一个桶中只算候选,键比较会剔除跨键配对。恰好输出一次则依赖第三个较隐蔽的事实:每个记录实例只送往一个分割区,每个查找记录实例只读一次。正因如此,论证计算的是记录实例而不是不同的键,重复项会相乘而不是合并。
命题 20.3.3
(块传输次数)
若每张建立的表都放得下,输出共有 对,每个输出块可放 对,则算法的传输次数恰为
当 时最后一项为零。此数包括输出落盘及所指定分割文件的传输,不包括计算、寻道、故障或删除存储数据的成本。
证明
(把互不重叠的传输阶段相加)
原始文件扫描需 次读取;写入分割文件需 次,再读取以建表及查找需同样次数,包括全部非空分割区。紧密打包的输出需 次写入。把这些互不重叠的传输相加就得到公式。表能放入内存是必要条件:若某个分割区放不下,所述的第二趟就不能照此执行,公式也不是这种情况下的成本。
例题 20.3.4
(重复、碰撞及未满块)
设输入块及分割块各可放两条记录,,且
按奇偶分割。左侧奇数文件为 、偶数文件为 ,分别需 个块;右侧奇数文件为 、偶数文件为 ,分别需 个块。所以 、、。假设两张左表都放得下,键 1 产生两对、键 2 产生两对、键 4 产生一对;键 3 没有配对。偶数区中不同的键 2 与 4 虽然同区,相等比较仍会拒绝跨键配对。因此 ,传输次数为 。 中的两个 2 不能合并成一个。
常见错误
(把同区当作配对)
上例的偶数区中,键 与 同在一个分割区,也可能同在一个哈希桶。若输出桶内所有候选,就会加入跨键配对 与 ,共 对错误配对( 有一个 和一个 ; 有两个 和一个 )。分割区及哈希桶的碰撞只产生候选;使输出正确的是最后的键相等检查。
常见错误
(合并重复的记录实例)
在多重集语义下, 中的两个 是不同的记录实例。若在连接之前把 去重,或在建表一侧每个不同的键只保留一个表项,上例就得到 而不是 。若需要的是集合语义,那是另一种输出约定,必须明确说明。
计数公式在没有任何配对时同样适用;这个边界情形显示哪些项仍然保留。
例题 20.3.5
(带空分割区的空连接)
沿用同样的块大小及奇偶分割,取 、,故 。左侧奇数文件用一个块存放 ,左侧偶数文件为空;右侧奇数文件为空,右侧偶数文件用一个块存放 。所以 。奇数区建表但没有查找;偶数区建立空表,仍读取其一个 块,找不到配对。因此 ,不写出输出块,传输次数为 。
内存预算必须同时照顾两趟,由较大的需求决定。
例题 20.3.6
(核查内存预算)
设有 个分割缓冲区,且最大的建立表需 个块。分割趟需 个块,查找趟需 个块,故预算至少为 个块。若只有 个块,分割趟仍可运行,但最大的分割区无法用所述的第二趟连接;必须先再分割或改用其他方法,上面的计数才适用。数字 也不说明另一份输入的情况,其最大表必须另行检查。
反例模式
平均分割区小,不代表每个分割区都放得下
断言:若平均分割区放得下,每个分割区都放得下。假设 有 100 个同键记录实例,而表只能容纳 20 个。分成十区时平均每区十个,但相同的键必须送往同一区,所以这一区仍有 100 个。只改变键的哈希函数,不能在保留上述简单算法的前提下拆开这一组。同样,整体块数看似平均,也不足以保证最大的分割区连同索引开销都能放入内存。修正后的假设就是条件中的那一条:最大的建立表放得下。
条件失效时怎么办
若某个分割区过大,可以用另一个函数再次分割,但必须对两侧使用同一函数。若过大是由许多不同的键造成,这可能有帮助;若全是同一个重复键,只按键分割就不能把它拆开。另一种做法是对该区使用块嵌套循环,或明确拆分热门键并复制或重新扫描另一侧的配对数据。这些都是不同的算法,有额外的传输及内存条件。声称两趟成本之前要先检测溢出,并把失败的尝试及后续处理一并计入实际成本。
输出庞大是另一个问题。若一个键在左、右两侧分别出现 次,它就产生 对。需要物化结果时,分割函数无法消除输出这些配对的工作。分割也不保证输出顺序;若下游要求排序,须另作处理。输入记录、临时分割及输出配对的大小可以不同,因此应计算实际块数,不应直接假设 。
练习与解答
快速检查
(键 在左侧出现三次、右侧出现四次,输出多少对?)
数出记录实例的有序对。
解答 · 答案
每个左记录实例都与每个右记录实例配对,共 对。外观相同的记录仍是不同的记录实例。
快速检查
(设 、、、、、,且所有左表都放得下。按所述程序计算传输次数。)
把输入扫描、分割写入与读取,以及打包输出相加。
解答 · 答案
原始读取需 次,分割写入及读取需 次,打包输出需 次,共 次。
快速检查
(设 、。若 按奇数键 、偶数键 分割, 却按相反的规则分割,第二趟输出什么?哪个假设失效了?)
找出每个 的记录实例落在哪个分割区。
解答 · 答案
左侧的 送往分割区 ,右侧的 送往分割区 ,两者从不在对应的分割区中相遇,所以输出为空,而正确的连接有一对。正确性定理要求两个文件使用同一个分割函数;两个函数各自固定,但两个文件之间相同的键已不再相遇。