🎉🎉🎉點進來你就是我的人了
博主主頁：🙈🙈🙈戳一戳,歡迎大佬指點!

歡迎志同道合的朋友一起加油喔🦾🦾🦾

---

目錄

1.概念

1.1概念及場景

1.2 模型

1.3 Map的說明

1.4 Map方法的介紹

1.5 Set的說明

1.6 Set方法的介紹

2、哈希表

2.1 什么是哈希表

3. 哈希沖突

3.1 概念

?3.2 降低哈希沖突的發生的概率

3.2.1 設計好的哈希函數

3.2.2 降低負載因子

3.3.當沖突發生時如何解決哈希沖突（簡單介紹）

閉散列：有兩種（線性探測法&&二次探測法）

線性探測

二次探測

開散列：它的叫法有很多，也叫做哈希桶/鏈地址法/拉鏈法

?③若遇到負載因子過大，要擴容，那么存入的數據又該怎么進行處理？？？（鏈表中的每一個數要進行重新哈希）,以下為二倍擴容后的圖?編輯實現一個哈希表

?重寫hashCode()方法

性能分析

小結

4.哈希表部分底層源碼的分析

5. 一些有關 Map 和 Set 的題目

1. 統計一組數據中的每個數據出現了多少次

2. 將一組數據中多余的數據去重

3. 找出第一個重復出現的數據

4. 只出現一次的數字

5. 復制帶隨機指針的鏈表

6. 寶石與石頭

7. 鍵盤壞了的鍵

8. 前K個高頻單詞

---

---

1.概念

1.1概念及場景

①Map和Set的作用：

一種專門用來進行搜索的容器或者數據結構，其搜索的效率與其具體的實例化子類有關?。

②Map和Set相比于其他類型的優點：

之前我們學過的常見搜索方式有：??直接遍歷，?二分查找等

上述排序比較適合靜態類型的查找，即一般不會對區間進行插入和刪除操作了，而現實中的查找比如：

1. 根據姓名查詢考試成績

2.?通訊錄，即根據姓名查詢聯系方式

3.?不重復集合，即需要先搜索關鍵字是否已經在集合中

可能在查找時進行一些插入和刪除的操作，即動態查找，那上述兩種方式就不太適合了，本節介紹的?Map?和?Set?是 一種適合?動態查找的集合容器?。

1.2 模型

1.?純 key 模型：

eg.有一個英文詞典，快速查找一個單詞是否在詞典中 ；快速查找某個名字在不在通訊錄中

2.Key-Value 模型：

eg.統計文件中每個單詞出現的次數，統計結果是每個單詞都有與其對應的次數：<單詞，單詞出現的次數?> ;梁山好漢的江湖綽號：每個好漢都有自己的江湖綽號

而?Map中存儲的就是key-value的鍵值對，Set中只存儲了Key

1.3 Map的說明

Map?中存儲的是?key-value的鍵值對，?Map?是一個接口類，該類沒有繼承自?Collection?，該類中存儲的是?<K,V>?結構的鍵值對，并且?K?一定是唯一的，不?能重復?。

1.4 Map方法的介紹

方法	解釋
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

Map的注意事項：

1.?Map?是一個接口，不能直接實例化對象?，如果?要實例化對象只能實例化其實現類?TreeMap?或者?HashMap。

2.?Map?中存放鍵值對的?Key?是唯一的，?value?是可以重復的（重復的情況，后面put的覆蓋前面的）。

3.?Map?中的?Key?可以全部分離出來，存儲到?Set?中?來進行訪問?(?因為?Key?不能重復?)?。

4.?Map?中的?value?可以全部分離出來，存儲在?Collection?的任何一個子集合中?(value?可能有重復?)?。

5. Map?中鍵值對的?Key?不能直接修改，?value?可以修改，如果要修改?key?，只能先將該?key?刪除掉，然后再來進行重新插入。

TreeMap?和?HashMap?的區別：

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

其中 Set<Map.Entry<K, V>> entry?Set() 這個方法非常復雜但也非常重要，所以要做一些具體的說明：

Map.Entry<K, V>?是?Map?內部實現的用來存放??<key, value>??鍵值對映射關系的內部類?，該內部類中主要提供了? <key, value> 的獲取，?value?的設置以及?Key?的比較方式。

如何理解？？？？通俗來說就是：

