Hash
join is one of the three join types in execution plans in SQL Server. The other
two are nested loops join and merge join.
Hash
Join就是利用哈希算法作匹配的联接算法。简单来说，哈希算法分成两步，“构建哈希桶(Build hash bucket)”和“探测哈希桶中的值(Probe hash bucket)”。在“Build”阶段，SQL Server选择两个要做Join的数据集中的一个，根据记录的值建立起一张在内存中的Hash表。然后在“Probe”阶段，SQL Server选择另外一个数据集，将里面的记录值依次带入，返回符合条件可以做联接的行。
In other words, SQL Server 选择两个需要join的表中的一个a，对于a中的每一个记录R1，计算其联接列的hash值，然后根据hash值将R1插入到hash bucket当中。选择另外一张表b，对于b中的每一条记录R2，我们也计算其联接列的hash值，然后去hash bucket上查找。如果Hash bucket上有R1能够跟R2进行连接，那么就输出 (R1, R2) 的联接结果，可能有多个R1的记录。
那么，到底什么是HASH表？数据库中一个记录的HASH值又是如何被计算出来的呢？
Hash，一般翻译做“”散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码, 这些编码值叫做HASH值。也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。
除了节省空间和通过加密提高安全性外，HASH还综合了数组（Array）和链表（Linked Lis）的优点。Array is a series of objects in the
same size and type. It is a data structure consisting
of a collection of elements (values or variables), each identified by at least one array
index or key. An
array is stored so that the position of each element can be computed from its
index tuple by a
mathematical formula. The
simplest type of data structure is a linear array, also called one-dimensional
array. 因此，数组的特点是：寻址容易，插入和删除困难。Linked list is a data structure consisting
of a group of nodes which
together represent a sequence. Under the simplest form, each node is composed
of a data and a reference (in
other words, a link) to
the next node in the sequence; more complex variants add additional links. This
structure allows for efficient insertion or removal of elements from any
position in the sequence。换句话说，链表的特点是：寻址困难，但插入和删除容易。而Hash table 则具备了两者的优点。How
come？
这主要是通过哈希的构造实现的。哈希表的具体构造方法有很多种，主要有直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。这里举除留余数法或除法散列法为例。具体做法是取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)。
如在下图中, 左边的0-15为Array(数组)，右边那些节点的数字则是Linked
List中的元素。假定我们使用了HASH(key) % Entry [].length或者更具体点是 index = hash (key) % 16。并且进一步假定Hash
(key=12) %16=12, Hash (key=28) %16=12, Hash (key=108) %16=12, Hash (key=140) %16=12。那么12、28、108以及140这些元素都会存储在数组下标为12的位置。
