Java?集合框架掌握?Map?和?Set?的使用(內(nèi)含哈希表源碼解讀及面試?？碱})
1. 搜索
1.1 場(chǎng)景引入
在學(xué)習(xí)編程時(shí)，我們常見(jiàn)的搜索方式有：
- 直接遍歷：時(shí)間復(fù)雜度為 O(N)，元素如果比較多效率會(huì)非常慢
- 二分查找：時(shí)間復(fù)雜度為 O(logN)，搜索前必須要求序列有序
但是上述排序比較適合靜態(tài)類(lèi)型的查找，即一般不會(huì)對(duì)區(qū)間進(jìn)行插入和刪除操作。
而現(xiàn)實(shí)中的查找如：
- 根據(jù)姓名查詢(xún)考試成績(jī)
- 通訊錄（根據(jù)姓名查詢(xún)聯(lián)系方式）
可能在查找時(shí)需要進(jìn)行一些插入和刪除操作，即動(dòng)態(tài)查找。因此上述排序的方式就不太適合。
1.2 模型
一般會(huì)把要搜索的數(shù)據(jù)稱(chēng)為關(guān)鍵字（Key），和關(guān)鍵字對(duì)應(yīng)的稱(chēng)為值（Value），這兩者又能組合成為 Key-Value 的鍵值對(duì)。
因此動(dòng)態(tài)查找的模型有下面兩種：
純 Key 模型： Set 的存儲(chǔ)模式，比如：
- 有一個(gè)英文詞典，快速查找一個(gè)單詞是否在詞典中
- 快速查找某個(gè)名字在不在通訊錄中
Key-Value 模型： Map 的存儲(chǔ)模式，比如：
- 統(tǒng)計(jì)文件中每個(gè)單詞出現(xiàn)的次數(shù)，統(tǒng)計(jì)結(jié)果是每個(gè)單詞都有與其對(duì)應(yīng)的次數(shù)：<單詞， 單詞出現(xiàn)的次數(shù)>
- 梁山好漢的江湖綽號(hào)，每個(gè)好漢都有自己的江湖綽號(hào)：<好漢， 江湖綽號(hào)>
2. Map
2.1 關(guān)于 Map 的介紹
簡(jiǎn)單介紹：
Map 是一個(gè)接口類(lèi)，沒(méi)有繼承自 Collection。該類(lèi)中存儲(chǔ)的是 <K, V> 結(jié)構(gòu)的鍵值對(duì)，并且 K 一定是唯一的，不能重復(fù)
注意：
- Map 接口位于 java.util 包中，使用前需要引入它
- Map 是一個(gè)接口類(lèi)，故不能直接實(shí)例化對(duì)象。如果要實(shí)例化對(duì)象只能實(shí)例化其實(shí)現(xiàn)類(lèi) TreeMap 或 HashMap
- Map 中存放的鍵值對(duì)的 Key 是唯一的，Value 是可以重復(fù)的
文檔信息：
2.2 關(guān)于 Map.Entry<K, V> 的介紹
簡(jiǎn)單介紹：
Map.Entry<K, V> 是 Map 內(nèi)部實(shí)現(xiàn)的用來(lái)存放 <Key, Value> 鍵值對(duì)映射關(guān)系的內(nèi)部類(lèi)。該內(nèi)部類(lèi)中主要提供了 <Key, Value> 的獲取，Value 的設(shè)置以及 Key 的比較方式
常用方法：
| 方法 | 說(shuō)明 |
|---|---|
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 將鍵值對(duì)中的 value 替換為指定的 value |
注意：
Map.Entry<K, V> 并沒(méi)有提供設(shè)置 Key 的方法
文檔信息：
2.3 Map 的常用方法說(shuō)明
注意：
- 往 Map 中存儲(chǔ)數(shù)據(jù)時(shí)，會(huì)先根據(jù) key 做出一系列的運(yùn)算，再存儲(chǔ)到 Map 中
- 如果 key 一樣，那么新插入的 key 的 value，會(huì)覆蓋原來(lái) key 的 value
- 在 Map 中插入鍵值對(duì)時(shí)，key 和 value 都可以為 null
- Map 中的 key 可以全部分離出來(lái)，存儲(chǔ)到 Set 中來(lái)進(jìn)行訪問(wèn)（因?yàn)?key 是不能重復(fù)的）
- Map 中的 value 可以全部分離出來(lái)，存儲(chǔ)到
Collection的任何一個(gè)子集中（注意 value 可能有重復(fù)） - Map 中的鍵值對(duì)的 key 不能直接修改，value 可以修改。如果要修改 key，只能先將 key 刪掉，然后再進(jìn)行重新插入（或者直接覆蓋）
2.4 關(guān)于 HashMap 的介紹
簡(jiǎn)單介紹：
HashMap是一個(gè)散列表，它存儲(chǔ)的內(nèi)容是鍵值對(duì)（key-value）映射- HashMap 實(shí)現(xiàn)了 Map 接口，根據(jù)鍵的
HashCode值存儲(chǔ)數(shù)據(jù)，具有很快的訪問(wèn)速度，最多允許一條記錄的鍵為 null，不支持線程同步 - HashMap 是無(wú)序的，即不會(huì)記錄插入的順序
- HashMap 繼承于 AbstractMap，實(shí)現(xiàn)了 Map、Cloneable、
java.io.Serializable接口
注意：
HashMap 類(lèi)位于 java.util 包中，使用前需要引入它
文檔信息：
2.5 關(guān)于 TreeMap 的介紹
簡(jiǎn)單介紹：
- TreeMap 是一個(gè)能比較元素大小的 Map 集合，會(huì)對(duì)傳入的 key 進(jìn)行大小排序。其中可以使用元素的自然順序，也可以使用集合中自定義的比較器來(lái)進(jìn)行排序。
- 不同于 HashMap 的哈希映射，TreeMap 底層實(shí)現(xiàn)了樹(shù)形結(jié)構(gòu)，即紅黑樹(shù)的結(jié)構(gòu)。
注意：
TreeMap 類(lèi)位于 java.util 包中，使用前需要引入它
文檔信息：
2.6 HashMap 和 TreeMap 的區(qū)別
2.7 Map 使用示例代碼
注意：Map 是一個(gè)接口類(lèi)，故不能直接實(shí)例化對(duì)象，以下以 HashMap 作為實(shí)現(xiàn)類(lèi)為例
示例一： 創(chuàng)建一個(gè) Map 實(shí)例
Map<String,String> map=new HashMap<>();
示例二： 插入 key 及其對(duì)應(yīng)值為 value
map.put("惠城","法師");
map.put("曉","刺客");
map.put("喵班長(zhǎng)","盜劍客");
System.out.println(map);
// 結(jié)果為：{惠城=法師, 曉=刺客, 喵班長(zhǎng)=盜劍客}
示例三： 返回 key 的對(duì)應(yīng) value
String str1=map.get("曉");
System.out.println(str1);
// 結(jié)果為：刺客
示例四： 返回 key 對(duì)應(yīng)的 value，若 key 不存在，則返回默認(rèn)值 defaultValue
String str2=map.getOrDefault("彌惠","冒險(xiǎn)者");
System.out.println(str2);
// 結(jié)果為：冒險(xiǎn)者
示例五： 刪除 key 對(duì)應(yīng)的映射關(guān)系
String str3=map.remove("喵班長(zhǎng)");
System.out.println(str3);
System.out.println(map);
// 結(jié)果為：盜劍客 和 {惠城=法師, 曉=刺客}
示例六： 除了上述直接打印 map，也可以通過(guò) Set<Map.Entry<K, V>> entrySet() 這個(gè)方法進(jìn)行遍歷打印
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=喵班長(zhǎng) Value=盜劍客
*/
示例七： 判斷是否包含 key
System.out.println(map.containsKey("惠城"));
// 結(jié)果為：true
3. Set
3.1 關(guān)于 Set 的介紹
簡(jiǎn)單介紹：
Set 是一個(gè)繼承于 Collection 的接口，是一個(gè)不允許出現(xiàn)重復(fù)元素，并且無(wú)序的集合，主要有 HashSet 和 TreeSet 兩大實(shí)現(xiàn)類(lèi)。
注意：
Set 接口位于 java.util 包中，使用前需要引入它
文檔信息：
3.1 Set 的常用方法說(shuō)明
注意：
Set 中只繼承了 Key，并且要求 Key 唯一
Set 的底層是使用 Map 來(lái)實(shí)現(xiàn)的，其使用 Key 與 Object 的一個(gè)默認(rèn)對(duì)象作為鍵值對(duì)插入插入到 Map 中
Set 的最大功能就是對(duì)集合中的元素進(jìn)行去重
實(shí)現(xiàn) Set 接口的常用類(lèi)有 TreeSet 和 HashSet，還有一個(gè) LinkedHashSet，LinkedHashSet 是在 HashSet 的基礎(chǔ)上維護(hù)了一個(gè)雙向鏈表來(lái)記錄元素的插入次序
Set 中的 Key 不能修改，如果修改，要先將原來(lái)的刪除
Set 中可以插入 null
3.3 關(guān)于 TreeSet 的介紹
簡(jiǎn)單介紹：
TreeSet 實(shí)現(xiàn)類(lèi) Set 接口，基于 Map 實(shí)現(xiàn)，其底層結(jié)構(gòu)為紅黑樹(shù)
注意：
TreeSet 類(lèi)位于 java.util 包中，使用前需要引入它
文檔信息：
3.4 關(guān)于 HashSet 的介紹
簡(jiǎn)單介紹：
- HashSet 實(shí)現(xiàn)了 Set 接口，底層由
HashMap實(shí)現(xiàn)，是一個(gè)哈希表結(jié)構(gòu) - 新增元素時(shí)，新增的元素，相當(dāng)于 HashMap 的 key，value 則默認(rèn)為一個(gè)固定的 Object
注意：
HashSet 類(lèi)位于 java.util 包中，使用前需要引入它
文檔信息：
3.5 TreeSet 和 HashSet 的區(qū)別
3.6 Set 使用示例代碼
注意：Set 是一個(gè)接口類(lèi)，故不能直接實(shí)例化對(duì)象，以下以 HashSet 作為實(shí)現(xiàn)類(lèi)為例
示例一： 創(chuàng)建一個(gè) Set 實(shí)例
Set<Integer> set=new HashSet<>();
示例二： 添加元素（重復(fù)元素?zé)o法添加成功）
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 中集合的個(gè)數(shù)
System.out.println(set.size()); // 結(jié)果為：4
示例六： 檢測(cè) set 是否為空
System.out.println(set.isEmpty()); // 結(jié)果為：false
示例七： 返回迭代器，進(jìn)行遍歷
Iterator<Integer> it=set.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
// 結(jié)果為：1 2 4 5
hashNext() 方法是判斷當(dāng)前元素是否還有下一個(gè)元素，next() 是獲取當(dāng)前元素，并且指向下一個(gè)元素
示例八： 清空集合
set.clear(); System.out.println(set); // 結(jié)果為：[]
4. 編程練習(xí)題
4.1 找出第一個(gè)重復(fù)數(shù)據(jù)
題目：
從一些數(shù)據(jù)中，打印出第一個(gè)重復(fù)數(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 去除重復(fù)數(shù)據(jù)
題目：
去除一些數(shù)據(jù)當(dāng)中重復(fù)的數(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)計(jì)重復(fù)數(shù)據(jù)的出現(xiàn)次數(shù)
題目：
統(tǒng)計(jì)重復(fù)的數(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 鏈接）：
給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(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 復(fù)制帶隨機(jī)指針的鏈表
題目（OJ 鏈接）：
給你一個(gè)長(zhǎng)度為 n 的鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針 random ，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。
代碼：
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 鏈接）：
給你一個(gè)字符串 jewels 代表石頭中寶石的類(lèi)型，另有一個(gè)字符串 stones 代表你擁有的石頭。 stones 中每個(gè)字符代表了一種你擁有的石頭的類(lèi)型，你想知道你擁有的石頭中有多少是寶石。
字母區(qū)分大小寫(xiě)，因此 “a” 和 “A” 是不同類(lèi)型的石頭。
代碼：
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 舊鍵盤(pán)
題目（OJ 鏈接）：
舊鍵盤(pán)上壞了幾個(gè)鍵，于是在敲一段文字的時(shí)候，對(duì)應(yīng)的字符就不會(huì)出現(xiàn)。現(xiàn)在給出應(yīng)該輸入的一段文字、以及實(shí)際被輸入的文字，請(qǐ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 個(gè)高頻單詞
題目（OJ 鏈接）：
給一非空的單詞列表，返回前 k 個(gè)出現(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 概念
簡(jiǎn)單介紹：
哈希表（也叫做散列表），是根據(jù)關(guān)鍵碼（Key Value）而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。它通過(guò)把關(guān)鍵碼映射到表中的一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做哈希函數(shù)（也叫做散列函數(shù)），存放記錄的數(shù)組叫做哈希表（也叫散列表）
在之前講解的數(shù)據(jù)結(jié)構(gòu)中，元素關(guān)鍵碼及其存儲(chǔ)位置之間沒(méi)有對(duì)應(yīng)的關(guān)系，因此在查找一個(gè)元素時(shí)，必須要經(jīng)過(guò)關(guān)鍵碼的多次比較，搜索的效率取決于搜索過(guò)程中元素的比較次數(shù)。例如：
- 順序查找的時(shí)間復(fù)雜度為：O(N)
- 二分查找的時(shí)間復(fù)雜度為：O(log(N))
我們希望有一種理想的搜索方法，它可以不經(jīng)過(guò)任何比較，能直接從表中得到要搜索的元素。因此就有了哈希表，它的原理就是：通過(guò)某種函數(shù)使元素的存儲(chǔ)位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，例如：
插入元素：
根據(jù)待插入元素的關(guān)鍵碼，以某個(gè)函數(shù)計(jì)算出該元素的存儲(chǔ)位置，并按此位置進(jìn)行存放
搜索元素：
用該函數(shù)對(duì)元素的關(guān)鍵碼進(jìn)行計(jì)算，把求得的函數(shù)值當(dāng)作元素的存儲(chǔ)位置，在此結(jié)構(gòu)中按此位置取元素與要搜索的元素進(jìn)行比較，若關(guān)鍵碼相等，則搜索成功
上述的方法就叫做哈希方法（也叫散列方法），其中哈希方法中使用的轉(zhuǎn)換函數(shù)稱(chēng)為哈希函數(shù)（也叫做散列函數(shù)），構(gòu)造出來(lái)的結(jié)構(gòu)稱(chēng)為哈希表（也叫散列表）
示例： 當(dāng)我們將哈希函數(shù)設(shè)置為：hash(key) = key % capacity 時(shí)，我們往一個(gè)數(shù)組中存放以下幾個(gè)元素，存放形式如下
但是使用哈希方法會(huì)出現(xiàn)一個(gè)問(wèn)題：哈希沖突
5.2 哈希沖突——概念
簡(jiǎn)單介紹：
哈希沖突（也叫做哈希碰撞），是指對(duì)于兩個(gè)數(shù)據(jù)元素的關(guān)鍵字 ki 和 kj (i != j)，雖然 ki != kj，但是存在：Hash(ki) == Hash(kj)，即不同關(guān)鍵字通過(guò)相同哈希函數(shù)，可能會(huì)計(jì)算出相同的哈希地址
示例： 當(dāng)我們將哈希函數(shù)設(shè)置為：hash(key) = key % capacity 時(shí)，元素 3 和 13 通過(guò)該哈希函數(shù)計(jì)算出的存放位置是一樣的
由于哈希表底層數(shù)組的容量往往是小于實(shí)際要存儲(chǔ)的關(guān)鍵字的數(shù)量的，這就導(dǎo)致，哈希沖突的發(fā)生是必然的。并且哈希沖突不能根本上消除，為此我們就要
- 在哈希沖突發(fā)生前：盡量避免
- 在哈希沖突發(fā)生后：重點(diǎn)解決
5.3 哈希沖突——避免
5.3.1 哈希函數(shù)設(shè)計(jì)
引起哈希沖突的一個(gè)原因可能是：哈希函數(shù)設(shè)計(jì)不合理
哈希函數(shù)的設(shè)計(jì)原則：
- 哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，而如果散列表允許有m個(gè)地址時(shí)，其值域必須在0到 m-1 之間
- 哈希函數(shù)計(jì)算出來(lái)的地址能夠均勻分布在整個(gè)空間中
- 哈希函數(shù)應(yīng)該比較簡(jiǎn)單
常見(jiàn)哈希函數(shù)：
直接定制法（常用）
- 思路：取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址：Hash(Key) = A * Key + B
- 優(yōu)點(diǎn)：簡(jiǎn)單、均勻
- 缺點(diǎn)：需要事先知道關(guān)鍵字的分布情況
- 使用場(chǎng)景：適合查找比較小且連續(xù)的情況
除留余數(shù)法（常用）
- 思路：設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：Hash(Key) = Key % p (p<=m) 將關(guān)鍵碼轉(zhuǎn)換成哈希地址
平方取中法（了解）
- 思路：假設(shè)關(guān)鍵字為1234，對(duì)它去平方就是1522756，抽取中間的3位數(shù)227作為哈希地址。再比如關(guān)鍵字為3241，它的平方就是18671041，抽取中間的3位671作為哈希地址
- 使用場(chǎng)景：不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況
折疊法（了解）
- 思路：將關(guān)鍵字從左到右分割成位數(shù)相等的及部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按散列表表長(zhǎng)，取后幾位作為散列地址
- 使用場(chǎng)景：事先不需要知道關(guān)鍵字的分布，且關(guān)鍵字位數(shù)比較多的情況
隨機(jī)數(shù)法（了解）
- 思路：選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即 Hash(Key) = random(Key) (random 為隨機(jī)函數(shù))
- 使用場(chǎng)景：通常應(yīng)用于關(guān)鍵字長(zhǎng)度不等時(shí)的情況
數(shù)學(xué)分析法（了解）
- 思路：設(shè)有n個(gè)d位數(shù)，每一位可能有r種不同的符號(hào)，這r種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，每種符號(hào)出現(xiàn)的機(jī)會(huì)均等，在某些位上分布不均勻的只有某幾種符號(hào)?？筛鷵?jù)散列表的大小，選擇其中各種符號(hào)分布均勻的若干位作為散列地址
- 使用場(chǎng)景：適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均與的情況
5.3.2 負(fù)載因子調(diào)節(jié)
負(fù)載因子定義：
散列表的載荷因子定義為：α = 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度
α 是散列表裝滿(mǎn)程度的標(biāo)志因子。由于表長(zhǎng)是定值，α 與填入表中的元素個(gè)數(shù)成正比，所以 α 越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性就越大；反之 α 越小，表名填入表中的元素越少，產(chǎn)生沖突的可能性就越小
一些采用開(kāi)放定址法的 hash 庫(kù)，如 Java 的系統(tǒng)庫(kù)限制了載荷因子為0.75，超過(guò)此值將 resize 散列表
負(fù)載因子和沖突率的關(guān)系粗略演示圖：
通過(guò)演示圖我們可以很直觀的了解，當(dāng)沖突率越大時(shí)，我們需要通過(guò)降低負(fù)載因子來(lái)變相降低沖突率。而填入表中的元素個(gè)數(shù)已成定局，我們不能夠修改，因此需要調(diào)整哈希表中的數(shù)組大小，即調(diào)整散列表長(zhǎng)度
5.4 哈希沖突——解決
解決哈希沖突兩種常見(jiàn)的方法：
- 閉散列
- 開(kāi)散列
5.4.1 閉散列
簡(jiǎn)單介紹：
閉散列：也叫開(kāi)放定址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被裝滿(mǎn)，說(shuō)明哈希表中必然還有空位置，那么可以把 Key 存放到?jīng)_突位置的下一個(gè)空位置中去
尋找沖突位置下一個(gè)空位置的方法：
線性探測(cè)
- 方法：從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到尋找到下一個(gè)空位置為止，如果后面的位置都滿(mǎn)了，則會(huì)從頭開(kāi)始尋找
- 缺點(diǎn)：會(huì)將所有沖突元素都堆積在一起
二次探測(cè)
- 方法：Hi = (H0 + i2) % m 或者 Hi = (H0 - i2) % m（i = 1,2,3…），H0 是通過(guò)散列函數(shù) Hash(x) 對(duì)元素的關(guān)鍵碼 key 進(jìn)行計(jì)算得到的位置，m是表的大小，Hi 是尋找到的空位置
- 缺點(diǎn)：空間利用率較低，這也是哈希表的缺陷
5.4.2 開(kāi)散列/哈希桶
簡(jiǎn)單介紹：
開(kāi)散列：也叫做鏈地址法或開(kāi)鏈法或哈希桶，首先對(duì)關(guān)鍵碼集合用散列函數(shù)計(jì)算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個(gè)子集合稱(chēng)為一個(gè)桶，各個(gè)桶的元素通過(guò)一個(gè)單鏈表連接起來(lái)，各個(gè)鏈表的頭節(jié)點(diǎn)存儲(chǔ)在哈希表中
補(bǔ)充：
HashMap 的底層就是一個(gè)開(kāi)散列
可以認(rèn)為開(kāi)散列是把一個(gè)在大集合中的搜索問(wèn)題轉(zhuǎn)化為在小集合中做搜索
由于會(huì)盡量避免沖突，所以沖突率其實(shí)會(huì)有保障，因此當(dāng)在單鏈表中做搜索時(shí)，其實(shí)很快，時(shí)間復(fù)雜度接近：O(1)
但是當(dāng)沖突很?chē)?yán)重時(shí)，那么在單鏈表這個(gè)小集合中做搜索其實(shí)性能就會(huì)大大降低，因此單鏈表就不太適合做小集合的結(jié)構(gòu)
沖突嚴(yán)重時(shí)的解決辦法：
- 將哈希桶的結(jié)構(gòu)替換成另一個(gè)哈希表
- 將哈希桶的結(jié)構(gòu)替換成搜索樹(shù)
5.5 相關(guān)習(xí)題
補(bǔ)充： Hash表的平均查找長(zhǎng)度（ASL）包括查找成功時(shí)的平均查找長(zhǎng)度和查找失敗時(shí)的平均查找長(zhǎng)度
- 查找成功的平均查找長(zhǎng)度=表中每個(gè)元素查找成功時(shí)的比較次數(shù)之和/表中元素個(gè)數(shù)
- 查找不成功的平均查找長(zhǎng)度=該位置如果查找一個(gè)元素失敗的次數(shù)/表的長(zhǎng)度
題目：
設(shè)哈希表長(zhǎng)度為11，哈希函數(shù) H(K) = (K的第一個(gè)字母在字母表中的序號(hào)) % 11，若輸入順序?yàn)椋―、BA、TN、M、CI、I、K、X、TA），采用閉散列處理沖突方法為線性探測(cè)，要求構(gòu)造哈希表，在等概率的情況下查找成功的平均查找長(zhǎng)度為( )，查找不成功的平均查找長(zhǎng)度為( )
5.6 性能分析
雖然哈希表一直在和沖突做斗爭(zhēng)，但在實(shí)際使用過(guò)程中，哈希表的沖突率是不高的，沖突個(gè)數(shù)是可控的，也就是每個(gè)桶中的鏈表的長(zhǎng)度是一個(gè)常數(shù)。
因此，通常意義下我們認(rèn)為哈希表的插入、刪除、查找時(shí)間復(fù)雜度為：O(1)
6. 手動(dòng)實(shí)現(xiàn) HashMap（提及 hashCode 和 equals 的作用）
- HashMap 底層是：數(shù)組+單鏈表
- 我們可以先定義一個(gè)最基礎(chǔ)的哈希表，讓他可以實(shí)現(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 對(duì)應(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 返回，也可以?huà)伄惓?
}
// 新增元素
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();
}
}
// 計(jì)算負(fù)載因子
public double loadFactor(){
return this.usedSize*1.0/this.array.length;
}
// 擴(kuò)容后，重新構(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;
}
}
}
}
當(dāng)我們實(shí)現(xiàn)了對(duì)整形的部分哈希表的實(shí)現(xiàn)后，如果要實(shí)現(xiàn)其它類(lèi)型是有問(wèn)題的，因?yàn)槲覀冊(cè)O(shè)計(jì)的哈希函數(shù)為：Hash(Key) = Key % capacity，而其它類(lèi)型都不能取模，因此我們需要能夠?qū)?Key 進(jìn)行數(shù)字轉(zhuǎn)換的方法。而在 Object 類(lèi)有一個(gè) hashCode() 方法，它能將傳過(guò)來(lái)的對(duì)象，轉(zhuǎn)換成一個(gè)合法的數(shù)字，以此來(lái)找到合適的位置，因此使用它就能解決我們上述的麻煩。除此之外，上述代碼中的一些==需要修改為 equals() 方法，因?yàn)?equals 它能夠判斷傳入的對(duì)象的實(shí)例是否相等
通過(guò)上面一部分的分析，最終可以得到如下代碼：
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;
}
// 計(jì)算負(fù)載因子
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 會(huì)一樣嗎？
- equals 不一定一樣，因?yàn)?hashCode 是確定在數(shù)組中存儲(chǔ)的位置是不是一樣，但不能確定在哈希桶中，存放的 key 是不是一樣，即不能確定 equals 的結(jié)果是不是一樣
如果 equals 一樣，那么 hashCode 一樣嗎？
- hashCode 一定一樣，因?yàn)?equals 一樣了，那么在數(shù)組中存儲(chǔ)的位置是肯定一樣的
8. 哈希和 Java 類(lèi)集的關(guān)系
HashMap和HashSet即 Java 中利用哈希表實(shí)現(xiàn)的 Map 和 Set- Java 中會(huì)使用哈希桶解決哈希沖突
- Java 會(huì)在沖突鏈表長(zhǎng)度大于一定閾值后，將鏈表轉(zhuǎn)變?yōu)樗阉鳂?shù)（紅黑樹(shù)）。具體數(shù)值為當(dāng)前鏈表的長(zhǎng)度超過(guò)8且當(dāng)前桶的個(gè)數(shù)大于等于64時(shí)，就會(huì)將當(dāng)前長(zhǎng)度超過(guò)8的鏈表變?yōu)榧t黑樹(shù)
- Java 中計(jì)算哈希值實(shí)際上是調(diào)用 Object 類(lèi)的 hashCode 方法，進(jìn)行 Key 的相等性比較是調(diào)用的 equals 方法
- 自定義類(lèi)如果需要作為 HashMap 的 Key 或者 HashSet 的值，必須重寫(xiě)
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;
// 當(dāng)哈希表的大小為 0 時(shí)，進(jìn)行 resize 調(diào)整
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ((n - 1) & hash) 其實(shí)等價(jià)于 (n % 數(shù)組長(zhǎng)度) 但是前提條件是，n是2的次冪
// 如果為 null 就是第一次插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果不為 null，就進(jìn)行尾插法
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);
// 當(dāng)單鏈表的長(zhǎng)度大于8時(shí)，轉(zhuǎn)換為紅黑樹(shù)
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 方法的實(shí)現(xiàn)（以2倍的方式進(jìn)行擴(kuò)容）
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 ?？紗?wèn)題
問(wèn)題一：如果 new HashMap(19)，那么 bucket 數(shù)組有多大？
32，原因在第9大節(jié)的構(gòu)造方法四中
問(wèn)題二：HashMap 什么時(shí)候開(kāi)辟 bucket 數(shù)組占用內(nèi)存？
第一次 put 的時(shí)候
問(wèn)題三：HashMap 何時(shí)擴(kuò)容？
當(dāng)填入的元素/容量大于負(fù)載因子的時(shí)候，進(jìn)行擴(kuò)容，jdk1.8 負(fù)載因子默認(rèn)為0.75
問(wèn)題四：當(dāng)兩個(gè)對(duì)象的 hashCode 相同時(shí)會(huì)發(fā)生什么？
會(huì)發(fā)生哈希沖突
問(wèn)題五：如果兩個(gè)鍵的 hashCode 相同，你如何獲取值對(duì)象？
遍歷當(dāng)前位置的鏈表，通過(guò) equals 返回和要查詢(xún)的 Key 值一樣的 Key 的 Value
問(wèn)題六：你了解重新調(diào)整 HashMap 大小存在什么問(wèn)題嗎？
重新調(diào)整大小一定要進(jìn)行重新哈希
到此這篇關(guān)于Java 集合框架掌握 Map 和 Set 的使用(內(nèi)含哈希表源碼解讀及面試?？碱})的文章就介紹到這了,更多相關(guān)Java 集合框架掌握 Map 和 Set 的使用內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
JavaBean和SpringBean的區(qū)別及創(chuàng)建SpringBean方式
這篇文章主要介紹了JavaBean和SpringBean的區(qū)別及創(chuàng)建SpringBean方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
Spring核心容器之Bean創(chuàng)建過(guò)程詳解
這篇文章主要介紹了Spring核心容器之Bean創(chuàng)建過(guò)程詳解,獲取?Bean?的方法是?getBean,其來(lái)自?BeanFactory?繼承的AbstractAutowireCapableBeanFactory?抽象類(lèi)繼承的AbstractBeanFactory?抽象類(lèi)中,需要的朋友可以參考下2023-11-11
使用maven實(shí)現(xiàn)有關(guān)Jsoup簡(jiǎn)單爬蟲(chóng)的步驟
這篇文章主要介紹了使用maven實(shí)現(xiàn)有關(guān)Jsoup簡(jiǎn)單爬蟲(chóng)的步驟，文中附含詳細(xì)示例代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-09-09
Springboot集成Kafka實(shí)現(xiàn)producer和consumer的示例代碼
這篇文章主要介紹了Springboot集成Kafka實(shí)現(xiàn)producer和consumer的示例代碼，詳細(xì)的介紹了什么是Kafka和安裝Kafka以及在springboot項(xiàng)目中集成kafka收發(fā)message，感興趣的小伙伴們可以參考一下2018-05-05
springboot整合netty-mqtt-client實(shí)現(xiàn)Mqtt消息的訂閱和發(fā)布示例
本文主要介紹了springboot整合netty-mqtt-client實(shí)現(xiàn)Mqtt消息的訂閱和發(fā)布示例，文中根據(jù)實(shí)例編碼詳細(xì)介紹的十分詳盡，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
mybatis二級(jí)緩存的實(shí)現(xiàn)代碼
這篇文章主要為大家詳細(xì)介紹了mybatis二級(jí)緩存的實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-10-10
Java程序執(zhí)行過(guò)程及內(nèi)存機(jī)制詳解
本講將介紹Java代碼是如何一步步運(yùn)行起來(lái)的，還會(huì)介紹Java程序所占用的內(nèi)存是被如何管理的：堆、棧和方法區(qū)都各自負(fù)責(zé)存儲(chǔ)哪些內(nèi)容，感興趣的朋友跟隨小編一起看看吧2020-12-12
Jenkins配置自動(dòng)發(fā)送郵件過(guò)程圖解
這篇文章主要介紹了jenkins配置自動(dòng)發(fā)送郵件過(guò)程圖解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-02-02
MyEclipse+Tomcat+MAVEN+SVN項(xiàng)目完整環(huán)境搭建(圖文教程)
這篇文章主要介紹了MyEclipse+Tomcat+MAVEN+SVN項(xiàng)目完整環(huán)境搭建(圖文教程)，非常具有實(shí)用價(jià)值，需要的朋友可以參考下2017-12-12
IDEA在創(chuàng)建包時(shí)如何把包分開(kāi)實(shí)現(xiàn)自動(dòng)分層(方法詳解)
這篇文章主要介紹了IDEA在創(chuàng)建包時(shí)如何把包分開(kāi)實(shí)現(xiàn)自動(dòng)分層,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-09-09