# [資料結構] CH20. Hash Functions

## 何謂Hash

* Hash是用於加速，十分常用的一種技巧；需要依照情況有不同的使用方法，需要一定的經驗才能運用自如，而不是反而讓你的程式crash。
* Hash table是一種mapping的技術，將多餘的空間壓掉。
* 舉個例子：你可能開了一個很大的陣列，但只用了裡面少少的空間，導致你每次搜尋時都遍歷了空的元素；我們何不將有資料的部分mapping到另一個較小的空間呢？
* 你可能還不太清楚上面這個例子為何會發生，我們幹嘛不一開始就開小的陣列就好了？我舉個更實際的例子如何：
* 給予你`10`個`1~10000`的數字，然後請列出每個有出現過的數字各出現幾次。
* 然後你開了`10000`空間的陣列，最多只用了`10`格。顯然這不是個好作法。
* 看完上面的範例，我們回來Hash的部分。如果我們有一個Hash Function，可以將資料映射到新的空間`Hash table`(或是說從新空間映射回來)，那就可以解決我們的問題了。
* 這個Function應該有以下特性：
* 低成本(Low cost)：我們用Hash就是為了加速，總不會做了Hash結果浪費更多時間吧。
* 決定性(Determinism)：它應該要正確的映射到某個地方，且資料不該有衝突發生。
* 均衡性(Uniformity)：Hash table應該要越小越好，不應該像原始陣列一樣有太多的空元素，就算有也不應該太集中在陣列的某個地方(如果前面都是空的，你一開始的範圍就設的不夠好)。

## Representative Hash Functions

* 以下介紹幾個常見的Hash Function，當然要依照情況(資料與限制)使用。

### Division Method

h(x) = x mod M

* 超級簡單的Hash方法，直接將資料對`M`取餘數當作新的空間索引。
* 當你確定資料有一定的分散性時，就可以用這招。

- 如果`M`是偶數，會出現以下特性：
- `x`和`h(x)`會同樣是奇數或同樣是偶數。
- 如果原始資料奇數偶數比例有很大的差距時，必須注意這點，否則均衡性會很差。
- 通常`M`會使用質數來避免這個問題，這也可以讓Hash的均衡性提升。

### Multiplication Method

h(x) = ⌊m(xA mod 1)⌋

* `A`為0~1之間的浮點數。
* 根據資料，`A`會決定這個Hash Function的好壞程度。
* 美國科學家**Knuth**統計(還是假設，我不知道)`A`為$\frac{\sqrt{5}-1}{2} = 0.618033$時的普遍效果最好。

### Mid-Square Method

h(x) = s

Which s is select from x^2

* 這個是我認為蠻有趣的hash function，舉個例子就很好理解運作方式了。
* 今天對`1234`和`5642`做`Mid-Square Method`：
* 先將數字平方得到`1522756`和`31832164`。
* 然後我們直接取三、四位數當作新的索引：`h(1234) = 27`、`h(5642) = 21`。
* 當然你可以根據資料大小，做不同的運算處理。

### Folding Method

Divide number to multiple parts
h(x) = s
Which s is select from the sum

* 一樣舉個例子：
* 對`5678`和`321`做`Folding Method`：
* 我們將前者拆成`56`和`78`；後者拆成`3`和`21`。
* 各自相加得到`134`和`24`，然後我們就將`34`(只取最低位元)和`24`當作新索引。
* 一樣可以按照資料和需求去改變細節。

## Hash的問題

* Hash看似是很單純的數學轉換式，但是我們必須考慮到資料不能映射在同一個hash table，否則資料就會被蓋掉，造成程式錯誤。
* 因此如何正確的選擇hash function就是很重要的問題了，所以我最開始才提到這需要一定的經驗(你失敗過才懂得如何避免XD)。
* 本人自己還沒有用過太多的hash，就算使用都是直接用STL內建的map去完成。

## 實際應用例子

* 剛好前陣子有人在問ZeroJudge的題目，裡面我有使用到Hash，拿出來分享一下：[a562: ITSA201112 P2 小白鼠走方格](https://zerojudge.tw/ShowProblem?problemid=a562)
* 我的解法是使用`DFS`硬爆所有可能路線，然後我使用了Hash Table去紀錄哪些數字是我走過的。
* 首先，題目說明提到地圖最大是`8*8`，也就是說即便地圖最大、所有數字都不同，最多也只有`64`種數字。
* 因此我將原地圖轉換成`0~63`的數字，然後就可以直接用一個`bool[64]`去檢查。

---

## 結語

* 本筆記就到這邊結束了，真的很感謝你可以全部閱讀完，如果有幫到忙就太好了。以下是一些碎念。
* 中間停了半年的時間才將最後的部分補完，主要是因為不在我自己的考試範圍，且我自己實際使用到的次數其實不太多。
* 自己還蠻喜歡打這些筆記類的文章，能夠將自己的想法轉換成文章真的對理解和記憶很有幫助；不過有點三分鐘熱度，能夠補完其實我自己也蠻訝異的XD
* 事隔半年回去看了前面某些部分，其實寫得不太好，不過也懶得改了(主要是畫圖語法都忘得差不多了)。如果有機會可能會把*Prim,Kruskal,Dijkstra,Bellman-Ford*整理成一份吧，後來都一直還有人詢問。
* 有想過要不要做**演算法筆記**，不過看人家師範的如此強大就算了。
* [我的網頁](https://zero871015.github.io/)裡面還有一些其他的文章，如果有興趣也可以去看看。

###### 最後，期許你我都可以在資工路上發光發亮。

###### tags: `DS` `note`