Java 【數據結構】哈希（Hash超詳解）HashSetHashMap【神裝】

?登神長階

第十神裝 HashSet

第十一神裝? HashMap

👔一.哈希

🧥1.概念

🩳2.Object類的hashCode()方法:

👚3.String類的哈希碼:

👠4.注意事項:

🎷二.哈希桶

🪗1.哈希桶原理

🎸2.哈希桶的實現細節

🪘3.總結

📲三.解決哈希沖突的常用方法*

💰四.HashSet

🪙1.定義

💵2.操作

💶3.特性

💷4.內部實現

💳5.應用場景

??五.HashMap

??1.定義

🖋?2.操作

🖊?3.特性

🖍?4.內部實現

🖌?5.應用場景

📝六.對比

?💼七.總結與反思

👔一.哈希

🧥1.概念

????????在Java中，哈希（Hash）是一個廣泛應用于數據結構和算法中的概念，主要用于快速查找、存儲和比較數據。哈希的核心在于哈希函數（Hash Function），它將輸入（通常稱為鍵，key）映射到一個固定范圍的輸出值，這個輸出值稱為哈希值（Hash Value）或哈希碼（HashCode）。哈希的目的在于將原本復雜、不規則的數據轉化為簡潔的、固定長度的值，使得數據的存儲和檢索更加高效。

🩳2.Object類的hashCode()方法:

Java中的每個對象都繼承自Object類，而Object類有一個hashCode()方法，這個方法被設計用來返回對象的哈希碼。默認的hashCode()實現通常基于對象的內存地址，但子類通常會重寫此方法，以便根據對象的實際內容生成更有意義的哈希值，這對于使用對象作為鍵的哈希表操作尤為重要。

作用：
- hashCode()方法返回對象的哈希碼值（哈希碼），是一個int類型的整數。
- 哈希碼是根據對象的內存地址或者根據對象的內容計算得到的一個唯一標識符。
- 在Java中，hashCode()方法通常與equals()方法一起使用，用于判斷兩個對象是否相等。
默認實現：
- 在Object類中，hashCode()方法的默認實現是根據對象的內存地址計算得到的哈希碼。
- 換句話說，如果兩個對象在內存中的地址不同，那么它們的哈希碼也會不同。
重寫規則：
- 在自定義類中，通常需要重寫hashCode()方法，以便根據對象的內容來生成哈希碼，而不是依賴于默認的內存地址。
- 如果重寫了equals()方法，就應該同時重寫hashCode()方法，保證相等的對象擁有相等的哈希碼。
- 重寫hashCode()方法時，應該遵循以下規則：
  1. 相等的對象必須具有相等的哈希碼。
  2. 不相等的對象盡量產生不同的哈希碼，以減少哈希沖突的發生。
使用場景：
- 在集合類中，如HashMap、HashSet等，hashCode()方法被用于確定對象在集合中的存儲位置，加快數據的查找速度。
- 當我們需要比較自定義類的對象是否相等時，通常會重寫equals()和hashCode()方法。

????????總之，Object類的hashCode()方法是用于獲取對象的哈希碼的方法，可以通過重寫該方法來根據對象的內容生成哈希碼，以便在集合中進行快速查找和比較。

👚3.String類的哈希碼:

String類是一個典型重寫了hashCode()方法的類，它根據字符串的內容計算哈希值，這意味著內容相同的字符串將擁有相同的哈希值，這有助于在哈希表中快速定位和比較字符串。

👠4.注意事項:

哈希函數應該是高效的，即計算速度快。
哈希函數應該盡量均勻分布，以減少哈希沖突。
哈希值雖然可以用于快速比較，但不保證絕對唯一，因此在判斷對象相等時，除了比較哈希值外，還需要比較對象的實際內容（通過equals()方法）。
在實現自定義類的hashCode()時，應當遵守與equals()方法的一致性原則，即如果兩個對象通過equals()判斷為相等，它們的哈希碼也必須相等。反之，哈希碼相等的對象不一定通過equals()判斷相等。

🎷二.哈希桶

