java HashMap

HashMap是最常用的Map實現,它按照鍵的HashCode 值存儲數據,按照鍵可以直接獲取它的值，具有很快的拜候速度。HashMap最多只許可一筆記錄的鍵為Null(多條會籠蓋，也就是key不克不及反復);許可多筆記錄的值為 Null。非同步的也就是說線程不平安。

東西/原料

電腦
intellij IDEA

第一步：HashMap實現道理。

1
什么是HashMap？
1、基于哈希表的一個Map接話柄現，存儲的對象是一個鍵值對對象(Entry<K,V>)；
2、基于數組和鏈表實現，內部維護著一個數組table，該數組保留著每個鏈表的表頭結點；查找時，先經由過程hash函數計較key的hash值，再按照key的hash值計較數組索引（取余法），然后按照索引找到鏈表表頭結點，然后遍歷查找該鏈表；
2
HashMap數據布局
1、畫了個示意圖，如下，左邊的數組索引是按照key的hash值計較獲得，分歧hash值有可能發生一樣的索引，即哈希沖突，此時采用鏈地址法處置哈希沖突，即將所有索引一致的節點組成一個單鏈表；
3
HashMap擔當的類與實現的接口
1、HashMap接口示意圖：如下所示
2、Map接口，方式的寄義很簡單，根基上看個方式名就知道了，后面會在HashMap源碼闡發里具體申明
3、AbstractMap抽象類中界說的方式

第二步：關頭源碼講解

1
HashMap 是若何存儲的？
a.底層是一個數組 tab
b. hash=hash(key) ，然后按照數組長度n和hash值，決議當前需要put的元素對應的數組下標，
hash算法見紅框。
2
數組長度是固心猿意馬的，HashMap 可以無限put(k,v) ,為什么？
HashMap 的元素個數大于threshold的時辰，會進行resize() 擴容
3
若何實現擴容的？
擴容就是經由過程 resize() , 從頭建立一個新數組，對所有元素rehash,放到新數組響應位置。
擴容價格是很大的，所以良多公司編碼規范都有一條，合理設置hashMap的InitialCapicity,
禁止直接用HashMap()
4
Hash 沖突是什么？怎么解決這個問題？
1、Hash 沖突：假如一個黌舍有366個同窗，一年365天，那么至少有兩個同窗是統一生成日，這就是hash沖突。用代碼來說，分歧的key 顛末計較p = tab[i = (n - 1) & hash] 對應統一個p
2、若何解決:
p在有的翻譯文檔中叫桶，一個桶可以裝多個，怎么裝? 鏈表或者紅黑樹。
3、下圖代碼中 else if 部門是紅黑樹
else 部門是鏈表，鏈表中若是沖突元素個>=TREEIFY_THRESHOLD-1,會將鏈表轉換當作紅黑樹。
因為元素個數良多時，紅黑樹比鏈表機能更好。
5
HashMap 是不是線程平安的，若何解決線程平安問題？
1、HashMap 是線程不平安的
2、對整個map加鎖。
3、如圖（3）對f加鎖了，就是對桶加鎖，就是傳說中的分段鎖機制。
在包管平安的前提下，加鎖的規模越小，則程序機能越高，本身寫代碼時切記胡亂在方式上加synchronized
6
HashMap 和 hash() equals() 方式的關系
1、面試中面試官會問重寫equals()方式要注重是什么，謎底是hash()也要重寫。
不重寫會引起HashMap 等調集類利用的紊亂。
2、如下圖：好比類Person(id,name)，重寫了 equals(Object obj){... reutrn this.id==obj.id}，沒有重寫hash(), 那么從類界說上來說，只要id相等就是統一小我，當我們Person作為key，放入兩個Person對象(id相等)到HashMap的時辰，那么就翻車了，HashMap 會有兩個元素，而我們期望的只保留一個。
7
驗證ConcurrentHashMap 線程平安。

第三步：HashMap利用實例

1
常用根基操作
package com.pichen.collection;

import java.util.HashMap;
import java.util.Map;

public class Main {

public static void main(String[] args) {
Map<String, Integer> map = new HashMap<String, Integer>();

//put方式
map.put("A", 5);
map.put("B", 6);
map.put("C", 7);
map.put("D", 8);

//重寫了toString方式
System.out.println(map);

//size方式
System.out.println(map.size());

System.out.println(map.containsKey("A"));
System.out.println(map.containsValue(6));
System.out.println(map.get("B"));

//remove
map.remove("C");
System.out.println(map);

//key調集
for(String str:map.keySet()){
System.out.print(str + " ");
}

System.out.println();
//value調集
for(Integer obj:map.values()){
System.out.print(obj + " ");
}

System.out.println();
//key-value調集
for(Map.Entry<String, Integer> entry:map.entrySet()){
System.out.print(entry.getKey() + ": " + entry.getValue() + ", ");
}

}
}