Entry是Map里面的一個內部類，而 Map.Entry<key，val> 的作用就是把一個個map元素(key，val) 打包成一個整體，而這個整體的類型就是 Map.Entry<K，V>, 然后我們有一個Set集合，它里面存放的每個元素的類型就是 Map.Entry<K，V>。這里可以聯想到我們的單鏈表的內部類ListNode，將 val，next 打包成一個整體，那么它的類型就是ListNode。

?所以下面這段代碼運行起來一定會把Set集合中存放的map中的每一個元素都輸出出來：

public static void main(String[] args) {Map<String, Integer> map = new HashMap<>();map.put("hello",2);map.put("world",1);map.put("bit",3);Set<Map.Entry<String, Integer>> entrySet = map.entrySet();for (Map.Entry<String,Integer> entry:entrySet) {System.out.println("key: "+entry.getKey()+" val: "+entry.getValue());} }

該內部類Entry提供的一些方法也是比較重要的：

方法	解釋
K?getKey?()	返回?entry?中的?key
V?getValue?()	返回?entry?中的?value
V setValue(V value)	將鍵值對中的?value?替換為指定?value

1.5 Set的說明

Set?與?Map?主要的不同有兩點：?Set?是繼承自?Collection?的接口類，?Set?中只存儲了?Key?。

1.6 Set方法的介紹

方法	解釋
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?中，可以達到去重的效果

Set的注意事項：

1. Set?是繼承自?Collection?的一個接口類。

2. Set?中只存儲了?key?，并且要求?key?一定要唯一。

3. Set?的底層是使用?Map?來實現的，其使用?key?與?Object?的一個默認對象作為鍵值對插入到?Map?中的。

4. Set?最大的功能就是對集合中的元素進行去重。

5.?實現?Set?接口的常用類有?TreeSet?和?HashSet?，還有一個?LinkedHashSet?，?LinkedHashSet?是在?HashSet?的基礎上維護了一個雙向鏈表來記錄元素的插入次序。

6. Set?中的?Key?不能修改，如果要修改，先將原來的刪除掉，然后再重新插入。

7. Set?中不能插入?null?的?key?。

TreeSet?和?HashSet?的區別?：

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

為什么HashMap和HashSet無序，而TreeMap和TreeSet有序？？后面會解釋到。

2、哈希表

2.1 什么是哈希表

最理想的搜索方法 , 即就是在查找某元素時 , 不進行任何比較的操作 , 一次直接查找到需要搜索的元素 , 可以達到這種要求的方法就是哈希表.

哈希表就是通過構造一種存儲結構 , 通過某種函數使元素存儲的位置與其關鍵碼位形成一 一映射的關系 , 這樣在查找元素的時候就可以很快找到目標元素.

哈希方法中使用的轉換函數稱為哈希(散列)函數，構造出來的結構稱為哈希表(Hash Table)(或者稱散列表)

例如:

存在一個數組集合 {1，7，6，4，5，9}.
哈希函數設置為：hash(key) = key % capacity;
capacity 為存儲元素底層空間總的大小。

如圖所示:?這樣存儲數據更加便于查找

?采取上面的方法，確實能避免多次關鍵碼的比較，搜索的效率也提高的，但是問題來了，拿上述圖的情況來舉例子的話，我接著還要插入一個元素 14，該怎么辦呢？

這個就是我們本章的重點，哈希沖突，4%10 = 4；14%10 = 4，此時發生了哈希沖突。

3. 哈希沖突

3.1 概念

首先我們得知道，哈希沖突是必然的，無論怎么插入，插入多少都無法杜絕，哪怕就插入兩個元素4，14都發生了哈希沖突，我們能做的就是盡量避免哈希沖突的發生。

這也就是我們哈希表這種結構存在的問題。

哈希沖突的概念：兩個不同關鍵字key通過相同哈希哈數計算出相同的哈希地址，該種現象稱為哈希沖突或哈希碰撞。????????????????

?把具有不同關鍵碼而具有相同哈希地址的數據元素稱為“同義詞”。

?3.2 降低哈希沖突的發生的概率

兩種解決方法

1.設計好的哈希函數；2.降低負載因子

3.2.1 設計好的哈希函數

哈希函數設計原則：

• 哈希函數的定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間。

• 哈希函數計算出來的地址能均勻分布在整個空間中。

• 哈希函數應該比較簡單。

常用的兩種哈希函數

