Java數據結構第二十三期：Map與Set的高效應用之道(二)

專欄：Java數據結構秘籍

個人主頁：手握風云

一、哈希表

1.1. 概念

1.2. 沖突

1.3. 避免沖突

1.4. 解決沖突

1.5. 實現

二、OJ練習

2.1.?只出現一次的數字

2.2.?隨機鏈表的復制

?2.3.?寶石與石頭

一、哈希表

1.1. 概念

????????順序結構以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，因此在查找?個元素時，必須要經過關鍵碼的多次比較。順序查找時間復雜度為 $O(n)$ ，平衡樹中為樹的?度，即 $O(n)$ ，搜索的效率取決于搜索過程中元素的比較次數。

????????理想的搜索?法：可以不經過任何比較，?次直接從表中得到要搜索的元素。如果構造?種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函數可以很快找到該元素。

????????當向該結構中，根據待插?元素的關鍵碼，以此函數計算出該元素的存儲位置并按此位置進行存放；對元素的關鍵碼進行同樣的計算，把求得的函數值當做元素的存儲位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功。該方式即為哈希(散列)方法，哈希方法中使?的轉換函數稱為哈希(散列)函數，構造出來的結構稱為哈希表(Hash Table)(或者稱散列表)。

????????哈希函數設置為：hash(key) = key % capacity；其中capacity為存儲元素底層空間總的大小。

? ? ? ? 我們設一個整數集合{1,7,6,4,5,9}，把capacity設置為10，那我們就可以按照下圖來存儲。如果我們再想存放一個元素12，我們可以直接通過哈希函數存進下標2中，要想搜索，直接通過2下標來找到12，這樣時間復雜度為 $O(n)$ ，從而提高效率。

1.2. 沖突

????????不同關鍵字通過相同哈希函數計算出相同的哈希地址，該種現象稱為哈希沖突或哈希碰撞。把具有不同關鍵碼?具有相同哈希地址的數據元素稱為“同義詞”。例如我們要想存放一個14，通過上面的哈希函數應該存到4下標，但此時4下標已經存了一個4，就會造成哈希沖突。

????????出現了哈希沖突，我們就要想辦法避免沖突。由于我們哈希表底層數組的容量往往是小于實際要存儲的關鍵字的數量的，就會導致沖突的發?是必然的，但我們能做的應該是盡量的降低沖突率。

1.3. 避免沖突

? ? ? ? 第一種方法可以設計合理的哈希函數。設計原則：定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間；計算出來的地址能均勻分布在整個空間中；比較簡單。

? ? ? ? 直接訂制法：取關鍵字的某個線性函數為散列地址：Hash(Key) = A*Key + B。優點：簡單、均勻。缺點：需要事先知道關鍵字的分布情況。使用場景：適合查找比較小且連續的情況。

? ? ? ? 除留余數法：設散列表中允許的地址數為m，取?個不大于m，但最接近或者等于m的質數p作為除數，按照哈希函數：Hash(key) = key% p(p<=m)，將關鍵碼轉換成哈希地址。

????????哈希函數設計的越精妙，產生哈希沖突的可能性就越低，但是無法避免哈希沖突。

? ? ? ? 我們還有另外一種就是調節負載因子。哈希表的載荷因子為：?=填入表中元素個數/哈希表長度。當沖突率達到?個?法忍受的程度時，我們需要通過降低負載因子來變相的降低沖突率。已知哈希表中已有的關鍵字個數是不可變的，那我們能調整的就只有哈希表中的數組的大小。

1.4. 解決沖突

????????解決哈希沖突兩種常?的?法是：閉散列和開散列。

????????閉散列：也叫開放地址法，當發?哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到沖突位置中的“下?個” 空位置中去。那如何尋找下?個空位置呢？此時我們就需要應用線性探索。從發生沖突的位置開始，依次向后探測，直到尋找到下?個空位置為止。但這樣還是會有一個缺點，就是會使得沖突元素聚集在一起，并且如果我們把4刪除了，又如何尋找14、24、34這些元素。因此線性探測采?標記的偽刪除法來刪除?個元素。

?????????次探測為了避免該問題，找下?個空位置的?法為：Hi = (H0+i^2)%m，i表示沖突的次數，m為表的大小。

????????開散列：開散列法?叫鏈地址法(開鏈法)，?先對關鍵碼集合?散列函數計算散列地址，具有相同地址的關鍵碼歸于同一子集合，每?個?集合稱為?個桶，各個桶中的元素通過?個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中。

1.5. 實現

? ? ? ? 由于我們需要節點數組來創建哈希表，利用內部類來表示節點對象。

public class HashBucket {//創建節點數組static class Node{public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}public Node[] array = new Node[10];public int UsedSize;//表示還系統中存放的元素public static final float LOAD_FACTOR = 0.75f;//負載因子表示為常數
}

????????我們先來模擬哈希表中放元素的方法。我們要想把元素放入，首先得是一個結點。比如key=14，如果表中已經有14了，就不能再放14并且更新val，所以我們首先需要遍歷數組判斷key是否相同，如果相同，更新val。下面再使用頭插法來把節點元素放入哈希表中。插入元素之后，我們還需要重新計算負載因子是否超過了我們規定的LOAD_FACTOR。如果超過了，就需要進行擴容操作。擴容的時候還需要注意，比如我們要插入的元素的key為14，擴容前需要插入下標為4的位置，擴容2倍后，就需要插入下標為14的位置。

