技術文章 » 資料結構與演演算法 | 雜湊表（Hash Table）

資料結構與演演算法 | 雜湊表（Hash Table）

2023-11-02 18:01:25

雜湊表（Hash Table）

在二分搜尋中提到了在有序集合中查詢某個特定元素的時候，通過折半的方式進行搜尋是一種很高效的演演算法。那能否根據特徵直接定位元素，而非折半去查詢？雜湊表（Hash Table），也稱為雜湊表，就是一種資料結構，用於實現鍵-值對的對映關係。它通過將鍵對映到特定的值（雜湊值）來實現快速的資料檢索。

	// Java 中Hash表JDK中有提供兩種結構Hashtable、HashMap，使用介面上區別不大
	// Hashtable 是Dictionary類的子類，而 HashMap 是AbstractMap類的子類。
	// 由於 Dictionary類已經被廢棄，因此Hashtable也不再推薦使用。
	// 在工程應用上值得注意的是 Hashtable是執行緒安全的，而HashMap不是

    public HashMap<Integer,Long> records1 = new HashMap<>();
    public Hashtable<Integer,Long> records2 = new Hashtable<>();

一般而言，雜湊表基於雜湊函數將鍵轉換為雜湊碼，然後使用這個雜湊碼作為索引獲取相應的元素。雜湊表的優點是具有快速的平均查詢時間，通常為O(1)。然而，它也具有一些挑戰，如處理雜湊衝突、設計良好的雜湊函數和維護適當的裝載因子。裝載因子表示雜湊表已用空間與總空間的比例，需要適時進行動態調整以保持雜湊表的效能。

	// 範例java中初始化 HashMap的容量以及裝載因子。
	Map<Integer,Integer> sumMap = new HashMap<>(2000,0.75f);

雜湊表在電腦科學中有廣泛的應用，包括實現關聯陣列、資料庫索引、快取、程式語言中的字典和集合等等。

基本概念

雜湊函數（Hash Function）： 雜湊表使用雜湊函數來將鍵轉換為整數，通常是陣列的索引。雜湊函數應該是確定性的，即對於相同的鍵，它應該生成相同的雜湊碼。理想情況下，不同的鍵應該對映到不同的雜湊碼，但由於雜湊函數的有限性，可能會出現雜湊衝突。

雜湊衝突（Hash Collision）： 當兩個不同的鍵對映到相同的雜湊碼時，發生雜湊衝突。雜湊表需要處理雜湊衝突，以確保不同的鍵可以正確儲存和檢索。

儲存結構： 雜湊表通常由一個陣列和一個雜湊函陣列成。陣列的每個元素稱為桶（Bucket），它可以儲存一個或多個鍵-值對。

PS：Java 中由於都已經封裝好了 HashMap，一般使用可能感知不到這些概念，但要熟練掌握還是需要理解這些基本理念。

基本操作

插入（Insertion）： 將鍵-值對插入雜湊表時，首先通過雜湊函數計算鍵的雜湊碼，然後確定儲存位置（桶）。如果存在雜湊衝突，通常會使用連結串列、陣列或其他資料結構來解決衝突，並將鍵-值對新增到儲存位置。

查詢（Lookup）： 查詢鍵對應的值時，使用相同的雜湊函數計算雜湊碼，並在儲存位置中查詢該鍵。如果存在雜湊衝突，必須在衝突的元素中搜尋以找到正確的鍵-值對。

刪除（Deletion）： 刪除鍵-值對時，使用相同的雜湊函數計算雜湊碼，然後從儲存位置中刪除對應的鍵-值對。

基本應用

Leetcode 383 贖金信【簡單】

給你兩個字串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 裡面的字元構成。
如果可以，返回 true ；否則返回 false 。

字元可以轉換成ASCII數位，陣列的下標也是數位。那麼利用這種數位對映作為雜湊函數，就能夠通過字元直接讀取陣列儲存的資訊。通過ASCII陣列 來記錄 magazine 裡面包含的各個字元數量，再遍歷 ransomNote 使用到的字元判斷是否存在於 ASCII陣列，並減少數量來標識已經使用過。

借這題不妨講一講分塊的編碼風格。在日常生活中，我們一定有記憶手機號碼的經歷，一個長長的數位串（比如1234567890）可能很難記憶，但如果將其分成更小的組塊，例如(123) 456-7890，就更容易記憶和處理。這個其實在認識心理學裡面概念叫："資訊分塊"（chunking），指的是將大量的資訊分割成更小的、有意義的單元，以便更容易處理和記憶。關鍵點是人類大腦通過將資訊分成較小的組塊，可以更有效地處理和記憶資訊。

所謂程式碼可讀性其實就是對程式碼的認識，將資訊認識心理學的分塊理論應用到程式碼可讀性就是提倡的 分塊編碼。可以將冗餘的程式碼分成一塊一塊的邏輯，塊與塊之間用空行來進行視覺上的分塊，方便小段小段的去理解程式碼邏輯；每一塊程式碼可以適當的加上註釋以方便閱讀。當然這些都是形式上的，更重要的是每一塊程式碼邏輯都會聚焦一個目標，這樣寫法也有利於編碼者自身對邏輯的梳理以及減少bug。

不妨練習下類似問題，參考程式碼就不附上了，相信一定能夠完成。

Leetcode 242. 有效的字母異位詞【簡單】

給定兩個字串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。
注意：若 s 和 t 中每個字元出現的次數都相同，則稱 s 和 t 互為字母異位詞。

更多應用

Leetcode 560. 和為 K 的子陣列【中等】

給你一個整數陣列 nums 和一個整數 k ，請你統計並返回 該陣列中和為 k 的子陣列的個數 。
子陣列是陣列中元素的連續非空序列。

Leetcode 3 無重複字元的最長子串【中等】

給定一個字串 s ，請你找出其中不含有重複字元的 最長子串 的長度。