1.?直接定制法

取關鍵字的某個線性函數為散列地址：?Hash?（?Key?）?= A*Key + B

優點：簡單、均勻。

缺點：需要事先知道關?鍵字的分布情況 使用場景：適合查找比較小且連續的情況。

力扣上這道題可以幫助我們理解：?字符串中第一個只出現一次字符

2.?除留余數法

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

3.2.2 降低負載因子

下圖是沖突率和負載因子的關系圖：

?從圖中我們可以直到要想降低沖突的概率，只能減小負載因子，而負載因子又取決于數組的長度。

公式：? ?負載因子 = 哈希表中元素的個數 / 數組的長度

因為哈希表中的已有的元素個數是不可變的，所以我們只能通過增大數組長度來降低負載因子。

3.3.當沖突發生時如何解決哈希沖突（簡單介紹）

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

閉散列：有兩種（線性探測法&&二次探測法）

閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以?把?key?存放到沖突位置中的?“?下一個?”?空位置中去。

線性探測

①什么是線性探測：

從發生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。

②線性探測的相關操作：

當插入操作時，通過哈希函數獲取待插入元素在哈希表中的位置 ；如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發生哈希沖突，使用線性探測找到 ；下一個空位置，插入新元素

簡而言之就是尋找下一個空的地方

③弊端：（可能會導致沖突元素均被放在一起）?

二次探測

①如何進行二次探測：

利用這個公式進入插入。其中：i = 1,2,3…，Hi是通過散列函數Hash(x)對元素的關鍵碼?key?進行計算得到的位置，m是表的大小。

對于上述線性探測中的問題如果要插入44，產生沖突，使用解決后的情況為：

②重要結論：

當表的長度為質數且表裝載因子?a?不超過?0.5?時，新的表項一定能夠插入，而且任何一個位置都不會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時可以不考慮表裝滿的情 況，但在插入時必須確保表的裝載因子a?不超過?0.5?，如果超出必須考慮增容。

因此：閉散列最大的缺陷就是空間利用率比較低，這也是哈希的缺陷。

開散列：它的叫法有很多，也叫做哈希桶/鏈地址法/拉鏈法

①什么是哈希桶？？？

開散列法又叫鏈地址法?(?開鏈法?) , 首先對關鍵碼集合用散列函數計算散列地址，具有相同地址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中。 開散列，可以認為是把一個在大集合中的搜索問題轉化為在小集合中做搜索了。?參照下圖：

?②哈希桶如何進行存儲？？？（鏈式存儲法）

?③若遇到負載因子過大，要擴容，那么存入的數據又該怎么進行處理？？？（鏈表中的每一個數要進行重新哈希）,以下為二倍擴容后的圖實現一個哈希表

代碼如下：