????????哈希桶（Hash Bucket）是哈希表（Hash Table）中用于解決哈希沖突的一種常用方法，它是哈希表數據結構的一個重要組成部分。哈希桶是哈希表中存儲元素的地方，通常是一個數組。每個桶都有一個索引，通過哈希函數計算得到的哈希值會決定元素被放置在哪個桶中。

🪗1.哈希桶原理

????????哈希桶解決哈希沖突的方法是，將哈希表的每個槽（或索引）擴展為一個“桶”（Bucket），這個桶本質上是一個數據結構（通常是鏈表、數組或其他容器），可以存儲多個具有相同哈希值的元素。具體來說，當一個鍵通過哈希函數計算得到的索引已經有其他元素時，新的元素會被添加到這個索引對應的桶中，而不是覆蓋原有的元素。

🎸2.哈希桶的實現細節

哈希函數：用于將鍵轉換成索引。好的哈希函數能夠盡量均勻地分布元素，減少沖突。
桶的實現：常用的桶實現是鏈表，因為鏈表插入和刪除操作的時間復雜度較低。但在Java 8以后的HashMap中，當桶中的元素數量達到一定閾值時，會將鏈表轉換為紅黑樹，以進一步優化查詢性能。
負載因子：表示哈希表中已填入元素的數量與哈希表長度的比例，用于衡量哈希表的填充程度。當負載因子超過某個預設值時，哈希表會進行擴容，重新調整大小，以減少沖突，保持高效性能。
擴容：擴容通常涉及創建一個新的、更大容量的哈希表，并將原哈希表中的所有元素重新哈希到新表中。這個過程可以確保桶的平均長度減少，從而減少沖突。
沖突處理：當多個鍵映射到同一索引時，桶中的鏈表（或紅黑樹）結構用于存儲這些沖突的鍵值對，并通過遍歷鏈表（或樹）來查找具體的元素。

🎹源代碼模擬實現

// key-value 模型
public class HashBucket {private static class Node {private int key;private int value;Node next;public Node(int key, int value) {this.key = key;this.value = value;}}private Node[] array;private int size;   // 當前的數據個數private static final double LOAD_FACTOR = 0.75;private static final int DEFAULT_SIZE = 8;//默認桶的大小public int put(int key, int value) {int index = key % array.length;Node cur = array[index];//遍歷當前列表，看是否存在當前值while (cur != null) {if (cur.key == key) {cur.value = value;}cur = cur.next;}//若無當前值，則進行頭插法Node node = new Node(key, value);node.next = array[index];array[index] = node;size++;//判斷是否超載if (loadFactor()>=LOAD_FACTOR){//擴容resize();}return 0;}private void resize() {Node[] newArr=new Node[array.length*2];for (int i = 0; i < array.length; i++) {Node cur=array[i];while(cur!=null){//遍歷鏈表，將數據儲存到新數組int newIndex=cur.key% newArr.length;Node curN=cur.next;cur.next=newArr[newIndex];newArr[newIndex]=cur;cur=curN;}}array=newArr;}private double loadFactor() {return size * 1.0 / array.length;}public HashBucket() {array=new Node[10];}public int get(int key) {int index=key%array.length;Node cur=array[index];while(cur!=null){if (cur.key==key){return cur.value;}cur=cur.next;}return -1;}
}

🪘3.總結

????????哈希桶機制通過將沖突的元素組織在一起，而非直接覆蓋，保證了哈希表的靈活性和高效性。它允許哈希表在面對大量數據時仍能保持較好的性能，尤其是在沖突較多的情況下。通過調整哈希函數、負載因子和適時的擴容，可以進一步優化哈希表的效率。在Java中，HashMap和HashSet就是使用哈希桶來實現的，它們是Java集合框架中非常重要的組件。

📲三.解決哈希沖突的常用方法*

????????解決哈希沖突是哈希表設計中的關鍵環節，目的是確保即使兩個或多個鍵通過哈希函數計算出相同的索引，也能高效地存儲和檢索這些鍵值對。以下是幾種常用的解決哈希沖突的方法：

1. 開放定址法（Open Addressing）

