目錄
一.簡介
二.數(shù)據(jù)結(jié)構(gòu)
三.具體使用
四.基礎(chǔ)知識
五.源碼分析
六.源碼總結(jié)
七.與jdk1.8的區(qū)別
八.額外補充：關(guān)于HashMap的其他問題
九.總結(jié)
一 簡介
?? 類定義
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
主要介紹
???HashMap的實現(xiàn)在JDK1.7和JDK1.8差別較大
二 數(shù)據(jù)結(jié)構(gòu)
? 具體描述
HashMap 采用的數(shù)據(jù)結(jié)構(gòu) : 數(shù)組(主) + 單鏈表(副)
該數(shù)據(jù)結(jié)構(gòu)方式也稱：拉鏈法（鏈路法）‘
? 存儲流程
? 數(shù)組元素 & 鏈表節(jié)點的 實現(xiàn)類
HashMap中的數(shù)組元素&鏈表節(jié)點 采用 Entry 類實現(xiàn)
1.HashMap的本質(zhì)=1個存儲Entry類對象的數(shù)組+多個單鏈表
2.Entry對象本質(zhì)=1個映射(鍵-值)觅够，屬性包括：鍵(key)灭红、值(value) & 下1節(jié)點(next)=單鏈表的指針=也是一個Entry對象，用于解決hash沖突
三 具體使用
? 主要使用的API（方法走趋、函數(shù)）
V get(Object key); // 獲得指定鍵的值
V put(K key, V value);? // 添加鍵值對
void putAll(Map<? extends K, ? extends V> m);? // 將指定Map中的鍵值對 復(fù)制到 此Map中
V remove(Object key);? // 刪除該鍵值對
boolean containsKey(Object key); // 判斷是否存在該鍵的鍵值對助泽；是 則返回true
boolean containsValue(Object value);? // 判斷是否存在該值的鍵值對楞慈；是 則返回true
Set<K> keySet();? // 單獨抽取key序列旺嬉，將所有key生成一個Set
Collection<V> values();? // 單獨value序列败潦，將所有value生成一個Collection
void clear(); // 清除哈希表中的所有鍵值對
int size();? // 返回哈希表中所有 鍵值對的數(shù)量 = 數(shù)組中的鍵值對 + 鏈表中的鍵值對
boolean isEmpty(); // 判斷HashMap是否為空本冲；size == 0時 表示為 空
?使用
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
? ? public static void main(String[] args) {
? ? ? /**
? ? ? ? * 1. 聲明1個 HashMap的對象
? ? ? ? */
? ? ? ? Map<String, Integer> map = new HashMap<String, Integer>();
? ? ? /**
? ? ? ? * 2. 向HashMap添加數(shù)據(jù)（成對 放入 鍵 - 值對）
? ? ? ? */
? ? ? ? map.put("Android", 1);
? ? ? ? map.put("Java", 2);
? ? ? ? map.put("iOS", 3);
? ? ? ? map.put("數(shù)據(jù)挖掘", 4);
? ? ? ? map.put("產(chǎn)品經(jīng)理", 5);
? ? ? /**
? ? ? ? * 3. 獲取 HashMap 的某個數(shù)據(jù)
? ? ? ? */
? ? ? ? System.out.println("key = 產(chǎn)品經(jīng)理時的值為：" + map.get("產(chǎn)品經(jīng)理"));
? ? ? /**
? ? ? ? * 4. 獲取 HashMap 的全部數(shù)據(jù)：遍歷HashMap
? ? ? ? * 核心思想：
? ? ? ? * 步驟1：獲得key-value對（Entry） 或 key 或 value的Set集合
? ? ? ? * 步驟2：遍歷上述Set集合(使用for循環(huán) 准脂、 迭代器（Iterator）均可)
? ? ? ? * 方法共有3種：分別針對 key-value對（Entry） 或 key 或 value
? ? ? ? */
? ? ? ? // 方法1：獲得key-value的Set集合 再遍歷
? ? ? ? System.out.println("方法1");
? ? ? ? // 1. 獲得key-value對（Entry）的Set集合
? ? ? ? Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
? ? ? ? // 2. 遍歷Set集合，從而獲取key-value
? ? ? ? // 2.1 通過for循環(huán)
? ? ? ? for(Map.Entry<String, Integer> entry : entrySet){
? ? ? ? ? ? System.out.print(entry.getKey());
? ? ? ? ? ? System.out.println(entry.getValue());
? ? ? ? }
? ? ? ? System.out.println("----------");
? ? ? ? // 2.2 通過迭代器：先獲得key-value對（Entry）的Iterator眼俊，再循環(huán)遍歷
? ? ? ? Iterator iter1 = entrySet.iterator();
? ? ? ? while (iter1.hasNext()) {
? ? ? ? ? ? // 遍歷時意狠，需先獲取entry粟关，再分別獲取key疮胖、value
? ? ? ? ? ? Map.Entry entry = (Map.Entry) iter1.next();
? ? ? ? ? ? System.out.print((String) entry.getKey());
? ? ? ? ? ? System.out.println((Integer) entry.getValue());
? ? ? ? }
? ? ? ? // 方法2：獲得key的Set集合 再遍歷
? ? ? ? System.out.println("方法2");
? ? ? ? // 1. 獲得key的Set集合
? ? ? ? Set<String> keySet = map.keySet();
? ? ? ? // 2. 遍歷Set集合，從而獲取key闷板，再獲取value
? ? ? ? // 2.1 通過for循環(huán)
? ? ? ? for(String key : keySet){
? ? ? ? ? ? System.out.print(key);
? ? ? ? ? ? System.out.println(map.get(key));
? ? ? ? }
? ? ? ? System.out.println("----------");
? ? ? ? // 2.2 通過迭代器：先獲得key的Iterator澎灸，再循環(huán)遍歷
? ? ? ? Iterator iter2 = keySet.iterator();
? ? ? ? String key = null;
? ? ? ? while (iter2.hasNext()) {
? ? ? ? ? ? key = (String)iter2.next();
? ? ? ? ? ? System.out.print(key);
? ? ? ? ? ? System.out.println(map.get(key));
? ? ? ? }
? ? ? ? // 方法3：獲得value的Set集合 再遍歷
? ? ? ? System.out.println("方法3");
? ? ? ? // 1. 獲得value的Set集合
? ? ? ? Collection valueSet = map.values();
? ? ? ? // 2. 遍歷Set集合，從而獲取value
? ? ? ? // 2.1 獲得values 的Iterator
? ? ? ? Iterator iter3 = valueSet.iterator();
? ? ? ? // 2.2 通過遍歷遮晚，直接獲取value
? ? ? ? while (iter3.hasNext()) {
? ? ? ? ? ? System.out.println(iter3.next());
? ? ? ? }
? ? }
}
// 注：對于遍歷方式性昭，推薦使用針對 key-value對（Entry）的方式：效率高
// 原因(此處存在疑問：看了源碼keySet、valueSet相對于entrySet只多了一個獲取值得操作)：
? // 1. 對于 遍歷keySet 县遣、valueSet糜颠，實質(zhì)上 = 遍歷了2次：1 = 轉(zhuǎn)為 iterator 迭代器遍歷、2 = 從 HashMap 中取出 key 的 value 操作（通過 key 值 hashCode 和 equals 索引）
? // 2. 對于 遍歷 entrySet 萧求，實質(zhì) = 遍歷了1次 = 獲取存儲實體Entry（存儲了key 和 value ）
四 基礎(chǔ)知識
? HashMap中的重要參數(shù)(變量)
? 具體介紹
/*
*1.容量(capacity):HashMap中數(shù)組的長度
*a.容量范圍：必須是2的冪 & <最大容量（2的30次方）
*b.初始容量=哈希表創(chuàng)建時的容量
*默認容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十進制的2^4 = 16
*/
static final int DEFAULT_INITIAL_CAPACITY =1 << 4;
//最大容量 = 2的30次方(若傳入的容量過大其兴，將被最大值替換)
static final int MAXIMUM_CAPACITY =1 <<30;
/*
*2.加載因子(load factor)：限制HashMap的容量，當(dāng)容量超過 負載因子 * ?哈希表的現(xiàn)有容量 * <= 添加元素后的容量夸政，擴容
*/
//實際加載因子
final float loadFactor;
//默認加載因子=0.75
static final float DEFAULT_LOAD_FACTOR =0.75f;
//3.擴容閾值(threshold):當(dāng)哈希表的大小 >=擴容閾值 時元旬，就會擴容哈希表
//擴容閾值 = 容量 * 加載因子
int threshold;
//HashMap 的實現(xiàn)方式 = 拉鏈法，Entry數(shù)組上的每個元素本質(zhì)上是一個單鏈表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//HashMap的大小守问，即 HashMap中存儲的鍵值對的數(shù)量
transient int size;
? 詳細說明 加載因子
五 源碼分析
? 聲明一個HashMap的對象
/**
? * 函數(shù)使用原型
? */
? Map<String,Integer> map = new HashMap<String,Integer>();
/**
? * 源碼分析：主要是HashMap的構(gòu)造函數(shù) = 4個
? * 僅貼出關(guān)于HashMap構(gòu)造函數(shù)的源碼
? */
? public class HashMap<K,V>
? ? ? extends AbstractMap<K,V>
? ? ? implements Map<K,V>, Cloneable, Serializable{
? ? // 省略上節(jié)闡述的參數(shù)
? /**
? ? * 構(gòu)造函數(shù)1：默認構(gòu)造函數(shù)（無參）
? ? * 加載因子 & 容量 = 默認 = 0.75匀归、16
? ? */
? ? public HashMap() {
? ? ? ? // 實際上是調(diào)用構(gòu)造函數(shù)3：指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
? ? ? ? // 傳入的指定容量 & 加載因子 = 默認
? ? ? ? this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
? ? }
? ? /**
? ? * 構(gòu)造函數(shù)2：指定“容量大小”的構(gòu)造函數(shù)
? ? * 加載因子 = 默認 = 0.75 、容量 = 指定大小
? ? */
? ? public HashMap(int initialCapacity) {
? ? ? ? // 實際上是調(diào)用指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
? ? ? ? // 只是在傳入的加載因子參數(shù) = 默認加載因子
? ? ? ? this(initialCapacity, DEFAULT_LOAD_FACTOR);
? ? }
? ? /**
? ? * 構(gòu)造函數(shù)3：指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
? ? * 加載因子 & 容量 = 自己指定
? ? */
? ? public HashMap(int initialCapacity, float loadFactor) {
? ? ? ? // HashMap的最大容量只能是MAXIMUM_CAPACITY耗帕，哪怕傳入的 > 最大容量
? ? ? ? if (initialCapacity > MAXIMUM_CAPACITY)
? ? ? ? ? ? initialCapacity = MAXIMUM_CAPACITY;
? ? ? ? // 設(shè)置 加載因子
? ? ? ? this.loadFactor = loadFactor;
? ? ? ? // 設(shè)置 擴容閾值 = 初始容量
? ? ? ? // 注：此處不是真正的閾值穆端，是為了擴展table，該閾值后面會重新計算仿便，下面會詳細講解?
? ? ? ? threshold = initialCapacity;?
? ? ? ? init(); // 一個空方法用于未來的子對象擴展
? ? }
? ? /**
? ? * 構(gòu)造函數(shù)4：包含“子Map”的構(gòu)造函數(shù)
? ? * 即 構(gòu)造出來的HashMap包含傳入Map的映射關(guān)系
? ? * 加載因子 & 容量 = 默認
? ? */
? ? public HashMap(Map<? extends K, ? extends V> m) {
? ? ? ? // 設(shè)置容量大小 & 加載因子 = 默認
? ? ? ? this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
? ? ? ? ? ? ? ? DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
? ? ? ? // 該方法用于初始化 數(shù)組 & 閾值体啰，下面會詳細說明
? ? ? ? inflateTable(threshold);
? ? ? ? // 將傳入的子Map中的全部元素逐個添加到HashMap中
? ? ? ? putAllForCreate(m);
? ? }
}
注：
1.此處僅用于接收初始容量大小(capacity)、加載因子(load factor),但仍無真正初始化哈希表探越，及初始化存儲數(shù)組table狡赐；
2.此處結(jié)論：真正初始化哈希表(初始化存儲數(shù)組table)是在第一次添加鍵值對時，即 第一次 調(diào)用 put()時
? 向HashMap添加數(shù)據(jù)
詳細流程如下：
? put源碼
/**
? ? * 源碼分析：主要分析： HashMap的put函數(shù)
? ? */
? ? public V put(K key, V value)
（分析1）// 1. 若 哈希表未初始化（即 table為空)
? ? ? ? // 則使用 構(gòu)造函數(shù)時設(shè)置的閾值(即初始容量) 初始化 數(shù)組table?
? ? ? ? if (table == EMPTY_TABLE) {
? ? ? ? inflateTable(threshold);
? ? }?
? ? ? ? // 2. 判斷key是否為空值null
（分析2）// 2.1 若key == null钦幔，則將該鍵-值 存放到數(shù)組table 中的第1個位置枕屉，即table [0]
? ? ? ? // （本質(zhì)：key = Null時，hash值 = 0鲤氢，故存放到table[0]中）
? ? ? ? // 該位置永遠只有1個value搀擂，新傳進來的value會覆蓋舊的value
? ? ? ? if (key == null)
? ? ? ? ? ? return putForNullKey(value);
（分析3） // 2.2 若 key ≠ null西潘，則計算存放數(shù)組 table 中的位置（下標(biāo)、索引）
? ? ? ? // a. 根據(jù)鍵值key計算hash值
? ? ? ? int hash = hash(key);
? ? ? ? // b. 根據(jù)hash值 最終獲得 key對應(yīng)存放的數(shù)組Table中位置
? ? ? ? int i = indexFor(hash, table.length);
? ? ? ? // 3. 判斷該key對應(yīng)的值是否已存在（通過遍歷 以該數(shù)組元素為頭結(jié)點的鏈表 逐個判斷）
? ? ? ? for (Entry<K,V> e = table[i]; e != null; e = e.next) {
? ? ? ? ? ? Object k;
（分析4）// 3.1 若該key已存在（即 key-value已存在 ）哨颂，則用 新value 替換 舊value
? ? ? ? ? ? if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
? ? ? ? ? ? ? ? V oldValue = e.value;
? ? ? ? ? ? ? ? e.value = value;
? ? ? ? ? ? ? ? e.recordAccess(this);
? ? ? ? ? ? ? ? return oldValue; //并返回舊的value
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? modCount++;
（分析5）// 3.2 若 該key不存在喷市，則將“key-value”添加到table中
? ? ? ? addEntry(hash, key, value, i);
? ? ? ? return null;
? ? }
? 初始化哈希表-初始化數(shù)組
/**
? ? * 函數(shù)使用原型
? ? */
? ? ? if (table == EMPTY_TABLE) {
? ? ? ? inflateTable(threshold);
? ? }?
? /**
? ? * 源碼分析：inflateTable(threshold);
? ? */
? ? private void inflateTable(int toSize) {?
? ? // 1. 將傳入的容量大小轉(zhuǎn)化為：>傳入容量大小的最小的2的次冪
? ? // 即如果傳入的是容量大小是19，那么轉(zhuǎn)化后威恼，初始化容量大小為32（即2的5次冪）
? ? int capacity = roundUpToPowerOf2(toSize);->>分析1?
? ? // 2. 重新計算閾值 threshold = 容量 * 加載因子?
? ? threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);?
? ? // 3. 使用計算后的初始容量（已經(jīng)是2的次冪） 初始化數(shù)組table（作為數(shù)組長度）
? ? // 即 哈希表的容量大小 = 數(shù)組大衅沸铡（長度）
? ? table = new Entry[capacity]; //用該容量初始化table?
? ? initHashSeedAsNeeded(capacity);?
}?
? ? /**
? ? * 分析1：roundUpToPowerOf2(toSize)
? ? * 作用：將傳入的容量大小轉(zhuǎn)化為：>傳入容量大小的最小的2的冪
? ? * 特別注意：容量大小必須為2的冪，該原因在下面的講解會詳細分析
? ? */
? ? private static int roundUpToPowerOf2(int number) {?
? ? ? //若 容量超過了最大值箫措，初始化容量設(shè)置為最大值 腹备；否則，設(shè)置為：>傳入容量大小的最小的2的次冪
? ? ? return number >= MAXIMUM_CAPACITY? ?
? ? ? ? ? ? MAXIMUM_CAPACITY? : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
? PUT源碼
/**
? ? * 函數(shù)使用原型
? ? */
? ? ? if (key == null)
? ? ? ? ? return putForNullKey(value);
? /**
? ? * 源碼分析：putForNullKey(value)
? ? */
? ? ? private V putForNullKey(V value) {?
? ? ? ? // 遍歷以table[0]為首的鏈表斤蔓，尋找是否存在key==null 對應(yīng)的鍵值對
? ? ? ? // 1. 若有：則用新value 替換 舊value植酥；同時返回舊的value值
? ? ? ? for (Entry<K,V> e = table[0]; e != null; e = e.next) {?
? ? ? ? ? if (e.key == null) {?
? ? ? ? ? ? V oldValue = e.value;?
? ? ? ? ? ? e.value = value;?
? ? ? ? ? ? e.recordAccess(this);?
? ? ? ? ? ? return oldValue;?
? ? ? ? }?
? ? }?
? ? modCount++;?
? ? // 2 .若無key==null的鍵，那么調(diào)用addEntry（）弦牡，將空鍵 & 對應(yīng)的值封裝到Entry中友驮，并放到table[0]中
? ? addEntry(0, null, value, 0);
? ? // 注：
? ? // a. addEntry（）的第1個參數(shù) = hash值 = 傳入0
? ? // b. 即 說明：當(dāng)key = null時，也有hash值 = 0驾锰，所以HashMap的key 可為null
? ? // c. 對比HashTable卸留，由于HashTable對key直接hashCode（），若key為null時稻据，會拋出異常艾猜，所以HashTable的key不可為null
? ? // d. 此處只需知道是將 key-value 添加到HashMap中即可，關(guān)于addEntry（）的源碼分析將等到下面再詳細說明捻悯，
? ? return null;?
} ??
?分析
為什么不直接采用經(jīng)過hashCode()處理的哈希嗎作為存儲數(shù)組table的下標(biāo)位置匆赃？
為什么采用 哈希碼 & (數(shù)組長度-1) 計算數(shù)組下標(biāo)？
引用:https://blog.csdn.net/carson_ho/article/details/79373026
