Hash算法原理

　　对于什么是Hash算法原理？这个问题有点难度，不是很好说清楚，来做一个比喻吧：我们有很多的小猪，每个的体重都不一样，假设体重分布比较平均(我们考虑到公斤级别)，我们按照体重来分,划分成100个小猪圈。 然后把每个小猪，按照体重赶进各自的猪圈里，记录档案。 好了，如果我们要找某个小猪怎么办呢？我们需要每个猪圈，每个小猪的比对吗？ 当然不需要了。 我们先看看要找的这个小猪的体重，然后就找到了对应的猪圈了。 在这个猪圈里的小猪的数量就相对很少了。 我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。 对应于hash算法。 就是按照hashcode分配不同的猪圈，将hashcode相同的猪放到一个猪圈里。 查找的时候，先找到hashcode对应的猪圈，然后在逐个比较里面的小猪。 所以问题的关键就是建造多少个猪圈比较合适。 如果每个小猪的体重全部不同（考虑到毫克级别)，每个都建一个猪圈，那么我们可以最快速度的找到这头猪。缺点就是，建造那么多猪圈的费用有点太高了。 如果我们按照10公斤级别进行划分，那么建造的猪圈只有几个吧，那么每个圈里的小猪就很多了。我们虽然可以很快的找到猪圈，但从这个猪圈里逐个确定那头小猪也是很累的。 所以，好的hashcode，可以根据实际情况，根据具体的需求，在时间成本(更多的猪圈，更快的速度)和空间本(更少的猪圈，更低的空间需求)之间平衡。(摘自网络)

Hash JOIN基本过程（可对比《hash join的模式》）

　　如果两个表（分别命名为表T1和表T2）在做表连接时使用的是哈希连接，则Oracle在做哈希连接时会依次顺序执行如下步骤：

1、确定Hash Partition的数量：首先Oracle会根据参数HASH_AREA_SIZE、DB_BLOCK_SIZE和_HASH_MULTIBLOCK_IO_COUNT的值来决定Hash Partition的数量（Hash Partition 是一个逻辑上的概念，所有Hash Partition的集合就被称之为Hash Table，即一个Hash Table是由多个Hash Partition所组成，而一个 Hash Partition又是由多个Hash Bucket所组成）；

2、确定驱动结果集：表T1和T2在施加了目标SQL中指定的谓词条件（如果有的话）后得到的结果集中数据量较小的那个结果集会被Oracle选为哈希连接的驱动结果集，这里我们假设T1所对应的结果集的数据量相对较小，我们记为S；T2所对应的结果集的数据量相对较大，我们记为B；显然 这里S是驱动结果集，B是被驱动结果集；

3、计算哈希值：接着Oracle会遍历S，读取S中的每一条记录，并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算，这个哈希运算会使用 两个内置哈希函数，这两个哈希函数会同时对该连接列计算哈希值，我们把这两个内置哈希函数分别记为hash_func_1和hash_func_2， 它们所计算出来的哈希值分别记为hash_value_1和hash_value_2；

4、分组：然后Oracle会按照hash_value_1的值把相应的S中的对应记录存储在不同Hash Partition的不同Hash Bucket里，同时和该记录存储在 一起的还有该记录用hash_func_2计算出来的hash_value_2的值。注意，存储在Hash Bucket里的记录并不是目标表的完整行记录，而是 只需要存储位于目标SQL中的跟目标表相关的查询列和连接列就足够了；我们把S所对应的每一个Hash Partition记为Si；

5、构建位图：在构建Si的同时，Oracle会构建一个位图（BITMAP），这个位图用来标记Si所包含的每一个Hash Bucket是否有记录（即记录数是否大于0）

6、构建Hash Table过程：如果S的数据量很大，那么在构建S所对应的Hash Table时，就可能会出现PGA的工作区（WORK AREA）被填满的情况，这时候Oracle会 把工作区中现有的Hash Partition中包含记录数最多的Hash Partition写到磁盘上（TEMP表空间），接着Oracle会继续构建S所对应的 Hash Table，在继续构建的过程中，如果工作区又满了，则Oracle会继续重复上述挑选包含记录数最多的Hash Partition并写回到磁盘 上的动作；如果要构建的记录所对应的Hash Partition已经事先被Oracle写回到了磁盘上，则此时Oracle就会去磁盘上更新该Hash Partition， 即会把该条记录和hash_value_2直接加到这个已经位于磁盘上的Hash Partition的相应Hash Bucket中；注意，极端情况下可能会出现只 有某个Hash Partition的部分记录还在内存中，该Hash Partition的剩余部分和余下的所有Hash Partition都已经被写回到磁盘上。（注：

7、上述构建S所对应的Hash Table的过程会一直持续下去，直到遍历完S中的所有记录为止；

8、排序：接着，Oracle会对所有的Si按照它们所包含的记录数来排序，然后Oracle会把这些已经排好序的Hash Partition按顺序依次、并且尽 可能的全部放到内存中（PGA的工作区），当然，如果实在放不下的话，放不下的那部分Hash Partition还是会位于磁盘上。我认为这个 按照Si的记录数来排序的动作不是必须要做的，因为这个排序动作的根本目的就是为了尽可能多的把那些记录数较小的Hash Partition 保留在内存中，而将那些已经被写回到磁盘上、记录数较大且现有内存已经放不下的Hash Partition保留在磁盘上，显然，如果所有的 Si本来就都在内存中，也没发生过将Si写回到磁盘的操作，那这里根本就不需要排序了。

