【Day9】[资料结构]-杂凑表Hash Table

杂凑表(Hash Table)又称哈希表，是透过杂凑函式(Hash Function)来计算出一个键(key)与值(value)所对应的位置，进而建立杂凑表格，而後也能够过杂凑函式来搜寻找出键值存放在表格的位置。由於动作都需要先经由杂凑函式来执行，若不被知道杂凑函式情况下，保密性就极高，因此很常被应用在加密、解密、压缩、验证等领域。

概念如下图所示:

杂凑表一些专有名词

• 桶(Bucket):杂凑表中储存资料的位置，每一个位置对应唯一位址(Bucket Address)。
• 槽(Slot):每一个桶中的资料栏位，例如：一笔资料有2个栏位，则代表桶中有2个槽。
• 碰撞(Collision):若2笔资料经过杂凑函数运算後的杂凑值相同，也就是对应到相同位址时，称为碰撞。
• 溢位(Overflow):资料经过杂凑函数运算後，杂凑值所指向的桶位址已满，无法再储存，称为溢位。

杂凑函式设计原则

• 尽可能降低碰撞与溢位的产生
• 不宜过於复杂，越容易计算越佳
• 尽可能把文字转换成数字的键值
• 得到的杂凑值，尽可能分布均匀在每个桶中，不要过於集中。

常见的杂凑函式(Hash Function)

1.除法(Mod/Division)
相除取余数来当作杂凑值。
例如:有11个Bucket，若有数值4。
4 mod 11 = 4，杂凑值为4。

2.中间平方法(Middle Square)
将值平方後，再取适当的中间位數作为杂凑值。
例如:有1000个Bucket，若有数值235。
235 X 235 = 55225，取中间三位数，杂凑值为522。

3.折叠相加法(Folding Addition)
相加方式分为两种:

• Shift(移位)
  例如:一个大数值987586265，拆分成3段相加，987+586+265，杂凑值为1838。
• Boundary(边界)
  例如:一个大数值987586265，拆分成3段，可分为基数段反转或偶数段反转，偶数段反转为: 987+685+265，杂凑值为1937。

4.数位分析法(Digits Analysis)
假设栏位资料已知，又属於同一位数，若很集中则舍弃该位，若很分散则挑选该位。
例如: 手机号码栏位，都是09开头+8位号码，舍去09，取用8位号码作为杂凑值。

碰撞(Collision)与溢位(Overflow)常見的处理方式

1.线性探测法(Linear Probing)
假设2笔资料得出一样的杂凑值，将以线性方式往後寻找直到有空的Bucket为止，一般来说也会视为环状结构，若後面Bucket都满了，可以循环到前面寻找。

2.平方探测法(Quadratic Probing)
透过 (H(x) ± i²) mod b，b为bucket數，1 ≤ i ≤ (b-1)/2，用此公式去寻找其他有空的Bucket。
第一次寻找: (H(x) + 1²) mod b
第二次寻找: (H(x) - 1²) mod b
第三次寻找: (H(x) + 2²) mod b
第四次寻找: (H(x) - 2²) mod b…...以此类推。

3.链结法(Chaining)
使用链结串列(Linked List)资料结构在每一组Bucket中。

链结串列的介绍可以参考此篇。

4.再杂凑法(Rehashing)
准备多个杂凑函式，当一个发生溢位时，则使用第二个函式，以此类推。

杂凑表初始的阵列规模若太小，容易造成碰撞次数增加，而需要多次的碰撞处理;若规模太大，容易造成过多未储存数据的阵列空间，因此初始设定适当的阵列规模相当重要。