【Java】認識 HashMap 前要具備的雜湊概念

https://unsplash.com/photos/a-row-of-books-sitting-on-top-of-a-shelf-6EH_ILd3S50

在 Java 程式語言，有兩種常見的資料結構，叫做「HashSet」和「HashMap」。那麼「Hash」是什麼呢？本文會用生活情境的例子來介紹雜湊資料結構。讀完後，可以前往文末附上的連結，學習 HashMap 的工作原理。

由於本文的範圍是認識 HashMap 前，至少要知道的概念，所以不會太深入地解說雜湊相關的演算法。

此篇轉載自本人的 iThome 鐵人賽文章。

一、雜湊相關概念

筆者平常會將紙本發票登錄到載具的 App，每兩個月讓它自動對獎。若有中獎，再從發票堆中找出來。那麼，對於發票該如何整理起來收好，會有一些做法。

第一種是隨便放，但這樣在尋找發票時，就得「循序搜尋」，效率低落。

第二種是按照月份歸類，例如 7 月往上方放，8 月往下方放。然而同月份的發票肯定有很多張，找發票時相當於規模小一點的循序搜尋，效率仍不太好。

第三種是根據發票號碼的最後一個數字分類。相較於第二種，此種做法能將發票分散開來（10 小堆），而且均勻分佈。

第四種是根據店家分成不同小堆，例如超商、咖啡店、速食、其他等。但相較於第三種，此種做法可能有「分佈不均」的問題。假設我只去 3 次咖啡店，當 App 提醒星巴克發票中獎，理應很快就找出發票。但若我去了很多次超商，當 7-11 發票中獎，反而尋找的花費時間較長。

前面的生活情境舉例，可以幫助我們認識雜湊的相關結構。

筆者再提供另一個例子來比喻這些結構之間的關係。

學校的一條走廊上有許多間教室；每間教室內有許多座位；每個座位上有一名學生。基於這個例子：走廊是 Hash Table；教室是 Bucket；Slot 是座位；資料是學生。

雜湊函數（hashing function）可以對一筆資料進行運算，最後得到一個整數，我們稱之為「雜湊值」（hash code）。在雜湊結構中，雜湊值會被用來決定要將資料放在哪個 bucket。

下面舉例幾種雜湊值的運算方式。前提是資料可以用某種數字來表示，或者已經轉換為數字了。

除法：將資料除以固定某個數字，取其餘數當作雜湊值。
中間平方法：將資料進行平方，固定取其中幾位數字當作雜湊值。例如有一筆資料是 829，平方後為 687241，若想取百位數和十位數當作雜湊值，則 829 的雜湊值為 24。

如果相異的資料卻被算出相同的雜湊值，我們稱發生了「碰撞」（collision）。以前面的生活情境來比喻，就像有第二張或更多張 7 月的發票，被放在同一堆。

好的雜湊函數，應該減少碰撞，讓資料盡可能均勻分佈在各個 bucket，以減少在 bucket 中搜尋資料的時間。其實「均勻」和資料結構中的「平衡樹」有異曲同工之妙，都是為了避免讓某些資料被放在很深層的位置，導致搜尋它們的時間變長。

另外，雜湊函數也建議設計成簡單的計算方式。畢竟在雜湊結構中，無論是放入還是搜尋資料，都得先從 hash table 中定位出 bucket 的位置。因此不宜設計得太過複雜，增加計算成本。