9、至此Oracle已经处理完S，现在可以来开始处理B了；

10、Oracle会遍历B，读取B中的每一条记录，并对B中的每一条记录按照该记录在表T2中的连接列做哈希运算，这个哈希运算和步骤3中的 哈希运算是一模一样的，即这个哈希运算还是会用步骤3中的hash_func_1和hash_func_2，并且也会计算出两个哈希值hash_value_1和hash_value_2； 接着Oracle会按照该记录所对应的哈希值hash_value_1去Si里找匹配的Hash Bucket；如果能找到匹配的Hash Bucket，则Oracle还会遍历该 Hash Bucket中的每一条记录，并会校验存储于该Hash Bucket中的每一条记录的连接列，看是否是真的匹配（即这里要校验S和B中的匹配记 录所对应的连接列是否真的相等，因为对于Hash运算而言，不同的值经过哈希运算后的结果可能是一样的），如果是真的匹配，则上述 hash_value_1所对应B中的记录的位于目标SQL中的查询列和该Hash Bucket中的匹配记录便会组合起来，一起作为满足目标SQL连接条件的记 录返回；如果找不到匹配的Hash Bucket，则Oracle就会去访问步骤5中构建的位图，如果位图显示该Hash Bucket在Si中对应的记录数大于0， 则说明该Hash Bucket虽然不在内存中，但它已经被写回到了磁盘上，则此时Oracle就会按照上述hash_value_1的值把相应B中的对应记录也 以Hash Partition的方式写回到磁盘上，同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值；如果位图显示 该Hash Bucket在Si中对应的记录数等于0，则Oracle就不用把上述hash_value_1所对应B中的记录写回到磁盘上了，因为这条记录必然不满足 目标SQL的连接条件；这个根据位图来决定是否将上述hash_value_1所对应B中的记录写回到磁盘的动作就是所谓的“位图过滤”；我们把B所对 应的每一个Hash Partition记为Bj；

11、上述去Si中查找匹配Hash Bucket和构建Bj的过程会一直持续下去，直到遍历完B中的所有记录为止；

12、至此Oracle已经处理完所有位于内存中的Si和对应的Bj，现在只剩下位于磁盘上的Si和Bj还未处理；

13、因为在构建Si和Bj时用的是同样的哈希函数hash_func_1和hash_func_2，所以Oracle在处理位于磁盘上的Si和Bj的时候可以放心的配对处 理，即只有对应Hash Partition Number值相同的Si和Bj才可能会产生满足连接条件的记录；这里我们用Sn和Bn来表示位于磁盘上且对应 Hash Partition Number值相同的Si和Bj；

14、对于每一对儿Sn和Bn，它们之中记录数较少的会被当作驱动结果集，然后Oracle会用这个驱动结果集的Hash Bucket里记录的hash_value_2 来构建新的Hash Table，另外一个记录数较大的会被当作被驱动结果集，然后Oracle会用这个被驱动结果集的Hash Bucket里记录的hash_value_2 去上述构建的新Hash Table中找匹配记录；注意，对每一对儿Sn和Bn而言，Oracle始终会选择它们中记录数较少的来作为驱动结果集，所以每 一对儿Sn和Bn的驱动结果集都可能会发生变化，这就是所谓的“动态角色互换”；

15、步骤14中如果存在匹配记录，则该匹配记录也会作为满足目标SQL连接条件的记录返回；

16、上述处理Sn和Bn的过程会一直持续下去，直到遍历完所有的Sn和Bn为止。

对于哈希连接的优缺点及适用场景，有如下总结：

1.哈希连接不一定会排序，或者说大多数情况下都不需要排序；

2.哈希连接的驱动表所对应的连接列的可选择性应尽可能的好，因为这个可选择性会影响对应Hash Bucket中的记录数，而Hash Bucket中的记录数又会直接影响从该Hash Bucket中查找匹配记录的效率；如果一个Hash Bucket里所包含的记录数过多，则可能会严重降低所对应哈希连接的执行效率，此时典型的表现就是该哈希连接执行了很长时间都没有结束，数据库所在database server上的CPU占用率很高，但目标SQL所消耗的逻辑读却很低，因为此时大部分时间都耗费在了遍历上述Hash Bucket里的所有记录上，而遍历Hash Bucket里记录这个动作是发生在PGA的工作区里，所以不耗费逻辑读；

3.哈希连接只适用于CBO、它也只能用于等值连接条件（即使是哈希反连接，Oracle实际上也是将其转换成了等价的等值连接）；

4.哈希连接很适合于一个小表（结果集）和大表之间的表连接，特别是在小表的连接列的可选择性非常好的情况下，这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当；

5.当两个表做哈希连接时，如果这两个表在施加了目标SQL中指定的谓词条件（如果有的话）后得到的结果集中数据量较小的那个结果集所对应的Hash Table能够完全被容纳在内存中时（PGA的工作区），则此时的哈希连接的执行效率会非常高。

---整理自网络

Oracle 表的连接方式(2)-----HASH JOIN的基本机制2