# Hash

## 何謂Hash

* Hash是用於加速，十分常用的一種技巧；需要依照情況有不同的使用方法，需要一定的經驗才能運用自如，而不是反而讓你的程式crash。
:::danger
* Hash table是一種mapping的技術，將多餘的空間壓掉。
:::

* 舉個例子：你可能開了一個很大的陣列，但只用了裡面少少的空間，導致你每次搜尋時都遍歷了空的元素；我們何不將有資料的部分mapping到另一個較小的空間呢？
* 你可能還不太清楚上面這個例子為何會發生，我們幹嘛不一開始就開小的陣列就好了？我舉個更實際的例子如何：
* 給予你`10`個`1~10000`的數字，然後請列出每個有出現過的數字各出現幾次。
* 然後你開了`10000`空間的陣列，最多只用了`10`格。顯然這不是個好作法。
* 看完上面的範例，我們回來Hash的部分。如果我們有一個Hash Function，可以將資料映射到新的空間`Hash table`(或是說從新空間映射回來)，那就可以解決我們的問題了。
:::success
* 這個Function應該有以下特性：
:::

:::warning
* 低成本(Low cost)：我們用Hash就是為了加速，總不會做了Hash結果浪費更多時間吧。
* 決定性(Determinism)：它應該要正確的映射到某個地方，且資料不該有衝突發生。
* 均衡性(Uniformity)：Hash table應該要越小越好，不應該像原始陣列一樣有太多的空元素，就算有也不應該太集中在陣列的某個地方(如果前面都是空的，你一開始的範圍就設的不夠好)。
:::

## Representative Hash Functions
:::danger

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

### Division Method
:::

h(x) = x mod M

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

- 如果`M`是偶數，會出現以下特性：
- `x`和`h(x)`會同樣是奇數或同樣是偶數。
- 如果原始資料奇數偶數比例有很大的差距時，必須注意這點，否則均衡性會很差。
- 通常`M`會使用質數來避免這個問題，這也可以讓Hash的均衡性提升。
- • (1) Division: `h(k)=k%D`
- • 則結果為0 ~ D-1 通常我們可以把`D`設為櫃子數目
:::info
### Multiplication Method
:::
:::warning
h(x) = `⌊m(xA mod 1)⌋`
:::

* `A`為0~1之間的浮點數。
* 根據資料，`A`會決定這個Hash Function的好壞程度。
:::danger

* 美國科學家**Knuth**統計(還是假設，我不知道)`A`為$\frac{\sqrt{5}-1}{2} = 0.618033$時的普遍效果最好。
:::
:::info
### Mid-Square Method
:::
:::warning

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`。
* 當然你可以根據資料大小，做不同的運算處理。
:::info
### Folding Method
:::
:::warning
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的Overflow處理 (Collision)
### Open Addressing (rehashing)

::: danger
- Linear probing：`(h(k) + i)%b`
- 缺點：形成primary clustering，具有相同hash address的資料容易聚集在鄰近的Bucket中，造成search time增加
- Quadratic probing：`(h(k) + i^2)%b and (h(k) − i^2)%b. `
- 缺點：hash table 不保證充分利用，會有secondary clustering problem, 探測順序皆相同, 增加search time
- Double hashing:`h(k,i) = ( h1(k) + i*h2(k) ) mod m`
- 時間花費多
:::

This method generally produces excellent results, but h2(k) must be relatively prime to m. One way is to make m a power of 2 and design h2(k) to produce only odd numbers

### Chaining
a bucket is a pointer to a list of keys having same home bucket
- 

## 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]`去檢查。