淺談「Hash」、「Hashtable」與「HashMap」
概論
本篇要討論的主題是「Hash」、「Hashtable」與「HashMap」；雖然它們都有「Hash」，但前者與後兩者是不一樣的兩件事。
更進一步的說，其實「Hash」是一種「演算法的概念」，而「Hashtable」與「HashMap」則是一種與「Hash」相關的資料結構實作。
由於筆者非本科出身，所以「演算法」與「資料結構」一直以來都是筆者相對比較不足的項目；但架不住重要啊，所以只能硬著頭皮上了，若各位發現本文有任何觀念不正確或解釋不清楚的地方，還請不吝賜教。
正文
雜湊：「Hash」
首先，我們先來介紹本文的主角：「Hash」，中譯為「雜湊」，其中文的是「切碎」、「拼湊」的意思；因此，「Hash」就是一個將東西切碎後再重新拼湊的過程。
就資料結構的來說就是：將原資料經過散列處理後，再拼湊成新的資料。
其中用來切碎資料的那把「菜刀」就是「Hash Function」，中譯為「雜湊函示」，它是一種「演法算」，常見的雜湊演算法例如「MD5」、「SHA-1」、「SHA-2」⋯等；要注意的是，關於「雜湊算法」的特性中，最重要的是它必須具備「不可逆」的特性。
最後，經過「雜湊算法」演算後所產生的值就被稱為「Hash Code」，中譯為「雜湊碼」，整體概念圖如下：
題外話，如果覺得文字不好理解的話，可以參考影片：「輕鬆搞懂資料結構: 雜湊(hash)」，說明地還滿淺顯易懂的。
雜湊的應用
關於「雜湊」的應用，筆者想補充一個重要的觀念，就是「『雜湊』與『加密』是不同的兩件事情；其最大的差異在於『雜湊』必須具有不可逆的特性。」，這與其「目的」有關。
試想，「加密」的最終目的是什麼？
答案是「傳遞資料」，不論是「對稱加密」或是「非對稱加密」的目的都是為了要保護資料，避免資料在不小心外洩時能「不被讀懂」，但其最終的目的還是要讓目標對象能「讀懂」資料，所以它必須是「可逆」的。
但「雜湊」則不需要還原資料，其常的應用如「數位簽章」、「資料完整性的驗證」、「密碼的傳輸與保存」⋯等。
「數位簽章」的目的是要驗證資料來源的正確性，就如同「防偽標籤」。
倘若我們今天要傳一份資料傳輸給遠端目標，那「目標對象」如何能知道其所接收到的資料是正確的呢？
其作法就是將要傳輸「數據資料」經過「Hash」，並將其產生的「Hash Code」作為「簽名憑證」並加密後與「數據資料」一併傳輸；而「接受者」只要將收到的「數據資料」經過同樣「Hash Function」處理，比將接收到並經過解密後的「簽名憑證」比對，就能分辨資料真偽，概念圖如下：
這樣的作法可以防止所謂的「中間人攻擊」。
試想，倘若「Hash」是可逆的，這樣當中間人拿到「簽名檔」，只要將其逆向處理，那不就可以得到原資料？
而「雜湊」用「驗證資料的完整性」的原理有些類似。
假如我們經網路傳輸獲取一「數據資料」，那我們要如何辨識該資料是否完整，是否有在傳輸過程中損毀？
其原理為「相同的數據」其經過相同的「Hash Function」運算後，其產生的「雜湊值」必為「相同」，且具有唯一性，意即「不同的數據」就算經過相同的「Hash Function」運算，也不可能產生相同的「雜湊值」。
為什麼要用雜湊值作為比對的依據？
這是因為，原則上，不論「數據資料」的大小，其經運算後的雜湊值都應為一固定長度的數值；也就是說，即使今天「數據資料」再大，但因為其經運算後的雜湊值為固定大小，所以當我們要驗證資料完整性時，僅需要比對「雜湊值」即可，能大幅減少比對成本。
密碼的傳輸與保存
在網路的世代，「密碼」經常是資安漏洞所在，事實上，我們幾乎不可能阻止密碼在網路傳遞時被竊取；即使現在的傳輸普遍都以「HTTPS」，也就是輔以「TLS」的「HTTP」協定。
因此，在一些資安規格要求比較高的系統，如金融系統；通常會將密碼先加密在進行「HTTPS」傳輸。
此外，關於密碼的規範還有一常見的原則：「密碼不落地」。
因為密碼不僅可能在「網路傳輸」時被竊取，也可能在「保存」時被盜取的，以手機登陸「行動銀行 APP」為例，密碼可能被存放於「手機」的儲存空間或是銀行端的資料庫；那麼當「手機」失竊時，是否有機會被破解呢？又或是有駭客攻破銀行系統時呢？
我們先來討論「Client」端，以會員登入為例子，在登入頁面時，應該有一個常見的功能為「自動登錄」吧？試想它密碼存於何處？
所以在「Client」端通常還是會以「加密」或「Hash」來處理，「加密」還容易理解，那為什麼「Hash」亦可以呢？
這跟「Server」端的所存放的密碼資料有關係，試想一下，當你在登入頁面選擇「忘記密碼」選項時，是不是通常有兩種處理方式，第一種方式是網站「直接」將密碼以「E-mail」的方式告知；這種情況就代表著「系統」必須儲存使用者的「密碼」。
其第二種，同樣是以「E-mail」寄送，只是內容不是直接告知密碼，而是需要我們根據信中連結自行修改密碼；在種情況下，「系統」僅須儲存使用者「密碼的 Hash 值」即可。
倘若有一天，網站系統被駭客攻破且系統資料庫外洩時；此時，如果外洩的資料只是「Hashed Text」，而非真實客戶資料，是不是就能降低其「資料外洩」所造成的損害？
實際上，即使是以「Hash Code」作為資料存放也並不是絕對的安全；當駭客竊取到「Hashed Text」後，他可以藉由「彩虹表」的方式來解譯；而其相對應的解法就是：「加鹽加密法」。
舉這個例子是想說，資安的議題可大可小，也可分為不同層級探討，至於資安等級要到何種程度，這端看網站設計的需求，不必無限上綱，造成不必要的效能損耗。
編碼的概念
既然都講到這邊了，就額外再補充個「編碼」的觀念吧。
事實上，「編碼」跟「加密」很類似，都是數據格式轉換的一個過程，更正確的說，「加密」也是一「編碼」過程，只是「編碼」的目的是為了保護資料。
但編碼的目的可能是為了任何需求，例如「Base 64」，其目的是為了「讓二進位資料能夠以 64 個基本字元來表示」，常用於資料的傳輸與保存，但因為其編譯的方式是公開的，因此不具任何加密功能；所以「Base 64」是一種「編碼」機制，而非是一種「加密」機制。
雜湊表：「Hash Table」
其實關於「Hash」的應用，還有一項是目前尚未提到的，就是用於「資料結構」的演算上，這我們稍候再繼續介紹，但在此之前，我們先來一種資料結構的概念：「Hash Table」。
簡單的說，「Hash Table」其實就只是一種以「Hash」概念方式實作「映射機制（Key-Value）」的資料結構，更直白的說，就是一種以「Key-Vaule」機制存放資料的結構容器。
其作法是這樣的，首先我們會先將資料的「Key」經過「Hash Function」運算，並將運算後產生的「Hashed Text」作為索引，並將資料「Value」放入與「索引」連結的「Buckets」內，示意圖如下：
而上述機制中，存放對應資訊的表格，就稱為「映射表」。
因此，在該機制下，倘若我們在要獲取「Value」時，我們只要根據「映射表」就能夠輕易地根據「Hashed Key」找到相對應「Value」，因為是查表法，所以在理想的情況下，它的查找效率極佳，其擁有「O(1)」的時間複雜度。
但所謂的理想狀態是指未出現「雜湊碰撞」的情況下，所謂的雜湊衝突是指兩個不同的「Key」經「Hash Function」運算後產生相同的「Hash」值，如下：
當出現「雜湊碰撞」時，「Hash Table」的效能就可能會受到影響，若是衝突項目是以「均勻分佈」的情況散佈仍符合預期，但倘若「分佈不均」，甚至是出現極端「大象腳」的情況時，其效能就會顯著下降。
備註：「大象腳」即大多數的「Key」值經過運算後都產生相同的「雜湊值」，並導致多數的資料都存於同一個「桶子」中。
根據上述內容，我們不難推測，實際上影響「Hash Table」效能優劣的最主要因素是「Hash Function」。
雖然筆者在先前曾說過，在「Hash Code」必須是唯一值；但若「雜湊演算法」本身過於複雜，也容易使得在建立「Table」時的損耗過高，所以當我們在設計雜湊函示時，使用情境與需求也是相當重要的考量因素，例如在「資料容器」的「雜湊算法」設計時，假如我們的最終目的是要讓資料查找變得容易，也許我們只要讓資料經「Hash」再分配後，能夠被「均勻散佈」即可，並不一定需要做到「唯一」，此時，當我們在設計該算法時，就可以設計的相對簡單一些，只要能符合需求的即可，畢竟，「唯一」本身就是一種成本。
但在多數情況下，我們還是會期望「Hash」的結果會是唯一值，尤其當我們將其作為「數位簽章」用時，或者是用於「驗證資料的完整性」時。
雜湊碰撞的處理
講一個比較不相干的話題：「雜湊碰撞」的處理方式。
若當「雜湊碰撞」出現時，最常見的處理方式是「鏈結串列」，即發生碰撞時，新的元素串接在既有元素之後；這是屬於「Closed Addressing」的實作方式之一。
而「Closed Addressing」又稱為「Separate Chaining」，與之相異的是「Open Addressing」，其常見的實作方式有「Linear Probing」、「Quadratic Probing」以及「Double Hashing」，至於原理跟實作細節，讀者們可以自行點連結閱讀，在此就不多說了。
關於「開放尋址」與「閉鎖尋址」的差異可以參考「Meaning of Open hashing and Closed hashing」。
若覺得太複雜，不太明白也沒關係，總之，我們只需要知道 ：「『Hash Table』是一種『Key-Value』的資料結構即可」。
「Java」中的「Hashtable」類
就如同先前所介紹，「Hash Table」僅是一種資料結構的「概念」。
由於「Key-Value」是一種常見，且相當實用的資料結構，因此幾乎在各程式語言中都有實作，而其在「Java」中的實作就是「Hashtable」類；官方文件對其介紹如下：
事實上，「Hashtable」類相當古老，從「JDK 1.0」開始就存在；在當時，連「Java Collections Framework」的概念都還未曾出現，「數據結構」還是由一群功能類別所負責，其中的「Dictionary」類就是屬於「Key-Value」的資料結構，而「Hashtable」就是繼承「Dictionary」的具體實現類。
直到「JDK 2.0」時，「Java」提出「Java Collections Framework」的概念與規範，而「Hashtable」被重構，實作「Map」介面，並被歸類於之中。
而「Hashtable」最大的特性就是它是「Synchronized」，它支持「執行序安全」，並且「Key」與「Value」皆不允許為「null」。
最後，事實上，「Hashtable」是一個不建議使用的類別，就如官方文件上所敘述，在「JDK 5.0」之後，若有「執行序安全」且屬於「Key-Value」資料結構的需求，建議以「ConcurrentHashMap」取代之。
「ConcurrentHashMap」類
「ConcurrentHashMap」的官方介紹如下：
作為「Hashtable」的替代品，它的功能規範幾乎與「Hashtable」一致，我們可將之視為「Hashtable」的優化類別，並且同樣是屬於「Java Collections Framework」的成員。
「HashMap」類
最後是「HashMap」類，它是「Java」中，屬於「Key-Value」類型的資料結構中最常被使用的容器，沒有之一，官方介紹如下：
事實上，它與「Hashtable」類似，並常被與之比較，如討論串：「What are the differences between a HashMap and a Hashtable in Java?」。
簡單地說，「HashMap」類不支持「執行序安全」，因此它具備更好的執行效率，同時也可以接受「null」值作為「Key」或「Value」。
題外話，「HashMap」在「JDK 1.7」與「JDK 1.8」的實現原理略有不同，不過這會牽扯很多演算法的細節，考慮篇幅不足，筆者也相對不熟悉，故就不在此細談了。
「Collection」與「Map」的比較
因為筆者曾聽人說過：「Map」是「Collection」的一種。
錯，雖然「Map」與「Collection」同屬於「Java Collections Framework」的成員之一，但它們之間並沒有繼承關係，請參考討論串：「What is the difference between a Collection and a Map?」的最佳回答，如下：
另外，可以參考「Java集合框架」中繼承樹圖，首先是「Collection」的繼承樹圖，如下：
由上圖可知，繼承「Collection」的介面有「Set」、「List」和「Queue」，但並沒有「Map」，而「Map」的繼承樹圖，如下：
總結
簡單整理一下，首先是「Hash」，它就是將數據資料經過「雜湊運算」並產生「雜湊碼」的過程。
然後是「Hash Table」，它其實就只是一種以「Hash」概念方式實作「映射機制（Key-Value）」的資料結構，而「Hashtable」類與「HashMap」類是「Hash Table」在「Java」中的實現類，且同為「Java Collections Framework」的一員，其最大的差別在於「Hashtable」類支持「執行緒安全」，「HashMap」類則無。
另外，「ConcurrentHashMap」是「Hash Table」的優化類，並建議以之作為替代。
