Java?集合框架掌握?Map?和?Set?的使用(內(nèi)含哈希表源碼解讀及面試?？碱})
1. 搜索
1.1 場景引入
在學習編程時，我們常見的搜索方式有：
- 直接遍歷：時間復雜度為 O(N)，元素如果比較多效率會非常慢
- 二分查找：時間復雜度為 O(logN)，搜索前必須要求序列有序
但是上述排序比較適合靜態(tài)類型的查找，即一般不會對區(qū)間進行插入和刪除操作。
而現(xiàn)實中的查找如：
- 根據(jù)姓名查詢考試成績
- 通訊錄（根據(jù)姓名查詢聯(lián)系方式）
可能在查找時需要進行一些插入和刪除操作，即動態(tài)查找。因此上述排序的方式就不太適合。
1.2 模型
一般會把要搜索的數(shù)據(jù)稱為關(guān)鍵字（Key），和關(guān)鍵字對應(yīng)的稱為值（Value），這兩者又能組合成為 Key-Value 的鍵值對。
因此動態(tài)查找的模型有下面兩種：
純 Key 模型： Set 的存儲模式，比如：
- 有一個英文詞典，快速查找一個單詞是否在詞典中
- 快速查找某個名字在不在通訊錄中
Key-Value 模型： Map 的存儲模式，比如：
- 統(tǒng)計文件中每個單詞出現(xiàn)的次數(shù)，統(tǒng)計結(jié)果是每個單詞都有與其對應(yīng)的次數(shù)：<單詞， 單詞出現(xiàn)的次數(shù)>
- 梁山好漢的江湖綽號，每個好漢都有自己的江湖綽號：<好漢， 江湖綽號>
2. Map
2.1 關(guān)于 Map 的介紹
簡單介紹：
Map 是一個接口類，沒有繼承自 Collection。該類中存儲的是 <K, V> 結(jié)構(gòu)的鍵值對，并且 K 一定是唯一的，不能重復
注意：
- Map 接口位于 java.util 包中，使用前需要引入它
- Map 是一個接口類，故不能直接實例化對象。如果要實例化對象只能實例化其實現(xiàn)類 TreeMap 或 HashMap
- Map 中存放的鍵值對的 Key 是唯一的，Value 是可以重復的
文檔信息：
2.2 關(guān)于 Map.Entry<K, V> 的介紹
簡單介紹：
Map.Entry<K, V> 是 Map 內(nèi)部實現(xiàn)的用來存放 <Key, Value> 鍵值對映射關(guān)系的內(nèi)部類。該內(nèi)部類中主要提供了 <Key, Value> 的獲取，Value 的設(shè)置以及 Key 的比較方式
常用方法：
| 方法 | 說明 |
|---|---|
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 將鍵值對中的 value 替換為指定的 value |
注意：
Map.Entry<K, V> 并沒有提供設(shè)置 Key 的方法
文檔信息：
2.3 Map 的常用方法說明
注意：
- 往 Map 中存儲數(shù)據(jù)時，會先根據(jù) key 做出一系列的運算，再存儲到 Map 中
- 如果 key 一樣，那么新插入的 key 的 value，會覆蓋原來 key 的 value
- 在 Map 中插入鍵值對時，key 和 value 都可以為 null
- Map 中的 key 可以全部分離出來，存儲到 Set 中來進行訪問（因為 key 是不能重復的）
- Map 中的 value 可以全部分離出來，存儲到
Collection的任何一個子集中（注意 value 可能有重復） - Map 中的鍵值對的 key 不能直接修改，value 可以修改。如果要修改 key，只能先將 key 刪掉，然后再進行重新插入（或者直接覆蓋）
2.4 關(guān)于 HashMap 的介紹
簡單介紹：
HashMap是一個散列表，它存儲的內(nèi)容是鍵值對（key-value）映射- HashMap 實現(xiàn)了 Map 接口，根據(jù)鍵的
HashCode值存儲數(shù)據(jù)，具有很快的訪問速度，最多允許一條記錄的鍵為 null，不支持線程同步 - HashMap 是無序的，即不會記錄插入的順序
- HashMap 繼承于 AbstractMap，實現(xiàn)了 Map、Cloneable、
java.io.Serializable接口
注意：
HashMap 類位于 java.util 包中，使用前需要引入它
文檔信息：
2.5 關(guān)于 TreeMap 的介紹
簡單介紹：
- TreeMap 是一個能比較元素大小的 Map 集合，會對傳入的 key 進行大小排序。其中可以使用元素的自然順序，也可以使用集合中自定義的比較器來進行排序。
- 不同于 HashMap 的哈希映射，TreeMap 底層實現(xiàn)了樹形結(jié)構(gòu)，即紅黑樹的結(jié)構(gòu)。
注意：
TreeMap 類位于 java.util 包中，使用前需要引入它
文檔信息：
2.6 HashMap 和 TreeMap 的區(qū)別
2.7 Map 使用示例代碼
注意：Map 是一個接口類，故不能直接實例化對象，以下以 HashMap 作為實現(xiàn)類為例
示例一： 創(chuàng)建一個 Map 實例
Map<String,String> map=new HashMap<>();
示例二： 插入 key 及其對應(yīng)值為 value
map.put("惠城","法師");
map.put("曉","刺客");
map.put("喵班長","盜劍客");
System.out.println(map);
// 結(jié)果為：{惠城=法師, 曉=刺客, 喵班長=盜劍客}
示例三： 返回 key 的對應(yīng) value
String str1=map.get("曉");
System.out.println(str1);
// 結(jié)果為：刺客
示例四： 返回 key 對應(yīng)的 value，若 key 不存在，則返回默認值 defaultValue
String str2=map.getOrDefault("彌惠","冒險者");
System.out.println(str2);
// 結(jié)果為：冒險者
示例五： 刪除 key 對應(yīng)的映射關(guān)系
String str3=map.remove("喵班長");
System.out.println(str3);
System.out.println(map);
// 結(jié)果為：盜劍客 和 {惠城=法師, 曉=刺客}
示例六： 除了上述直接打印 map，也可以通過 Set<Map.Entry<K, V>> entrySet() 這個方法進行遍歷打印
Set<Map.Entry<String,String>> set=map.entrySet();
for(Map.Entry<String,String> str: set){
System.out.println("Key="+str.getKey()+" Value="+str.getValue());
}
/** 結(jié)果為：
Key=惠城 Value=法師
Key=曉 Value=刺客
Key=喵班長 Value=盜劍客
*/
示例七： 判斷是否包含 key
System.out.println(map.containsKey("惠城"));
// 結(jié)果為：true
3. Set
3.1 關(guān)于 Set 的介紹
簡單介紹：
Set 是一個繼承于 Collection 的接口，是一個不允許出現(xiàn)重復元素，并且無序的集合，主要有 HashSet 和 TreeSet 兩大實現(xiàn)類。
注意：
Set 接口位于 java.util 包中，使用前需要引入它
文檔信息：
3.1 Set 的常用方法說明
注意：
Set 中只繼承了 Key，并且要求 Key 唯一
Set 的底層是使用 Map 來實現(xiàn)的，其使用 Key 與 Object 的一個默認對象作為鍵值對插入插入到 Map 中
Set 的最大功能就是對集合中的元素進行去重
實現(xiàn) Set 接口的常用類有 TreeSet 和 HashSet，還有一個 LinkedHashSet，LinkedHashSet 是在 HashSet 的基礎(chǔ)上維護了一個雙向鏈表來記錄元素的插入次序
Set 中的 Key 不能修改，如果修改，要先將原來的刪除
Set 中可以插入 null
3.3 關(guān)于 TreeSet 的介紹
簡單介紹：
TreeSet 實現(xiàn)類 Set 接口，基于 Map 實現(xiàn)，其底層結(jié)構(gòu)為紅黑樹
注意：
TreeSet 類位于 java.util 包中，使用前需要引入它
文檔信息：
3.4 關(guān)于 HashSet 的介紹
簡單介紹：
- HashSet 實現(xiàn)了 Set 接口，底層由
HashMap實現(xiàn)，是一個哈希表結(jié)構(gòu) - 新增元素時，新增的元素，相當于 HashMap 的 key，value 則默認為一個固定的 Object
注意：
HashSet 類位于 java.util 包中，使用前需要引入它
文檔信息：
3.5 TreeSet 和 HashSet 的區(qū)別
3.6 Set 使用示例代碼
注意：Set 是一個接口類，故不能直接實例化對象，以下以 HashSet 作為實現(xiàn)類為例
示例一： 創(chuàng)建一個 Set 實例
Set<Integer> set=new HashSet<>();
示例二： 添加元素（重復元素無法添加成功）
set.add(1); set.add(2); set.add(3); set.add(4); set.add(5); System.out.println(set); // 結(jié)果為：[1, 2, 3, 4, 5]
示例三： 判斷 1 是否在集合中
System.out.println(set.contains(1)); // 結(jié)果為：true
示例四： 刪除集合中的元素
System.out.println(set.remove(3)); // 結(jié)果為：true
示例五： 返回 set 中集合的個數(shù)
System.out.println(set.size()); // 結(jié)果為：4
示例六： 檢測 set 是否為空
System.out.println(set.isEmpty()); // 結(jié)果為：false
示例七： 返回迭代器，進行遍歷
Iterator<Integer> it=set.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
// 結(jié)果為：1 2 4 5
hashNext() 方法是判斷當前元素是否還有下一個元素，next() 是獲取當前元素，并且指向下一個元素
示例八： 清空集合
set.clear(); System.out.println(set); // 結(jié)果為：[]
4. 編程練習題
4.1 找出第一個重復數(shù)據(jù)
題目：
從一些數(shù)據(jù)中，打印出第一個重復數(shù)據(jù)
代碼：
public static void findNum(int[] array){
Set<Integer> set=new HashSet<>();
for(int i=0;i<array.length;i++){
if(set.contains(array[i])){
System.out.println(array[i]);
break;
}
set.add(array[i]);
}
}
4.2 去除重復數(shù)據(jù)
題目：
去除一些數(shù)據(jù)當中重復的數(shù)據(jù)
代碼：
public static int[] removeSample(int[] array){
Set<Integer> set=new HashSet<>();
for(int i=0;i<array.length;i++){
set.add(array[i]);
}
Object[] arr=set.toArray();
return array;
}
4.3 統(tǒng)計重復數(shù)據(jù)的出現(xiàn)次數(shù)
題目：
統(tǒng)計重復的數(shù)據(jù)出現(xiàn)的次數(shù)
代碼：
public static Map count(int[] array){
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<array.length;i++){
if(map.containsKey(array[i])){
int val=map.get(array[i]);
map.remove(array[i]);
map.put(array[i],val+1);
}else {
map.put(array[i], 1);
}
}
return map;
}
4.4 只出現(xiàn)一次的數(shù)字
題目（OJ 鏈接）：
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素
代碼1： 異或法
public int singleNumber(int[] nums) {
int sum=0;
for(int i=0;i<nums.length;i++){
sum=sum^nums[i];
}
return sum;
}
代碼2： 使用 HashSet
public int singleNumber(int[] nums) {
Set<Integer> set=new HashSet<>();
for(int val: nums){
if(set.contains(val)){
set.remove(val);
}else{
set.add(val);
}
}
for(int val: nums){
if(set.contains(val)){
return val;
}
}
return -1;
}
4.5 復制帶隨機指針的鏈表
題目（OJ 鏈接）：
給你一個長度為 n 的鏈表，每個節(jié)點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。
代碼：
public static 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){
Node node=map.get(cur);
node.next=map.get(cur.next);
node.random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
4.6 寶石與石頭
題目（OJ 鏈接）：
給你一個字符串 jewels 代表石頭中寶石的類型，另有一個字符串 stones 代表你擁有的石頭。 stones 中每個字符代表了一種你擁有的石頭的類型，你想知道你擁有的石頭中有多少是寶石。
字母區(qū)分大小寫，因此 “a” 和 “A” 是不同類型的石頭。
代碼：
public int numJewelsInStones(String jewels, String stones) {
Set<Character> set=new HashSet<>();
for(int i=0;i<jewels.length();i++){
set.add(jewels.charAt(i));
}
int count=0;
for(int i=0;i<stones.length();i++){
if(set.contains(stones.charAt(i))){
count++;
}
}
return count;
}
4.7 舊鍵盤
題目（OJ 鏈接）：
舊鍵盤上壞了幾個鍵，于是在敲一段文字的時候，對應(yīng)的字符就不會出現(xiàn)。現(xiàn)在給出應(yīng)該輸入的一段文字、以及實際被輸入的文字，請你列出
肯定壞掉的那些鍵。
代碼：
import java.util.*;
public class Main{
public static void main(String[] args){
Set<Character> set=new HashSet<>();
List<Character> list=new ArrayList<>();
Scanner scanner=new Scanner(System.in);
String str1=scanner.next();
String str2=scanner.next();
char[] s1=str1.toUpperCase().toCharArray();
char[] s2=str2.toUpperCase().toCharArray();
for(int i=0;i<s2.length;i++){
set.add(s2[i]);
}
for(int i=0;i<s1.length;i++){
if(!set.contains(s1[i])){
set.add(s1[i]);
System.out.print(s1[i]);
}
}
}
}
4.8 前 K 個高頻單詞
題目（OJ 鏈接）：
給一非空的單詞列表，返回前 k 個出現(xiàn)次數(shù)最多的單詞。返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率，按字母順序排序。
代碼：
public List<String> topKFrequent(String[] words, int k) {
Map<String,Integer> map=new HashMap<>();
for(String s: words){
if(map.containsKey(s)){
map.put(s,map.get(s)+1);
}else{
map.put(s,1);
}
}
PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
@Override
public int compare(Map.Entry<String,Integer> s1, Map.Entry<String,Integer> s2){
if(s1.getValue().compareTo(s2.getValue())==0){
return s2.getKey().compareTo(s1.getKey());
}
return s1.getValue()-s2.getValue();
}
});
for(Map.Entry<String,Integer> entry: map.entrySet()){
if(minHeap.size()<k){
minHeap.add(entry);
}else{
if(entry.getValue().compareTo(minHeap.peek().getValue())>0){
minHeap.poll();
minHeap.offer(entry);
}else if(entry.getValue().compareTo(minHeap.peek().getValue())==0){
if(entry.getKey().compareTo(minHeap.peek().getKey())<0){
minHeap.poll();
minHeap.offer(entry);
}
}
}
}
List<String> list=new ArrayList<>();
for(int i=0;i<k;i++){
Map.Entry<String,Integer> top=minHeap.poll();
list.add(top.getKey());
}
Collections.reverse(list);
return list;
}
5. 哈希表
5.1 概念
簡單介紹：
哈希表（也叫做散列表），是根據(jù)關(guān)鍵碼（Key Value）而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。它通過把關(guān)鍵碼映射到表中的一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做哈希函數(shù)（也叫做散列函數(shù)），存放記錄的數(shù)組叫做哈希表（也叫散列表）
在之前講解的數(shù)據(jù)結(jié)構(gòu)中，元素關(guān)鍵碼及其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個元素時，必須要經(jīng)過關(guān)鍵碼的多次比較，搜索的效率取決于搜索過程中元素的比較次數(shù)。例如：
- 順序查找的時間復雜度為：O(N)
- 二分查找的時間復雜度為：O(log(N))
我們希望有一種理想的搜索方法，它可以不經(jīng)過任何比較，能直接從表中得到要搜索的元素。因此就有了哈希表，它的原理就是：通過某種函數(shù)使元素的存儲位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，例如：
插入元素：
根據(jù)待插入元素的關(guān)鍵碼，以某個函數(shù)計算出該元素的存儲位置，并按此位置進行存放
搜索元素：
用該函數(shù)對元素的關(guān)鍵碼進行計算，把求得的函數(shù)值當作元素的存儲位置，在此結(jié)構(gòu)中按此位置取元素與要搜索的元素進行比較，若關(guān)鍵碼相等，則搜索成功
上述的方法就叫做哈希方法（也叫散列方法），其中哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)（也叫做散列函數(shù)），構(gòu)造出來的結(jié)構(gòu)稱為哈希表（也叫散列表）
示例： 當我們將哈希函數(shù)設(shè)置為：hash(key) = key % capacity 時，我們往一個數(shù)組中存放以下幾個元素，存放形式如下
但是使用哈希方法會出現(xiàn)一個問題：哈希沖突
5.2 哈希沖突——概念
簡單介紹：
哈希沖突（也叫做哈希碰撞），是指對于兩個數(shù)據(jù)元素的關(guān)鍵字 ki 和 kj (i != j)，雖然 ki != kj，但是存在：Hash(ki) == Hash(kj)，即不同關(guān)鍵字通過相同哈希函數(shù)，可能會計算出相同的哈希地址
示例： 當我們將哈希函數(shù)設(shè)置為：hash(key) = key % capacity 時，元素 3 和 13 通過該哈希函數(shù)計算出的存放位置是一樣的
由于哈希表底層數(shù)組的容量往往是小于實際要存儲的關(guān)鍵字的數(shù)量的，這就導致，哈希沖突的發(fā)生是必然的。并且哈希沖突不能根本上消除，為此我們就要
- 在哈希沖突發(fā)生前：盡量避免
- 在哈希沖突發(fā)生后：重點解決
5.3 哈希沖突——避免
5.3.1 哈希函數(shù)設(shè)計
引起哈希沖突的一個原因可能是：哈希函數(shù)設(shè)計不合理
哈希函數(shù)的設(shè)計原則：
- 哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有m個地址時，其值域必須在0到 m-1 之間
- 哈希函數(shù)計算出來的地址能夠均勻分布在整個空間中
- 哈希函數(shù)應(yīng)該比較簡單
常見哈希函數(shù)：
直接定制法（常用）
- 思路：取關(guān)鍵字的某個線性函數(shù)為散列地址：Hash(Key) = A * Key + B
- 優(yōu)點：簡單、均勻
- 缺點：需要事先知道關(guān)鍵字的分布情況
- 使用場景：適合查找比較小且連續(xù)的情況
除留余數(shù)法（常用）
- 思路：設(shè)散列表中允許的地址數(shù)為m，取一個不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：Hash(Key) = Key % p (p<=m) 將關(guān)鍵碼轉(zhuǎn)換成哈希地址
平方取中法（了解）
- 思路：假設(shè)關(guān)鍵字為1234，對它去平方就是1522756，抽取中間的3位數(shù)227作為哈希地址。再比如關(guān)鍵字為3241，它的平方就是18671041，抽取中間的3位671作為哈希地址
- 使用場景：不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況
折疊法（了解）
- 思路：將關(guān)鍵字從左到右分割成位數(shù)相等的及部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址
- 使用場景：事先不需要知道關(guān)鍵字的分布，且關(guān)鍵字位數(shù)比較多的情況
隨機數(shù)法（了解）
- 思路：選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址，即 Hash(Key) = random(Key) (random 為隨機函數(shù))
- 使用場景：通常應(yīng)用于關(guān)鍵字長度不等時的情況
數(shù)學分析法（了解）
- 思路：設(shè)有n個d位數(shù)，每一位可能有r種不同的符號，這r種不同的符號在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，每種符號出現(xiàn)的機會均等，在某些位上分布不均勻的只有某幾種符號。可跟據(jù)散列表的大小，選擇其中各種符號分布均勻的若干位作為散列地址
- 使用場景：適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均與的情況
5.3.2 負載因子調(diào)節(jié)
負載因子定義：
散列表的載荷因子定義為：α = 填入表中的元素個數(shù) / 散列表的長度
α 是散列表裝滿程度的標志因子。由于表長是定值，α 與填入表中的元素個數(shù)成正比，所以 α 越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性就越大；反之 α 越小，表名填入表中的元素越少，產(chǎn)生沖突的可能性就越小
一些采用開放定址法的 hash 庫，如 Java 的系統(tǒng)庫限制了載荷因子為0.75，超過此值將 resize 散列表
負載因子和沖突率的關(guān)系粗略演示圖：
通過演示圖我們可以很直觀的了解，當沖突率越大時，我們需要通過降低負載因子來變相降低沖突率。而填入表中的元素個數(shù)已成定局，我們不能夠修改，因此需要調(diào)整哈希表中的數(shù)組大小，即調(diào)整散列表長度
5.4 哈希沖突——解決
解決哈希沖突兩種常見的方法：
- 閉散列
- 開散列
5.4.1 閉散列
簡單介紹：
閉散列：也叫開放定址法，當發(fā)生哈希沖突時，如果哈希表未被裝滿，說明哈希表中必然還有空位置，那么可以把 Key 存放到?jīng)_突位置的下一個空位置中去
尋找沖突位置下一個空位置的方法：
線性探測
- 方法：從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止，如果后面的位置都滿了，則會從頭開始尋找
- 缺點：會將所有沖突元素都堆積在一起
二次探測
- 方法：Hi = (H0 + i2) % m 或者 Hi = (H0 - i2) % m（i = 1,2,3…），H0 是通過散列函數(shù) Hash(x) 對元素的關(guān)鍵碼 key 進行計算得到的位置，m是表的大小，Hi 是尋找到的空位置
- 缺點：空間利用率較低，這也是哈希表的缺陷
5.4.2 開散列/哈希桶
簡單介紹：
開散列：也叫做鏈地址法或開鏈法或哈希桶，首先對關(guān)鍵碼集合用散列函數(shù)計算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶的元素通過一個單鏈表連接起來，各個鏈表的頭節(jié)點存儲在哈希表中
補充：
HashMap 的底層就是一個開散列
可以認為開散列是把一個在大集合中的搜索問題轉(zhuǎn)化為在小集合中做搜索
由于會盡量避免沖突，所以沖突率其實會有保障，因此當在單鏈表中做搜索時，其實很快，時間復雜度接近：O(1)
但是當沖突很嚴重時，那么在單鏈表這個小集合中做搜索其實性能就會大大降低，因此單鏈表就不太適合做小集合的結(jié)構(gòu)
沖突嚴重時的解決辦法：
- 將哈希桶的結(jié)構(gòu)替換成另一個哈希表
- 將哈希桶的結(jié)構(gòu)替換成搜索樹
5.5 相關(guān)習題
補充： Hash表的平均查找長度（ASL）包括查找成功時的平均查找長度和查找失敗時的平均查找長度
- 查找成功的平均查找長度=表中每個元素查找成功時的比較次數(shù)之和/表中元素個數(shù)
- 查找不成功的平均查找長度=該位置如果查找一個元素失敗的次數(shù)/表的長度
題目：
設(shè)哈希表長度為11，哈希函數(shù) H(K) = (K的第一個字母在字母表中的序號) % 11，若輸入順序為（D、BA、TN、M、CI、I、K、X、TA），采用閉散列處理沖突方法為線性探測，要求構(gòu)造哈希表，在等概率的情況下查找成功的平均查找長度為( )，查找不成功的平均查找長度為( )
5.6 性能分析
雖然哈希表一直在和沖突做斗爭，但在實際使用過程中，哈希表的沖突率是不高的，沖突個數(shù)是可控的，也就是每個桶中的鏈表的長度是一個常數(shù)。
因此，通常意義下我們認為哈希表的插入、刪除、查找時間復雜度為：O(1)
6. 手動實現(xiàn) HashMap（提及 hashCode 和 equals 的作用）
- HashMap 底層是：數(shù)組+單鏈表
- 我們可以先定義一個最基礎(chǔ)的哈希表，讓他可以實現(xiàn)整形的存值、取值等（哈希函數(shù)設(shè)定為：Hash(Key) = Key % capacity)
class HashBuck{
static class Node{
public int key;
public int value;
public Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public Node[] array;
public int usedSize;
public HashBuck(){
this.array=new Node[8];
}
// 獲取 key 對應(yīng)的 value
public int get(int key){
int index=key%this.array.length;
Node cur=this.array[index];
while(cur!=null){
if(cur.key==key){
return cur.value;
}
cur=cur.next;
}
return -1; // 這里先用 -1 返回，也可以拋異常
}
// 新增元素
public void put(int key, int val){
int index=key%this.array.length;
Node cur=this.array[index];
Node node=new Node(key,val);
if(cur==null){
this.array[index]=node;
}else{
while(cur.next!=null){
if(cur.key==key){
cur.value=val;
break;
}
cur=cur.next;
}
cur.next=node;
}
this.usedSize++;
if(loadFactor()>=0.75){
resize();
}
}
// 計算負載因子
public double loadFactor(){
return this.usedSize*1.0/this.array.length;
}
// 擴容后，重新構(gòu)造哈希
public void resize(){
Node[] oldArray=this.array;
this.array=new Node[2*oldArray.length];
this.usedSize=0;
for(int i=0;i<oldArray.length;i++){
Node cur=oldArray[i];
while(cur!=null){
put(cur.key,cur.value);
cur=cur.next;
}
}
}
}
當我們實現(xiàn)了對整形的部分哈希表的實現(xiàn)后，如果要實現(xiàn)其它類型是有問題的，因為我們設(shè)計的哈希函數(shù)為：Hash(Key) = Key % capacity，而其它類型都不能取模，因此我們需要能夠?qū)?Key 進行數(shù)字轉(zhuǎn)換的方法。而在 Object 類有一個 hashCode() 方法，它能將傳過來的對象，轉(zhuǎn)換成一個合法的數(shù)字，以此來找到合適的位置，因此使用它就能解決我們上述的麻煩。除此之外，上述代碼中的一些==需要修改為 equals() 方法，因為 equals 它能夠判斷傳入的對象的實例是否相等
通過上面一部分的分析，最終可以得到如下代碼：
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=new Node[8];
public int usedSize;
public void put(K key,V val){
int hash=key.hashCode();
int index=hash%this.array.length;
Node<K,V> cur=this.array[index];
Node<K,V> node=new Node<K,V>(key,val);
if(cur==null){
this.array[index]=node;
}else{
while(cur.next!=null){
if(cur.key.equals(key)){
cur.val=val;
break;
}
cur=cur.next;
}
cur.next=node;
}
this.usedSize++;
if(loadFactor()>=0.75){
resize();
}
}
public V get(K key){
int hash=key.hashCode();
int index=hash%this.array.length;
Node<K,V> cur=this.array[index];
while(cur!=null){
if(cur.key.equals(key)){
return cur.val;
}
cur=cur.next;
}
return null;
}
// 計算負載因子
public double loadFactor(){
return this.usedSize*1.0/this.array.length;
}
// 重新哈希
public void resize(){
Node<K,V>[] oldArray=this.array;
this.array=(Node<K, V>[]) new Node[2*oldArray.length];
this.usedSize=0;
for(int i=0;i<oldArray.length;i++){
Node<K,V> cur=oldArray[i];
while(cur!=null){
put(cur.key,cur.val);
cur=cur.next;
}
}
}
}
7. hashCode 和 equals 的關(guān)系
如果 hashCode 一樣，那么 equals 會一樣嗎？
- equals 不一定一樣，因為 hashCode 是確定在數(shù)組中存儲的位置是不是一樣，但不能確定在哈希桶中，存放的 key 是不是一樣，即不能確定 equals 的結(jié)果是不是一樣
如果 equals 一樣，那么 hashCode 一樣嗎？
- hashCode 一定一樣，因為 equals 一樣了，那么在數(shù)組中存儲的位置是肯定一樣的
8. 哈希和 Java 類集的關(guān)系
HashMap和HashSet即 Java 中利用哈希表實現(xiàn)的 Map 和 Set- Java 中會使用哈希桶解決哈希沖突
- Java 會在沖突鏈表長度大于一定閾值后，將鏈表轉(zhuǎn)變?yōu)樗阉鳂洌t黑樹）。具體數(shù)值為當前鏈表的長度超過8且當前桶的個數(shù)大于等于64時，就會將當前長度超過8的鏈表變?yōu)榧t黑樹
- Java 中計算哈希值實際上是調(diào)用 Object 類的 hashCode 方法，進行 Key 的相等性比較是調(diào)用的 equals 方法
- 自定義類如果需要作為 HashMap 的 Key 或者 HashSet 的值，必須重寫
hashCode和equals方法
9. HashMap 部分源碼解讀
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 當哈希表的大小為 0 時，進行 resize 調(diào)整
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ((n - 1) & hash) 其實等價于 (n % 數(shù)組長度) 但是前提條件是，n是2的次冪
// 如果為 null 就是第一次插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果不為 null，就進行尾插法
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 當單鏈表的長度大于8時，轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize 方法的實現(xiàn)（以2倍的方式進行擴容）
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
10. HashMap 常考問題
問題一：如果 new HashMap(19)，那么 bucket 數(shù)組有多大？
32，原因在第9大節(jié)的構(gòu)造方法四中
問題二：HashMap 什么時候開辟 bucket 數(shù)組占用內(nèi)存？
第一次 put 的時候
問題三：HashMap 何時擴容？
當填入的元素/容量大于負載因子的時候，進行擴容，jdk1.8 負載因子默認為0.75
問題四：當兩個對象的 hashCode 相同時會發(fā)生什么？
會發(fā)生哈希沖突
問題五：如果兩個鍵的 hashCode 相同，你如何獲取值對象？
遍歷當前位置的鏈表，通過 equals 返回和要查詢的 Key 值一樣的 Key 的 Value
問題六：你了解重新調(diào)整 HashMap 大小存在什么問題嗎？
重新調(diào)整大小一定要進行重新哈希
到此這篇關(guān)于Java 集合框架掌握 Map 和 Set 的使用(內(nèi)含哈希表源碼解讀及面試常考題)的文章就介紹到這了,更多相關(guān)Java 集合框架掌握 Map 和 Set 的使用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java?Lombok實現(xiàn)手機號碼校驗的示例代碼
手機號碼校驗通常是系統(tǒng)開發(fā)中最基礎(chǔ)的功能之一，本文主要介紹了Java?Lombok實現(xiàn)手機號碼校驗的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-07-07
多線程編程可以說是在大部分平臺和應(yīng)用上都需要實現(xiàn)的一個基本需求,下面這篇文章主要給大家介紹了關(guān)于JAVA多線程之JDK中各種鎖的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-07-07
Netflix Eureka 是由 Netflix 開源的一款基于 REST 的服務(wù)發(fā)現(xiàn)組件，包括 Eureka Server 及 Eureka Client。這篇文章主要介紹了Spring Cloud 系列之注冊中心 Eureka,需要的朋友可以參考下2020-11-11
在本篇文章里小編給大家整理的是關(guān)于SpringBoot打印啟動時異常堆棧信息，有需要的朋友們可以學習下。2019-11-11
在日常開發(fā)中，如果要操作數(shù)據(jù)庫的話，或多或少都會遇到批量數(shù)據(jù)的處理，本文主要介紹了Mybatis批量插入的三種實現(xiàn)方法，感興趣的可以了解一下2023-10-10
字符串廣泛應(yīng)用在Java編程中，在Java中字符串屬于對象，Java 提供了String類來創(chuàng)建和操作字符串，今天給大家介紹Java基礎(chǔ)入門語法--String類的相關(guān)知識，感興趣的朋友一起看看吧2021-06-06
本篇文章主要介紹了詳述 IntelliJ IDEA 插件的安裝及使用方法(圖解)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11
spring的xml文件打開沒有namespace等操作選項的解決方案
這篇文章主要介紹了spring的xml文件打開沒有namespace等操作選項的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了如何區(qū)分JAVA中的throws和throw，文中講解十分詳細，代碼幫助大家更好的理解和學習，感興趣的朋友可以了解下2020-06-06
Java多態(tài)和實現(xiàn)接口的類的對象賦值給接口引用的方法(推薦)
下面小編就為大家?guī)硪黄狫ava多態(tài)和實現(xiàn)接口的類的對象賦值給接口引用的方法(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-02-02