線性探測法（Linear Probing）：當發生沖突時，從沖突位置開始，沿著數組線性地檢查下一個位置，直到找到一個空位。這種方法簡單，但容易造成“聚集”現象，影響查找效率。
二次探測法（Quadratic Probing）：在沖突發生后，按照某種探測序列（通常是二次的，如i^2 + c）尋找下一個空位，這可以減少聚集現象。
雙重散列法（Double Hashing）：使用第二個哈希函數來計算步長，當發生沖突時，按步長跳躍尋找下一個可用位置，以減少探測的順序性。

2. 再哈希法（Rehashing）

當第一個哈希函數導致沖突時，使用第二個、第三個不同的多個哈希函數繼續嘗試尋找空閑位置。這種方法減少了沖突的機會，但增加了計算開銷。

再哈希法通過使用一系列哈希函數不斷嘗試新的位置，而雙重散列法則通過一個固定的步長規則在哈希表中進行探測。

3. 鏈地址法（Separate Chaining）

每個哈希表的索引位置對應一個鏈表或其它動態數據結構（如紅黑樹，Java 8中HashMap的實現）。當發生沖突時，將新的元素添加到該索引位置的鏈表中。這種方法簡單且靈活，但鏈表過長時會降低查找效率。

4. 建立公共溢出區（Overflow Area）

這種方法將哈希表分為兩個部分：基本表和溢出表。當基本表中的位置已滿時，沖突的元素被放置在溢出表中。這種方式實現簡單，但效率不如鏈地址法。

5. 開散列法（Open Hashing）*

這是一種特殊的鏈地址法，哈希表本身是一個指針數組，每個元素指向一個鏈表的頭節點。這種方法強調了鏈表的獨立性，便于管理和擴展。

負載因子調整

????????無論采取哪種沖突解決策略，維護一個合理的負載因子（已用單元數與總單元數的比例）至關重要。當負載因子超過某個閾值時，通常會觸發哈希表的擴容操作，通過增大哈希表的大小并重新分配所有元素來減少沖突，保持高效的查找性能。

????????每種方法都有其優勢和劣勢，實際應用時需根據具體需求和數據特點選擇最適合的沖突解決策略。例如，對于內存充足的場景，鏈地址法因其實現簡單且效果穩定而常用；而在內存受限或查找性能要求極高的場景下，開放定址法或再哈希法可能更為合適。

💰四.HashSet

此部分建議，對照上一篇來學習????????Java 【數據結構】 TreeSet&TreeMap（二叉搜索樹詳解）【神裝】

🪙1.定義

????????Java中的HashSet是一個實現了Set接口的集合類，它提供了一種存儲不可重復元素的高效數據結構。HashSet的實現基于HashMap，這意味著它內部使用了哈希表來管理元素，這使得HashSet能夠提供快速的插入、刪除和查找操作。以下是關于HashSet的一些關鍵特性和內部工作原理的詳細說明：

💵2.操作

方法	解釋
boolean add(E e)	添加元素，但重復元素不會被添加成功
void clear()	清空集合
boolean contains(Object o)	判斷 o 是否在集合中
Iterator<E> iterator()	返回迭代器
boolean remove(Object o)	刪除集合中的 o
int size()	返回set中元素的個數
boolean isEmpty()	檢測set是否為空，空返回true，否則返回false
Object[] toArray()	將set中的元素轉換為數組返回
boolean containsAll(Collection<?> c)	集合c中的元素是否在set中全部存在，是返回true，否則返回 false
boolean addAll(Collection<? extends E> c)	將集合c中的元素添加到set中，可以達到去重的效果

源代碼?

