1. 基本的hash连接算法
建立对于关系R的hash表
在该hash表上进行probe
如果在关系S中的id拥有和关系R中id一样的值。那么他们利用相同的hash函数进行映射之后。就必然会去到相同的桶内。
2. Probe 阶段的优化
可以创建Bloom Filter进行优化。
何谓Bloom Filter
Bloom-Filter，即布隆过滤器，是一种多哈希函数映射的快速查找算法。通常应用在一些需要快速检测一个元素是否在一个集合中，但是并不严格要求100%正确的场合。Bloom Filter的空间利用效率很高，使用位数组表示一个待检测集合，使用它可以大大节省存储空间。利用这个算法我们可以实现去重效果。
Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元素不在集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误（不在的一定不在，在的不一定在）。
看一个例子。如果我们存入baidu
Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：
加入我们现在查询alibaba。它经过哈希函数如果返回3、7、8我们会发现这三个位全为1.这样如果我们就会认为alibaba已经存在了。所以这也就是Bloom Filter不保证完全正确的原因。
引入Bloom Filter之后我们可以在探测之前先利用它进行判断。
3. GRACE HASH JOIN
适合于内存比较小的情况
从头进行比较。如果相同则进行join
如果某一个桶内的元素太多。内存中无法放下。则进行递归分块。利用不同的hash函数进行rehash
时间复杂度分析