Hash

• 雜湊是透過一個數學函數來計算（或轉換）一個雜湊表中鍵值所對應的位址
• 可以直接且快速地找到鍵值所放的地址, 毋需透過循序搜尋的尋找方式
• 雜湊是一種由鍵值至位址之關係轉換
• 任何透過雜湊搜尋的檔案都不需經過事先的排序。也就是直接以：鍵值→　雜湊函數　→位址
• 一般而言在有限的記憶體中，使用雜湊函數可快速的建檔、插入、搜尋及更新
• 雜湊有以下四大優點：
  1. 使用雜湊法搜尋，事先不用排序
  2. 搜尋速度與資料多少無關，在沒有碰撞和溢位下，只需一起讀取即可
  3. 保密性高，不事先知道雜湊函數就無法搜尋
  4. 可做資料壓縮，可節省空間。
• bucket：雜湊表中儲存資料的位置，且每個位置被指定一個唯一的位址，稱為 bucket address
  • 雜湊法中的記憶位置被分成b個bucket，所有的資料鍵值經赫序轉換後必對應到表中的某一bucket
• slot：每一個bucket有好幾個儲存區，此儲存區便稱之為 slot，每個 slot 可以容納一個記錄
• 載入密度：雜湊空間的載入密度以α表示。α＝n/sb
  • n是識別字的使用數目，b是bucket的數目，s則是每一bucket的slot數
  • α值愈大則使用率越高，碰撞或溢位的機會也就相對較高
• 同義字：若兩個識別字 I1 與 I2 其雜湊函數值相同，則f(I1)＝f(I2)，則稱I1與I2為同義字
• 碰撞：當兩個不同識別字經過雜湊函數運算後落在相同的bucket address，則稱為碰撞
• 溢位：如果一個識別字經雜湊函數運算後，所對應的bucket已經滿了，則稱為溢位
• Hash Function 設計原則
  • 運算容易
  • 碰撞越少越好
  • 盡量將文字轉換成數字
  • 盡量充分利用所有的 bucket 位置, 不要有偏差( bias ), 極盡可能均勻分配
• 中間平方法: 轉換成數值 --> 平方此數值-->取中間三位(視需要決定位數)--> 壓縮(視需要決定倍數)
• 除法: 利用 Mod 運算將識別字 X 除以某數 M, 取其餘數當作 X 的位址( 0~ M-1 ), M 建議用質數
• 疊合法:  轉換成數值 --> 將其分成幾部分, 除最後一個外, 每部分長度相同-->將其相加起來得到 bucket addess
  • 移動摺疊
  • 邊界摺疊: 將機數位段或偶數位段反轉後相加
• 位數分析法: 取出適當位數後, 可直接對應置 bucket 或再配合其他方法
  • 靜態表: 永久性表, 所有資料已事先得知, 無刪除或修改的運算
  • 動態表; 暫時性表, 所有資料未事先得知, 且有插入, 刪除或修改的運算
• 溢位處理（Overflow handling）
  • 當識別字放入某個 bucket 時，若該 bucket 已滿了，則發生溢位
  • 任何一種雜湊函數都免不了會發生碰撞或溢位
  • 完美雜湊:  無碰撞或溢位的雜湊函數
• 線性探測（linear probing）: 是把雜湊位置視為環狀的空間，當溢位發生時，以線性的方式從一 bucket開始探測，找到一個空的儲存位址即將資料存入，若找完一個循環還沒有找到空間則表示位置已滿。
• 平方探測（quadratic probing）: 用來改善線性探測的缺失，避免相近的鍵值聚在一起。當f(X)的位址發生溢位時，下一次是探測(f(X)+i2) mod m或(f(X)-i2) mod m，其中1≦i≦(m-1)/2（注意m必須是具有4j+3型的質數（如7 or 127））
• 再雜湊: 設置一系列的雜湊函數f1,f2...fm。當f1產生溢位時，則改用f2，若f2又發生溢位時，則改用f3，....直到沒有溢位發生為止。
• 鏈結串列: 首先將所有的雜湊空間建立b個串列，起初只有b個串列首之後，若有相同位址的識別字則將其鏈結其後，成為鏈結串列，直到所有的可用空間用完為止。