public class HashBuck {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;public int usedSize;public static final double DEFAULT_LOAD_FACTOR = 0.75;public HashBuck() {this.array = new Node[10];}/*** put函數* @param key* @param val*/public void put(int key,int val) {//1、找到Key所在的位置int index = key % this.array.length;//2、遍歷這個下標的鏈表，看是不是有相同的key。有 要更新val值的Node cur = array[index];while (cur != null) {if(cur.key == key) {cur.val = val;//更新val值return;}cur = cur.next;}//3、沒有這個key這個元素，頭插法Node node = new Node(key, val);node.next = array[index];array[index] = node;this.usedSize++;//4、插入元素成功之后，檢查當前散列表的負載因子if(loadFactor() >= DEFAULT_LOAD_FACTOR) {resize();//}}//擴容private void resize() {Node[] newArray = new Node[array.length*2];for (int i = 0; i < array.length; i++) {Node cur = array[i];while (cur != null) {int index = cur.key % newArray.length;//獲取新的下標 11//就是把cur這個節點，以頭插/尾插的形式 插入到新的數組對應下標的鏈表當中Node curNext = cur.next;cur.next = newArray[index];//先綁定后面newArray[index] = cur;//綁定前面cur = curNext;}}array = newArray;}private double loadFactor() {return 1.0*usedSize/array.length;}/*** 根據key獲取val值* @param key* @return*/public int get(int key) {//1、找到Key所在的位置int index = key % this.array.length;//2、遍歷這個下標的鏈表，看是不是有相同的key。有 要更新val值的Node cur = array[index];while (cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}return -1;}

?說明：以上的代碼只是簡單的實現了兩個重要的函數：插數據和取數據

并且只是簡單的實現，底層的樹化并沒有實現。

問題--》

問題一：以上代碼的key是整形，所以找地址的時候，可以直接用 key % array.length，如果我的key是一個引用類型呢？？？，我怎么找地址？？？

下面這段代碼，兩者的 id 都一樣，運行結果卻不一樣，這就和我們剛剛的相同的key發生沖突就不一致了。

class Person {public String id;public Person(String id) {this.id = id;}@Overridepublic String toString() {return "Person{" +"id=" + id +'}';} } public class Test {public static void main(String[] args) {Person person1 = new Person("134");Person person2 = new Person("134");System.out.println(person1.hashCode());System.out.println(person2.hashCode());} }

但是這個時候直接輸出他們的hashcode卻是不相同的

?重寫hashCode()方法

class Person {public String id;public Person(String id) {this.id = id;}@Overridepublic String toString() {return "Person{" +"id=" + id +'}';}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return id == person.id;}@Overridepublic int hashCode() {return Objects.hash(id);} } public class Test {public static void main(String[] args) {Person person1 = new Person("134");Person person2 = new Person("134");System.out.println(person1.hashCode());System.out.println(person2.hashCode());} }

1.為什么引用類型就要談到 hashCode() ？？

因為如果key是引用類型，就不能通過模上數組的長度來尋址了。而 hashCode() 作用就是返回對象的哈希代碼值，簡單來說，他就是一個整數

2.按道理來說，學號相同的兩個對象應該是同一個人，為什么重寫 hashCode()，返回對象的哈希代碼值才會一樣，不重寫為什么會導致最終在數組中尋找的地址不相同？？

因為底層的hashCode()是Object類的方法，底層是由C/C++代碼寫的，我們是看不到，但是因為它是根據對象的存儲位置來返回的哈希代碼值，這里就可以解釋了，person1和person2本質上就是兩個不同的對象，在內存中存儲的地址也不同，所以最終返回的哈希代碼值必然是不相同的，哈希代碼值不同，那么在數組中根據 hash % array.length 尋找的地址也就不相同。而重寫 hashCode() 方法之后，咱們根據 Person 中的成員變量 id 來返回對應的哈希代碼值，這就相當于當一個對象，多次調用，那么返回的哈希代碼值就必然相同。

所以我們的哈希表的實現就可以相應的改寫成這樣：

public class HashBuck<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 double DEFAULT_LOAD_FACTOR = 0.75;public void put(K key, V val) {Node<K,V> node = new Node<>(key,val);int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while(cur != null) {if(cur.key.equals(key)) {cur.val = val;return;}cur = cur.next;}//頭插node.next = array[index];array[index] = node;this.usedSize++;if(loadFactor() >= DEFAULT_LOAD_FACTOR) {reSize();}}private double loadFactor() {return this.usedSize * 1.0 / array.length;}private void reSize() {Node<K,V>[] newArray = (Node<K, V>[]) new Node[2 * array.length];for (int i = 0; i < array.length; i++) {Node<K,V> cur = array[i];while (cur != null) {Node<K,V> curNext = cur.next;int hash = cur.key.hashCode();int index = hash % newArray.length;cur.next = newArray[index];newArray[index] = cur;cur = cur.next;}}array = newArray;}public V get(K key) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while(cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}return null;} }

性能分析

雖然哈希表一直在和沖突做斗爭，但在實際使用過程中，我們認為哈希表的沖突率是不高的，沖突個數是可控的，也就是每個桶中的鏈表的長度是一個常數，所以，通常意義下，我們認為哈希表的插入?/?刪除?/?查找時間復雜度是?O(1)

面試問題一：hashCode()和equals() 在HashMap中的作用分別是什么？？？

hashCode()：用來找元素在數組中的位置；

equals()：用來比較數組下鏈表中的每個元素的 key 與我的 key 是否相同。

equals也一樣，如果不重寫，上面的person1和person2的比較結果必然是不相同。

hashCode()和equals()就好比查字典，比如要查美麗，肯定要先查美字在多少頁--hashCode()，然后它的組詞有美景，美女，美麗，equals()就能找到美麗。

面試問題二：如果hashCode一樣，那么equals一定一樣嗎? 如果equals一樣，hashCode一定一樣嗎？？

答案肯定是不一定，一定。

同一個地址下鏈表中的key不一定一樣，就好比數組長度為10，4和14找到的都是4下標。

而equals一樣，hashCode就一定一樣，4和4肯定都在4下標。

所以這時候再回過頭來看HashMap數據的打印時，就能明白HashMap和HashSet為什么無序了，它本身就不是一個順序結構,至于TreeMap和TreeSet為啥有序，這就和我們之前學過的優先級隊列是一個道理了。（整形的key，輸出時，自然而然就排好序了，如果key是引用類型，則需要實現Comparable接口，或者傳比較器）

小結

1. HashMap 和 HashSet 即 java 中利用哈希表實現的 Map 和 Set
2. java 中使用的是哈希桶方式解決沖突的
3. java 會在沖突鏈表長度大于一定閾值后，將鏈表轉變為搜索樹（紅黑樹）
4. java 中計算哈希值實際上是調用的類的 hashCode 方法，進行 key 的相等性比較是調用 key 的 equals 方法。所以如果要用自定義類作為 HashMap 的 key 或者 HashSet 的值，必須覆寫 hashCode 和 equals 方法，而且要做到 equals 相等的對象，hashCode 一定是一致的。

4.哈希表部分底層源碼的分析

哈希表底層部分成員屬性的分析：?

? 面試問題:以下兩個桶的數組容量分別是多大？

HashMap<String,Integer> map = new HashMap<>(19); //桶1HashMap<String,Integer> map = new HashMap<>(); //桶2

剛剛我們分析了成員屬性和成員方法，桶的只是定義了，并沒有看見給桶開辟大小？？那我們如何put 進去元素呢？

首先可以確定的是桶 2 的大小為 0，至于為什么沒開辟空間也可以 put 元素，我們就需要分析底層的 put 函數，接下來我們帶著疑惑繼續分析源碼，，

??結論：

1.桶2的默認大小是0，但是在put進去第一個元素時，它的容量就擴容為了16.

2.我們可以看到底層尋址的方式不是 hash?% array.length，而是 (n-1) & hash，因為?JDK規定數組的長度必須是 2 的某個次冪。因為當 n 是 2 的某個次冪時，hash % array.length 與(n-1) & hash 得到的值是一樣的，并且位運算的效率高。所以桶1的容量就不是19，而是2的某個次冪向上取整，所以桶1大小為32，我們可以繼續看帶一個參數的構造方法的源碼：

5. 一些有關 Map 和 Set 的題目

1. 統計一組數據中的每個數據出現了多少次

/*** 統計一組數據中的每個數據出現了多少次*/import java.util.HashMap; import java.util.Map;public class Test {public static void main(String[] args) {char[] arr = {'a','c','e','c','b','d','f','c','d'};Map<Character,Integer> map = computer(arr);System.out.println(map);}public static Map<Character,Integer> computer(char[] arr){Map<Character,Integer> map = new HashMap<>();//如果在 map 中沒有數組對應的 Key，那么就添加 1個 Key 進去//如果在 map 中包含了和數組對應的 Key，且 Key 對應 count個 Val,//那么就添加 count + 1個 Key 進去for (char x :arr) {if(map.containsKey(x)){int count = map.get(x);map.put(x, count+1);}else {map.put(x,1);}}return map;} }

2. 將一組數據中多余的數據去重

/*** 將一組數據中多余的數據去重*/import java.util.HashSet; import java.util.Set;public class Test {public static void main(String[] args) {int[] arr = {1,3,5,7,9,3,2,4,6,8,5,4,6};Set<Integer> set = new HashSet<>();for (int x : arr) {set.add(x);}System.out.println(set);} }

3. 找出第一個重復出現的數據

/*** 在一組數據中，找出第一個重復出現的數據*/import java.util.HashSet; import java.util.Set;public class Test6 {public static void main(String[] args) {int[] arr = {1,3,5,7,9,3,2,4,6,8,5,4,6};Set<Integer> set = new HashSet<>();int i = 0;//如果在添加元素到 set 之前，就已經發現了 set 中包含某個數組的元素，//那么就 breakfor (i = 0; i < arr.length; i++) {if(set.contains(arr[i])){break;}set.add(arr[i]);}System.out.println(arr[i]); //拿到的就是第一次出現的重復值} }

4. 只出現一次的數字

leetcode 136

方法一：

/*** 利用兩兩元素之間異或，最終得出的就是單獨元素*/ class Solution {public int singleNumber(int[] nums) {int x = nums[0];for(int i= 1; i<nums.length; i++){x = x^nums[i];}return x;} }

方法二：

/*** 利用集合 Set* 如果集合中有相同元素，就移除，反之，就添加*/ 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;} }

5. 復制帶隨機指針的鏈表

leetcode 138

本題需要詳細掌握 Map 的操作，與其對應的映射關系，才能將本題理解到位。

/*** 通過 Map 的映射關系* 知道了 Key 的狀態，實現 Value 的狀態* 即通過舊節點之間的關系，實現新節點之間的關系*/ class Solution {public Node copyRandomList(Node head) {if(head == null) return null;//Key - 舊節點，Value - 新節點Map<Node,Node> map = new HashMap<>(); Node cur = head;//1. 創建新的節點while(cur != null){map.put(cur, new Node(cur.val)); cur = cur.next;}cur = head;//2. 連接各個節點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);} }

6. 寶石與石頭

leetcode 771

方法一

/*** 方法一* 1. 將 jewels 字符串中的字符放入集合 set 中* 2. 查看集合 set 中是否包含 stones 字符數組中字符* 3. 用 count 計數，最后返回*/ class Solution {public int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet<>();for(char x:jewels.toCharArray()){ //1.set.add(x);}int count = 0;for(char j:stones.toCharArray()){ //2.if(set.contains(j)){count++;}}return count; //3.} }

方法二

/*** 方法二* 兩層 for 循環 */ class Solution {public int numJewelsInStones(String jewels, String stones) {int count = 0;for(int i=0; i<jewels.length(); i++){for(int j=0; j<stones.length();j++){if( jewels.charAt(i) == stones.charAt(j) ){count++;}}}return count;} }

7. 鍵盤壞了的鍵

牛客網鏈接

import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; import java.util.Set;/*** 1. 將實際輸入的文字 str2 放在集合 set 中* 2. for 循環遍歷應該輸入的文字 str1, * 若集合 set 不包含某個字符，且線性表之前也未出現該字符，就輸出打印* 3. 將步驟 2 中不包含的字符放入順序表中,以便下一次判斷*/ public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String str1 = scanner.nextLine(); //應該輸入的文字String str2 = scanner.nextLine(); //實際輸入的文字out(str1,str2);}public static void out(String str1, String str2){Set<Character> set = new HashSet<>();ArrayList<Character> list = new ArrayList<>();for (char x:str2.toUpperCase().toCharArray()) {set.add(x); //1.}for(char x:str1.toUpperCase().toCharArray()){ //2.if(!set.contains(x) && !list.contains(x)){ System.out.print(x);}list.add(x); //3.}} }

8. 前K個高頻單詞

??? 力扣鏈接

class Solution {public List<String> topKFrequent(String[] words, int k) {Map<String,Integer> hashMap =new HashMap<>();for(String s: words) {if(hashMap.get(s) == null) {hashMap.put(s,1);}else {hashMap.put(s,hashMap.get(s)+1);}}//2、建立小根堆PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {if(o1.getValue().compareTo(o2.getValue()) == 0) {return o2.getKey().compareTo(o1.getKey());}return o1.getValue().compareTo(o2.getValue());}});//3、遍歷hashMap 把里面 的數據 放到小根堆for(Map.Entry<String,Integer> entry : hashMap.entrySet()) {if(minHeap.size() < k) {minHeap.offer(entry);}else {//小根堆放滿了K個，下一個entry和堆頂元素比較Map.Entry<String,Integer> top = minHeap.peek();//堆頂的頻率小于當前entry的頻率 就出隊 然后入隊entryif(top.getValue().compareTo(entry.getValue()) < 0) {minHeap.poll();minHeap.add(entry);}else {//頻率相同的情況if(top.getValue().compareTo(entry.getValue()) == 0) {if(top.getKey().compareTo(entry.getKey()) > 0) {minHeap.poll();minHeap.add(entry);}}}}}//4、 此時小根堆當中已經有了結果//System.out.println(minHeap);List<String> ret = new ArrayList<>();for (int i = 0; i < k; i++) {String key = minHeap.poll().getKey();ret.add(key);}Collections.reverse(ret);//System.out.println("ret: "+ret);return ret;} }

總結

以上是生活随笔為你收集整理的【Java 数据结构】Map和Set的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。