Java 有兩種常見的資料結構，叫做「HashSet」和「HashMap」。那麼「Hash」是什麼呢？本文會先用生活情境的例子來介紹雜湊資料結構，後面兩篇則進一步解說 HashMap 的工作原理。這三天的文章是一個小系列，筆者想藉由複習來加深印象。

此篇亦轉載到個人部落格。

一、雜湊相關概念

（一）生活情境舉例

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

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

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

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

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

（二）雜湊相關結構

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

• Bucket（桶）：集中存放多筆資料的地方。例如 7 月的發票都放在一堆，8 月的放另一堆。每一堆發票視為一個 bucket。
• Slot（槽）：存放一筆資料的地方，就像寫著發票資料的紙。一個 bucket 可具有一至多個 slot。
• Hash Table（雜湊表）：是 bucket 的集合，就像用來放各個發票堆的容器。

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

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

二、雜湊函數

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

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

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

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

好的雜湊函數，應該減少碰撞，讓資料均勻分佈在各個 bucket，以減少在 bucket 中搜尋資料的時間。

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

Ref：資料結構與演算法筆記 - Hashing (雜湊) 原理介紹

接下來的兩篇文章會以此為基礎，介紹 HashMap 的工作原理。

今日文章到此結束！
最後推廣一下自己的部落格，我是「新手工程師的程式教室」的作者，請多指教