import java.util.HashSet;public class HashSetExample {public static void main(String[] args) {// 創建一個HashSet實例HashSet<String> myHashSet = new HashSet<>();// 添加元素myHashSet.add("Apple");myHashSet.add("Banana");myHashSet.add("Cherry");System.out.println("HashSet after adding elements: " + myHashSet);// 檢查元素是否存在boolean isPresent = myHashSet.contains("Banana");System.out.println("Is 'Banana' in the HashSet? " + isPresent);// 嘗試添加重復元素myHashSet.add("Apple");System.out.println("HashSet after trying to add duplicate 'Apple': " + myHashSet);// 刪除元素boolean isRemoved = myHashSet.remove("Banana");System.out.println("Is 'Banana' removed? " + isRemoved);System.out.println("HashSet after removing 'Banana': " + myHashSet);// 遍歷HashSetSystem.out.println("Iterating over HashSet:");for (String fruit : myHashSet) {System.out.println(fruit);}// 清空HashSetmyHashSet.clear();System.out.println("HashSet after clearing: " + myHashSet);}
}

💶3.特性

無序性：HashSet不保證元素的插入順序，每次遍歷HashSet時，元素的順序可能不同。這是因為HashSet在內部使用哈希表，元素的存儲位置由其哈希值決定。
不允許重復：HashSet中不能包含重復的元素。這是通過比較元素的哈希值以及equals()方法來實現的。如果兩個元素的哈希值相同，并且通過equals()方法比較也認為是相等的，則視為重復元素，后者將不會被加入集合中。
允許null值：HashSet允許存儲一個null元素，因為HashMap允許一個鍵為null。
非線程安全：HashSet不是線程安全的。如果多個線程同時訪問一個HashSet，且至少有一個線程修改了HashSet，則必須通過外部同步來保證線程安全。

💷4.內部實現

基于HashMap：HashSet實際上是一個包裝器，它將每個元素作為HashMap的鍵，并且所有元素共享一個靜態的、唯一的值對象作為映射的值。這意味著HashSet中元素的添加、刪除等操作實際上是在操作底層的HashMap。
哈希值與索引：當向HashSet添加元素時，首先調用該元素的hashCode()方法計算哈希值，然后使用哈希值來確定元素在底層數組中的索引位置。如果該位置已有元素（哈希沖突），則使用鏈地址法（在JDK 7及以前是單向鏈表，在JDK 8中引入了紅黑樹，當鏈表長度超過8時會轉換為紅黑樹）來存儲多個具有相同索引的元素。
擴容機制：當HashSet中的元素數量超過其當前容量乘以負載因子時，HashSet會自動進行擴容，以減少哈希沖突并保持高效的查找性能。擴容包括創建一個新的更大的數組，并將原數組中的所有元素重新哈希到新數組中。

重寫equals()與hashCode()：為了確保HashSet能正確識別重復元素，存儲在HashSet中的自定義對象必須正確重寫equals()和hashCode()方法，保證相等的對象具有相同的哈希值，并且通過equals()方法判斷也為相等。

💳5.應用場景

Java中的HashSet是一個高效無序且不允許重復元素的集合類，基于HashMap實現。

它的核心應用場景包括數據去重、集合運算、緩存實現、快速查找成員、統計唯一元素、輔助高級數據結構及游戲開發中的對象管理等。
HashSet利用哈希機制提供快速的插入、刪除和查找功能，特別適合需要高效率集合操作的場景。

????????HashSet是Java集合框架中一個非常實用的類，特別適用于需要快速插入、刪除和查找，且不需要維護元素插入順序的場景。理解其基于HashMap的實現以及如何利用哈希機制來管理元素，對于高效使用HashSet至關重要。

??五.HashMap

?此部分建議，對照上一篇來學習????????Java 【數據結構】 TreeSet&TreeMap（二叉搜索樹詳解）【神裝】

??1.定義

Java中的HashMap是一個實現Map接口的類，它提供了一個存儲鍵值對（key-value pairs）的數據結構。HashMap允許使用唯一的鍵來映射到特定的值，并且能夠高效地進行插入、刪除和查找操作。鍵值對之間沒有特定的順序，HashMap也不是線程安全的。

🖋?2.操作

方法	解釋
V get(Object key)	返回 key 對應的 value
V getOrDefault(Object key, V defaultValue)	返回 key 對應的 value，key 不存在，返回默認值
V put(K key, V value)	設置 key 對應的 value
V remove(Object key)	刪除 key 對應的映射關系
Set<K> keySet()	返回所有 key 的不重復集合
Collection<V> values()	返回所有 value 的可重復集合
Set<Map.Entry<K, V>> entrySet()	返回所有的 key-value 映射關系
boolean containsKey(Object key)	判斷是否包含 key
boolean containsValue(Object value)	判斷是否包含 value

源代碼

import java.util.HashMap;
import java.util.Map;public class HashMapExample {public static void main(String[] args) {// 創建一個HashMap實例HashMap<String, Integer> myHashMap = new HashMap<>();// 添加鍵值對myHashMap.put("Apple", 1);myHashMap.put("Banana", 2);myHashMap.put("Cherry", 3);System.out.println("HashMap after adding elements: " + myHashMap);// 更新鍵對應的值myHashMap.put("Apple", 4);System.out.println("HashMap after updating 'Apple': " + myHashMap);// 檢查鍵是否存在boolean isPresent = myHashMap.containsKey("Banana");System.out.println("Is 'Banana' a key in the HashMap? " + isPresent);// 刪除鍵值對myHashMap.remove("Banana");System.out.println("HashMap after removing 'Banana': " + myHashMap);// 遍歷HashMapSystem.out.println("Iterating over HashMap:");for (Map.Entry<String, Integer> entry : myHashMap.entrySet()) {System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());}// 獲取特定鍵的值Integer appleValue = myHashMap.get("Apple");System.out.println("Value of 'Apple': " + appleValue);// 檢查一個鍵是否存在且獲取其值Integer orangeValue = myHashMap.getOrDefault("Orange", -1); // 如果沒有找到鍵'Orange'，則返回-1System.out.println("Value of 'Orange' or default: " + orangeValue);}
}

🖊?3.特性

鍵值關聯：HashMap存儲的是鍵值對，其中鍵是唯一的，而值可以重復。
無序性：HashMap中的元素沒有特定的順序，迭代時的順序并不反映插入時的順序。
允許null值和null鍵：HashMap是少數幾個可以接受null鍵和null值的Java集合之一，但每個HashMap只能有一個null鍵。
線程不安全：HashMap不是線程安全的，多線程環境下若不采取額外的同步措施，可能導致數據不一致性。
可調整大小：隨著元素的增加，HashMap會自動擴容來維持其性能，通過重新哈希所有元素到更大的數組中實現。
性能：平均情況下，HashMap提供O(1)的時間復雜度進行插入、刪除和查找操作。

🖍?4.內部實現

哈希表：HashMap的底層實現是一個哈希表，它由一個動態調整大小的數組（稱為桶或bin）組成，數組的每個位置可以是一個鏈表或紅黑樹（JDK 8開始）。
哈希函數：HashMap使用哈希函數將鍵轉換成數組的索引。哈希沖突通過鏈地址法解決，即在同一索引位置的多個元素通過鏈表或紅黑樹鏈接起來。
負載因子：HashMap有一個負載因子，默認為0.75，它決定了HashMap何時進行擴容。當HashMap中的元素數量超過當前容量乘以負載因子時，HashMap會自動擴容，一般擴容為原來的兩倍。
擴容機制：擴容時，HashMap會創建一個新的更大容量的數組，并將原數組中的所有元素重新哈希到新數組中，這個過程涉及到重新計算哈希值和重新分配。

🖌?5.應用場景

緩存：HashMap非常適合做輕量級的緩存，快速存取熱點數據。
數據映射：在需要快速根據鍵查找相關聯值的場景，如配置參數管理。
計數：可以用HashMap統計元素出現的頻率，鍵是元素，值是出現次數。
去重：雖然HashSet更直接，但在需要存儲額外信息或自定義比較邏輯時，HashMap可以用來去重。
圖的鄰接表表示：在圖算法中，HashMap可以用來表示頂點的鄰接關系，鍵是頂點，值是一個列表或集合，包含與該頂點相鄰的所有頂點。

綜上，HashMap憑借其高效的查找和靈活的鍵值對存儲機制，在眾多Java應用中扮演著核心角色。

📝六.對比

Set

Set底層結構	TreeSet	HashSet
底層結構	紅黑樹	哈希桶
插入/刪除/查找時間復雜度	O(log N)	O(1)
是否有序	關于Key有序	不一定有序
線程安全	不安全	不安全
插入/刪除/查找區別	按照紅黑樹的特性來進行插入和刪除	1. 先計算 key 哈希地址 2. 然后進行插入和刪除
比較與覆寫	key必須能夠比較，否則會拋出 ClassCastException異常	自定義類型需要覆寫 equals 和 hashCode 方法
應用場景	需要Key有序場景下	Key 是否有序不關心，需要更高的時間性能

Map

Map底層結構	TreeMap	HashMap
底層結構	紅黑樹	哈希桶
插入/刪除/查找時間復雜度	O(log N)	O(1)
是否有序	關于Key有序	無序
線程安全	不安全	不安全
插入/刪除/查找區別	需要進行元素比較	通過哈希函數計算哈希地址
比較與覆寫	key必須能夠比較，否則會拋出 ClassCastException異常	自定義類型需要覆寫 equals 和 hashCode 方法
應用場景	需要Key有序場景下	Key 是否有序不關心，需要更高的時間性能

?💼七.總結與反思

盛年不重來，一日難再晨，及時當勉勵，歲月不待人。——陶淵明

HashSet學習總結

HashSet是Java集合框架中實現Set接口的一個重要類，它提供了一種無序且不重復元素的集合。HashSet的核心特點是：

不重復性：HashSet不允許存儲重復的元素，這是通過調用元素的hashCode()和equals()方法來確保的。這兩個方法共同決定元素的唯一性。
無序性：HashSet不保證元素的插入順序，遍歷HashSet時得到的順序可能與插入順序不同。
基于HashMap實現：HashSet實際上是對HashMap的一種包裝，它將元素作為HashMap的鍵，而值統一設為一個固定對象（如PRESENT常量），從而達到只關心鍵的目的。
性能優勢：得益于HashMap的哈希表實現，HashSet提供了高效的添加、刪除和查找操作，平均時間復雜度接近O(1)。
注意事項：使用自定義對象作為HashSet的元素時，必須重寫hashCode()和equals()方法，確保邏輯上相同（根據業務定義）的對象具有相同的哈希值和相等性判斷。

HashMap學習總結

HashMap是Java中最常用的鍵值對集合，它實現了Map接口，提供了一種快速存取鍵值對的方式。HashMap的主要特征有：

鍵值對存儲：每個元素由一個鍵和一個值組成，鍵是唯一的，值可以重復。
哈希表結構：內部使用哈希表實現，通過哈希函數將鍵映射到數組的特定索引，解決沖突的方法是鏈地址法（JDK 7及以前是鏈表，JDK 8引入了鏈表/紅黑樹的結構轉換）。
線性探測法和擴容：當哈希碰撞導致沖突時，通過開放尋址法（如線性探測）或鏈表/紅黑樹解決。當HashMap的填充程度達到一定閾值（由負載因子控制，默認0.75），會觸發擴容，以保持高效性能。
線程不安全：HashMap在多線程環境下不是線程安全的，若在并發環境中使用，推薦使用ConcurrentHashMap。
null值處理：HashMap允許一個null鍵和多個null值，這是與某些其他集合類不同的地方。

反思

理解哈希機制的重要性：深入理解哈希函數、沖突解決策略對于高效使用HashSet和HashMap至關重要。實際開發中，合理的重寫hashCode()和equals()方法能夠顯著提升集合操作的性能。
并發使用的風險：在多線程環境下，直接使用HashMap可能導致數據不一致。意識到這一點后，未來在設計系統時，應當優先考慮線程安全的集合類，如ConcurrentHashMap。
性能與內存權衡：雖然HashMap提供了快速的訪問速度，但其內存占用相對較高，尤其是在高負載因子下。在內存敏感的應用中，應權衡性能與內存消耗，選擇合適的集合類型或調整集合參數。
API的深入理解：HashMap和HashSet提供了豐富的API，如computeIfAbsent()、putIfAbsent()等，這些方法在特定場景下能夠簡化代碼，提高效率。掌握并合理利用這些高級API能夠提升代碼質量。

總之，深入學習HashSet和HashMap不僅要求理解其底層數據結構和實現原理，還需關注其在具體應用環境下的適用性和限制，通過實踐不斷加深理解，并靈活運用到項目開發中。

🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

以上，就是本期的全部內容啦，若有錯誤疏忽希望各位大佬及時指出💐

? 制作不易，希望能對各位提供微小的幫助，可否留下你免費的贊呢🌸