# [資演] 13- Hashing

###### tags: `資演`

雜湊表（hash table）是一種用來儲存鍵（key）---值（value）對的資料結構，其中：
* 鍵（key）是用來獲取資料index的不重複整數
* 值（value）是要儲存的資料

透過雜湊函數（hash function，或簡稱hashing），我們可以得到各個key對應的雜湊值（hash value），再把這個雜湊值當作用來查找的index，以快速查詢資料。


一個簡單的例子是，當我們在通訊錄中想要查找一個人的基本資料時，可以創建一個按照聯絡人姓氏順序排列的表（即建立人名 $x$ 到姓氏 $y$ 的函數關係 $y = h(x)$）。在姓氏為「陳」的表中查找「陳怡君」的資料，顯然比直接查找「陳怡君」要快得多。在這裡，key就是人名，「取姓氏」則是雜湊函數，整個通訊錄的架構就是一個雜湊表。


你可能已經發現一個問題了：很多人都姓「陳」，該怎麼辦？用數學一點的語言說就是，有很多不同的 $x$，都對應到相同的雜湊值 $h(x)$。這種狀況稱為衝突（collision）。這種時候就需要再進行額外的處理。以實用的角度來說，一個好的hash function當然是衝突的機會越小越好。在某些應用場景上，例如密碼學的相關應用，這個hash function的選擇是很重要的。
## 名詞解釋
* 桶(Bucket)：雜湊表中儲存資料的位置，每一個位置對應唯一位址(Bucket Address)。
* 衝突(Collision)：若2筆以上的資料經過雜湊函數運算後的雜湊值相同，也就是對應到相同index時，稱為碰撞。
* 溢位(Overflow)：資料經過雜湊函數運算後，雜湊值所指向的桶位址已滿，無法再儲存，稱為溢位。

## 雜湊函數
一個好的雜湊函數 $h(x)$ 應該要有以下性質：
* 可以大大減少可能出現的key的總數，也就是說，雜湊值的數量遠少於key的數量。
* 盡可能讓key在經過雜湊函數後，能夠平均分佈到每一個雜湊值上，如此才能盡可能減少兩個key對應到相同的雜湊值（衝突）的情況。

在這邊我們介紹一種最簡單的雜湊函數：Division method。

假設雜湊表大小為 $m$，要把大範圍的key對應到較小範圍的index，最直覺的做法就是除以 $m$ 然後取餘數：
$$
h(x)=x~\text{mod}~m
$$例如，選定雜湊表大小為 $m=8$，那麼以下的key與index將有對應關係如下：
* $h(14)=14~\text{mod}~8=6$
代表「key = 14」的資料要放進「第6個」bucket。
* $h(23)=23~\text{mod}~8=7$
代表「key = 23」的資料要放進「第7個」bucket。
* $h(46)=46~\text{mod}~8=6$
代表「key = 46」的資料要放進「第6個」bucket。

## 衝突處理
衝突在「可能使用到的key」之數量遠大於雜湊表大小的情況下，無可避免。解決的辦法有下列兩種：
* [Chaining](http://alrightchiu.github.io/SecondRound/hash-tablechaining.html)：使用Linked list把「Hashing到同一個bucket」的資料串起來。
* [Open Addressing](http://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html)：使用Probing Method來尋找雜湊表中「空的bucket」存放資料。

## 雜湊表的應用
Python 的 dictionary 就是一種雜湊表的實作。這邊我們來看一個運用 dictionary 可以巧妙解決的題目。

* [Two Sum](https://leetcode.com/problems/two-sum/)
給定一個整數陣列`nums`和一個整數值`target`，在裡面找出兩個數，其加總恰等於`target`。
每個數不能被重複使用，且必剛好只有一個解。
:::spoiler 解答
相信大家看到這題都可以馬上想出暴力解，如下：

    class Solution:
        def twoSum(self, nums: list[int], target: int) -> list[int]:
            for i in range(len(nums)):
                for j in range(i):
                    if nums[i] + nums[j] == target:
                        return [i, j]

然而這個暴力解的複雜度為 $O(n^2)$，其中 $n=$`len(nums)`，並不是相當理想。

在這裡我們可以運用dictionary來解決他。我們會希望每個數只要查一次就知道結果，這樣複雜度就會是 $O(n)$。運用dictionary的思路為，當你尋訪到某個數字`nums[i]`的時候，可以把和`target - nums[i]`對應的這個index `i`存在dictionary裡面。這樣我們只要檢查其他數字`nums[j]`是不是有被包含在dictionary的key裡面，如果有，回傳`[i, j]`這對數字就可以了。

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            h = {}
            for i in range(len(nums)):
                if nums[i] in h:
                    return [i, h[nums[i]]]
                h[target - nums[i]] = i

:::