Day-25 Hash Function(杂凑函数), 乘法杂凑法, 除法杂凑法

Hash function

一个好的杂凑函数，可以把 $key$ 均匀的分布在杂凑表的每一个slot中，也就是尽量满足简单均匀杂凑的假设，而且 $key$ 分布的均匀性，不会受到元素的影响，也就是说，一个好的杂凑函数，我们希望它所产生的杂凑值，可以独立於输入的元素。

Division method(除法杂凑法)

在杂凑函数中，除法杂凑法是很常见的杂凑函数，令 $key$ 为 $k$ ，杂凑表 $T$ 有 $m$ 个槽，我们通过取 $k$ 对 $m$ 的余数，将 $k$ 映射到 $T$ 的其中一个槽中，可以用以下的式子表示这个杂凑函数

$h(k) = k\ mod\ m$

使用这个杂凑函数时，我们需要避免一些情况的发生。

杂凑表可用的槽需要够多，假设 $m=2$ ，则产生出的杂凑表分布的将不够平均，只有两条链结串列，导致效率低落。
如果我们给定的 $key$ 和 $m$ 都恰好为偶数，那麽我们只能使用 $T$ 一半的槽，不仅浪费许多空间，且违反的我们对於杂凑函数的期望，也就是 $key$ 分布的均匀性不受到输入元素的影响。
如果我们给定 $m=2^p$ ，则 $h(k)$ 就是 $k$ 的 $p$ 个最低位数字，而这样的情况下，除非 $p$ 个最低位数字他们是均匀分布的，也是以二进位观点，0和1都是均等出现的，那麽才能保证杂凑表有较好的效率，否则一般设计时，我们都会优先考虑到元素的所有位数。

0010101011001, m=2^6，那麽我们会使用到的数字为

011001=h(k)，而在二进位中，1和0的出现通常都具有一定的规律性，这会导致我们产生出的杂凑情况不够均匀

一般情况下，我们在取 $m$ 的时候，会选择一个不接近2的整数幕的质数，而这样取 $m$ 的情况下，往往会产生出比较好的结果。像是 $m=701$

除法杂凑法很常在程序中见到，因为他的程序码量不多，且效果不会太差，但相较於其他基於加法和乘法的杂凑函数，除法在电脑中需要花费更多的计算步骤，造成更多时间的消耗。

Multiplication method(乘法杂凑法)

在实际处理资料时，我们常常无法事先得知 $key$ 的范围，或是 $key$ 具有的特性，像是全部都是偶数之类的，这时候，乘法杂凑表就是一个不错的方法可以使用。

假设 $m=2^r$ ， $m$ 表示hash table的槽数，且在一部电脑中，每一个bytes含有 $w$ bits，则杂凑函数为

$h(k)=(A*k\ mod\ 2^w) >> (w-r)$

$>>$ 表示向右偏移(right shift)的意思，就是二进制的偏移, A是一个奇数，范围介於 $2^{w-1}<A<2^w$ , $k$ 表示 $key$ 。

这个方法的关键在於 $A$ 的选取，在选取 $A$ 时我们必须避免选取一些特定的数值，像是选择 $A$ 时要尽量避免以2为底的数字，像是2,4,8,16等数字。

基本上这个方法是一个相当快速的方法，相乘後再取余数会比起直接除法要来的更快，且二进制的偏移运算本身就十分快速，尤其是在我们进行杂凑运算之前。我们就已经得知需要偏移的位元数的情况下，又来的更加的快速。

Example 1. 假设我们有一个hash table，有8个槽， $m=8=2^3$ ， $w=7$

这个杂凑函数的关键就在於A的选取，假设A = 1011001(Bin) = 89(dec)，2^w-1 = 64, 2^w = 128。
然後选取一个key来乘上A，k = 1101011，接着计算A * k

        1011001 = A
*       1101011 = k
 __________________
 10010100110011
 
 得到A和k的乘积後，接着对2^7取余数，也就是取出前7位数字
 
 1001010__(0110011), 接着向右偏移(w-r)位，也就是(7-3) 
 
 0110011 >> (7-3) = 0000011，也就是取出最高位的前3位数字，而这个值就是h(k)了

而为什麽乘法杂凑法是一个很不错的演算法，我们引用下面图形进行说明，在说明之前，我们先进行一些假设

       1011001 = A
*      1101011 = k
 __________________
 10010100110011
 
 假设A是一个小於1的数，则我们可以在A的最高位天加上一个小数点，如下面所示
 
       .1011001 = A
 *      1101011 = k
___________________
1001010.0110011

而取余数的计算就是忽略掉整数部分，保留小数部分，以这个例子来说，A的小数部分以10进制来说大约是5.5左右。
而假设k = 1,2,3,4,5....

有了上面的假设，我们可以以一个环来表示一个规律

当k = 1时，A*k取小数部分大约为 $5.5/8$

当k = 2时，A*k取小数部分大概是 $3/8$

而乘法杂凑法就是运用这样的想法，让 $key$ 平均的分布在hash table中每一个槽里。而这也就是为什麽这是一个不错的杂凑方法，既可以保证计算的速度，又可以保证 $key$ 分布的平均性。