????????完整代碼實現：

    public void put(int key, int val) {int index = key % array.length;//先遍歷index數組下的鏈表，如果有相同的key，則更新valNode cur = array[index];while (cur != null) {if (cur.key == key) {cur.val = val;return;}cur = cur.next;}//頭插法Node node = new Node(key, val);node.next = array[index];array[index] = node;UsedSize++;//重新計算負載因子是不是超過了我們規定的值if (CalculateLoadFactor() >= LOAD_FACTOR) {//擴容ReSize();}}private float CalculateLoadFactor() {return UsedSize * 1.0f / array.length;}private void ReSize() {Node[] newArray = new Node[array.length*2];for (Node node : array) {Node cur = node;while (cur != null) {int newIndex = cur.key % newArray.length;//把當前節點放入新數組的位置,再次使用頭插法Node curNext = cur.next;cur.next = newArray[newIndex];newArray[newIndex] = cur;cur = curNext;}}array = newArray;}

? ? ? ? get方法也是一樣，也是通過索引下標來尋找目標值。

    public int get(int key){int index = key % array.length;Node cur = array[index];while(cur != null){if(cur.key == key){return cur.val;}cur = cur.next;}return -1;}

? ? ? ? 我們在Test類里面進行實例化并調試。

public class Test {public static void main(String[] args) {HashBucket hashBucket = new HashBucket();hashBucket.put(11,99);hashBucket.put(2,99);hashBucket.put(43,99);hashBucket.put(4,99);hashBucket.put(14,99);hashBucket.put(24,99);hashBucket.put(7,99);hashBucket.put(8,99);}
}

????????我們上面的方法key是整型，那如果key是引用類型呢，比如String或者Person類。那我們就把整型換作是泛型K、V。需要注意的是，key換成了泛型，不能直接進行%操作，我們可以使用hashCode方法轉成整型，并且進行比較要使用equals方法。

/*** @author: gao* @create-date: 2025/3/15 16:32*/public class HashBucket<K, V> {static class Node<K, V> {public K key;public V val;public Node<K, V> next;public Node(K key, V val) {this.key = key;this.val = val;}}public Node<K, V>[] array = (Node<K, V>[]) new Node[10];public int UsedSize;//表示還系統中存放的元素public static final float LOAD_FACTOR = 0.75f;//負載因子表示為常數public void put(K key, V val) {int hashcode = key.hashCode();int index = hashcode % array.length;//先遍歷index數組下的鏈表，如果有相同的key，則更新valNode<K, V> cur = array[index];while (cur != null) {if (cur.key == key) {cur.val = val;return;}cur = cur.next;}Node<K, V> node = new Node<K, V>(key, val);node.next = array[index];array[index] = node;UsedSize++;}public V get(K key) {int hashcode = key.hashCode();int index = hashcode % array.length;Node<K, V> cur = array[index];while (cur != null) {if (cur.key.equals(key)) {return cur.val;}cur = cur.next;}return null;}
}

????????如果我們要判斷是否為同一個人，我們可以判斷身份證號碼是否相等。如果我們按照這種方法去寫，發現比較結果為false。這是因為我們沒有重寫equals和hashCode方法，編譯器默認調用Object方法。

class Person {public String id;public Person(String id) {this.id = id;}
}public class Test {public static void main(String[] args) {Person person1 = new Person("1234");Person person2 = new Person("1234");System.out.println(person1.equals(person2));System.out.println(person1.hashCode());System.out.println(person2.hashCode());}
}

    public boolean equals(Object obj) {return (this == obj);}

? ? ? ? 我們在Person類里面右擊，點擊Generate，再點擊equals() and hashCode()，就可以重寫。

    @Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return Objects.equals(id, person.id);}@Overridepublic int hashCode() {return Objects.hash(id);}

二、OJ練習

2.1.?只出現一次的數字

????????我們的基本思路是：利用HashSet，先遍歷一遍數組，把集合中沒有的數字放入，如果有，再移除，最后集合中剩下的元素就是只出現一次的數字，再遍歷一遍數組，匹配HashSet中的數組。

????????完整代碼實現：

class Solution {public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();for (int i = 0;i < nums.length;i++) {if(! set.contains(nums[i])){set.add(nums[i]);}else{set.remove(nums[i]);}}for (int i = 0;i < nums.length;i++) {if(set.contains(nums[i])){return nums[i];}}return -1;}
}

????????執行時間還是比較高，因為使用了兩次for循環遍歷數組。

2.2.?隨機鏈表的復制

? ? ? ? 題目比較長，大概題意就是復制出一份與原來相同的鏈表。這道題的難點在于比單鏈表多了一個可以指向任意節點或者空的random域。起初，很多人會去想定義一個Node cur去遍歷一遍鏈表，一個一個節點進行拷貝，但一拷貝就會發現問題，因為我們我們不知道cur.next和cur.random是哪一個節點的地址。既然遍歷一遍鏈表不行，那就遍歷兩遍。第一遍遍歷，所有節點的val域全都拷貝過來，next域以及random域全都默認為null，每遍歷一個鏈表，就新實例化一個節點。然后我們<K,V>結構來建立老節點與新節點之間的映射關系。

????????我們每獲取一個節點的地址，都可以修改它的next域與random域。

????????完整代碼實現：

class Solution {public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();//第一遍遍歷鏈表Node cur = head;while(cur != null){Node node = new Node(cur.val);map.put(cur,node);cur = cur.next;}//第二遍遍歷鏈表cur = head;while(cur != null){map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}
}

?2.3.?寶石與石頭

????????題目很簡單，就是查找stones中含有jewels中的字符的個數。我們先遍歷jewels字符串，將里面的字符放入集合中，再去遍歷stones中的字符，最后返回寶石個數。

????????完整代碼實現：

class Solution {public int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet<>();for (int i = 0; i < jewels.length(); i++) {char ch = jewels.charAt(i);set.add(ch);}int count = 0;for (int i = 0; i < stones.length(); i++) {char ch = stones.charAt(i);if(set.contains(ch)){count++;}}return count;}
}