一、HashMap的誕生
1.1 陣列
陣列：一片物理上連續的大小確定的儲存空間，
好處：根據下標快速的查找和修改里面的內容，
缺點：大小確定，無法修改，添加新的元素或者洗掉元素比較麻煩，
陣列的靜態初始化
//陣列實作方式一：
//資料型別 陣列名稱[] = {值, 值,…}
String str[] = {"移動端","Android","iOS"};
System.out.println(str.length);//三個元素
for (int i = 0; i <str.length ; i++) {
System.out.println(str[i]);
}
//陣列實作方式二：
//資料型別 陣列名稱[] = new 資料型別[] {值, 值,…}
String str2[] = new String[3];
str2[0] = "移動端";
str2[1] = "Android";
str2[2] = "iOS";
System.out.println(str2.length);//三個元素
for (int i = 0; i <str2.length ; i++) {
System.out.println(str2[i]);
}
運行結果是一樣的，
"E:\Android\Android StudioO\jre\bin\java.exe"...
3
移動端
Android
iOS
如果我想再添加兩個新元素(Java、Kotlin)，那么使用陣列就不合適了，這時候順序表就出現了，
1.2 順序表
順序表：以陣列的形式保存的線性表，物理上連續、邏輯上連續、大小可以動態增加，(如：ArrayList)
順序表用的頻率遠遠高于資料，用肯定都會用，咱們看看原始碼，
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
transient Object[] elementData;//存盤 ArrayList 元素的陣列緩沖區，
private int size;//ArrayList 的大小
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
}
然后你會發現還是用陣列進行存盤的，只不過把對陣列的操作處理了，而不需要我們自己處理，
原來的資料：
新增資料:
而順序表的新增和洗掉元素都需要大量移動元素等操作，此時鏈表就產生了，
1.3 鏈表
鏈表：鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標連接次序實作的，
新增
這里將元素1的指標由指向元素2改為指向新增元素4，然后再將元素4的指標指向元素2即可，
洗掉元素
將元素1的指標直接指向元素3即可，
1.4 ArrayList 和 LinkedList 對比
ArrayList(順序表)：
-
優點：查找快
-
缺點：增刪慢
LinkedList(鏈表)
-
優點：增刪快
-
缺點：查找慢
那么問題來了在什么情況下使用 ArrayList？在什么情況下使用 LinkedList？ 為什么？
那么可不可以將 順序表和鏈表的優點結合起來呢？——Hash表
1.5 Hash表
散串列（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函式叫做散列函式，存放記錄的陣列叫做散串列，
哈希表其實本質上就是一個陣列，可以根據一個key值來直接訪問資料，查找速度快，
二、HashMap
HashMap采用Node(implements Map.Entry)陣列來存盤key-value對，每一個鍵值對組成了一個Node物體，Node類實際上是一個單向的鏈表結構，它具有Next指標，可以連接下一個Node物體，
注意：jdk1.8 HashMap中的Entry不見了，取而代之的是Node，但是Node也實作了Map.Entry介面，和之前的Entry類似，
Node類
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
...
}
}
從上面看出 hash、key、value 代表本節點資料，next表示指向下一個節點的資料，
-
JDK1.8之前，哈希表底層采用陣列+鏈表實作，即使用鏈表處理沖突，同一hash值的鏈表都存盤在一個鏈表里，但是當位于一個桶中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低，
-
JDK1.8中，哈希表存盤采用陣列+鏈表+紅黑樹實作，當鏈表長度超過閾值（8） 時，將鏈表轉換為紅黑樹，這樣大大減少了查找時間，
2.0 小試牛刀
class HashMapTest {
public static void main(String[] args) {
//創建HashMap
HashMap<String,String> hashMap = new HashMap<>();
//添加資料（key-value）
hashMap.put("name","帥次");
hashMap.put("age","20");
hashMap.put("subject","Android");
hashMap.put(null,"空Key");
System.out.println("HashMap1:"+hashMap.toString());//{null=空Key, subject=Android, name=帥次, age=20}
//添加資料(覆寫已有key)
hashMap.put("age","26");
System.out.println("HashMap2:"+hashMap.toString());//{null=空Key, subject=Android, name=帥次, age=26}
//根據key，獲取value
System.out.println("Key-null:"+hashMap.get(null));//空Key
System.out.println("Key-subject:"+hashMap.get("subject"));//Android
//根據key洗掉元素
System.out.println("洗掉subject對應:"+hashMap.remove("subject"));//洗掉subject對應:Android
//根據key-value洗掉元素
System.out.println("洗掉age:"+hashMap.remove("age","20"));//洗掉age對應20:false
System.out.println(hashMap.toString());//{null=空Key, name=帥次, age=26}
System.out.println("洗掉age:"+hashMap.remove("age","26"));//洗掉age對應20:true
System.out.println("HashMap3:"+hashMap.toString());//{null=空Key, name=帥次}
//方法一：1、獲得key-value的Set集合，2、回圈(推薦)
Set<Map.Entry<String,String>> entrySet= hashMap.entrySet();
for (Map.Entry<String, String> strEntry : entrySet) {
System.out.println("遍歷Set集合："+strEntry.getKey()+"-"+strEntry.getValue());
}
//方法二：1、獲取key的Set集合，2、回圈
Set<String> strKeySet= hashMap.keySet();
for (String s : strKeySet) {
//先獲取key，通過key獲取value
System.out.println("遍歷KeySet集合："+s+"-"+hashMap.get(s));
}
//方法三：1、獲得key-value的Set集合，2、獲取iterator 3、回圈
Set<Map.Entry<String,String>> itEntrySet= hashMap.entrySet();
Iterator iterator = itEntrySet.iterator();
while (iterator.hasNext()){
Map.Entry map= (Map.Entry)iterator.next();
System.out.println("遍歷Iterator："+map.getKey()+"-"+map.getValue());
}
//其他還有不少方法可以遍歷資料
}
}
運行結果
"E:\Android...."
HashMap1:{null=空Key, subject=Android, name=帥次, age=20}
HashMap2:{null=空Key, subject=Android, name=帥次, age=26}
Key-null:空Key
Key-subject:Android
洗掉subject對應:Android
洗掉age:false
{null=空Key, name=帥次, age=26}
洗掉age:true
HashMap3:{null=空Key, name=帥次}
遍歷Set集合：null-空Key
遍歷Set集合：name-帥次
遍歷KeySet集合：null-空Key
遍歷KeySet集合：name-帥次
遍歷Iterator：null-空Key
遍歷Iterator：name-帥次
Process finished with exit code 0
2.1 構造方法
/**
* 默認加載因子值
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 哈希表的加載因子，
*/
final float loadFactor;
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 構造一個具有默認加載因子 (0.75) 的空 HashMap，
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap有4個構造方法，主要初始化了三個引數：
-
initialCapacity：初始容量(默認16)，
-
loadFactor 加載因子(默認0.75)，
-
threshold 閾值：hashMap所能容納的最大價值對數量，如果超過則需要擴容，計算方式：
threshold=initialCapacity*loadFactor，
加載因子：在默認情況下，陣列大小為16，那么當HashMap中元素個數超過
16*0.75=12的時候，就把陣列的大小擴展為16*2=32，即擴大一倍，然后重新計算每個元素在陣列中的位置，當然這個值是可以自己設定的，但是不推薦修改這個值，
咱們比較常用的還是無參構造方法，HashMap 創建好了，那么咱們開始存盤資料吧，
2.2 put()
添加資料：
-
key可以為null
-
key唯一，如果key存在則覆寫value內容
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這里在呼叫 putVal() 方法前根據key進行了hash計算，
2.2.1 hash(key)
/**
* 計算 key.hashCode() 并將散列的高位散列（XOR）到低位，由于該表使用二次冪掩碼，因此僅在當前掩碼之上位變化的散列集將始終發生沖突，
* 使用樹來處理 bin 中的大量沖突，我們只是以最便宜的方式對一些移位的位進行異或，以減少系統損失，以及合并最高位的影響，否則由于表邊界，這些最高位將永遠不會用于索引計算(摘自原始碼)，
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public int hashCode() {
return identityHashCode(this);
}
static int identityHashCode(Object obj) {
int lockWord = obj.shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
return identityHashCodeNative(obj);
}
-
當 key == null 時回傳0，也就是說 key 可以設定為 null，
-
從identityHashCode()方法看出key可以是任意型別，都可以變成int型別的hashCode，
h >>> 16 是什么?
h是hashCode，h >>> 16是用來取出h的高16，(>>>是無符號右移)
0000 0100 1011 0011 1101 1111 1110 0001
>>> 4
0000 0000 0100 1011 0011 1101 1111 1110
>>> 16
0000 0000 0000 0000 0000 0100 1011 0011
上面兩個例子 一個>>>4 一個>>>16，可用于對比，
這里根據Key回傳了一個Hash值，拿到哈希值咱們繼續看 putVal() 方法，
2.2.2 putVal()
/**
* table 在首次使用時初始化，存盤資料的Node型別 陣列，并根據需要調整大小，
* 長度 = 2 的冪，(特殊情況下可為0)，陣列的每個元素 = 1個單鏈表
*/
transient Node<K,V>[] table;
/**
* @param hash 鍵的哈希值
* @param key 鍵
* @param value 要放置的值
* @param onlyIfAbsent 如果為真，則不要更改現有值
* @param evict 如果為 false，則表處于創建模式，
* @return 前一個值，如果沒有則回傳 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷table是否初始化
if ((tab = table) == null || (n = tab.length) == 0)
//呼叫 resize() 方法，進行初始化并賦值
n = (tab = resize()).length;
//通過hash獲取下標，如果資料為null
if ((p = tab[i = (n - 1) & hash]) == null)
//tab[i]下標沒有值，創建新的Node并賦值，
tab[i] = newNode(hash, key, value, null);
else {
//tab[i] 下標的有資料，發生碰撞
Node<K,V> e; K k;
//判斷tab[i]的hash值傳入的hash值相當，tab[i]的的key值和傳入的key值相同
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) {
//p的下一個節點為null,表示p就是最后一個節點
if ((e = p.next) == null) {
//創建Node并插入鏈表的尾部
p.next = newNode(hash, key, value, null);
//當元素>=8-1，鏈表轉為樹(紅黑樹)結構
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果key在鏈表中已經存在，則退出回圈
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//更新p指向下一個節點，繼續遍歷
p = e;
}
}
//如果key在鏈表中已經存在，則修改其原先key的value值，并且回傳老的value值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//替換舊值時會呼叫的方法(默認實作為空)
return oldValue;
}
}
++modCount;//修改次數
//根據map值判斷是否要對map的大小擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);//插入成功時會呼叫的方法(默認實作為空)
return null;
}
2.2.3 resize() 擴容
/**
* 默認初始容量 - 必須是 2 的冪，
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 初始化或加倍 table 大小， 如果為空，則按照欄位閾值中保存的初始容量目標進行分配，
* 否則，因為我們使用二次冪擴展
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//table已經初始化，且容量 > 0
if (oldCap > 0) {
//MAXIMUM_CAPACITY=1<<30=2的30次冪=1073741824
if (oldCap >= MAXIMUM_CAPACITY) {
//如果舊的容量已近達到最大值，則不再擴容，閾值直接設定為最大值
//Integer.MAX_VALUE=(1 << 31)-1=2的31次冪-1=2147483648-1
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 擴大兩倍
}
else if (oldThr > 0) // 初始化容器=threshold
newCap = oldThr;
else {
//threshold 和 table 皆未初始化情況，此處即為首次進行初始化
//第一次進入什么都沒有所以要初始化容器(16)
newCap = DEFAULT_INITIAL_CAPACITY;
//12 = 0.75*16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//newThr 為 0 時，計算閾值
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資料
table = newTab;
//如果之前的陣列桶里面已經存在資料，由于table容量發生變化，hash值也會發生變化，需要重新計算下標
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//將指定下標資料不為null
if ((e = oldTab[j]) != null) {
//將指定下標資料置空
oldTab[j] = null;
//指定下標資料只有一個
if (e.next == null)
//直接將資料存放到新計算的hash值下標
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//紅黑樹
//將樹箱中的節點拆分為下樹箱和上樹箱，如果現在太小(<=6)，則資料結構取消紅黑樹改為鏈表，
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //鏈表
//重新計算hash值，根據新的下標重新分組
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;
}
因此，resize()方法 初始化了容器，并給 table 賦值，回傳Node<K,V>[]，
2.2.4 putTreeVal()
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//獲取根節點
TreeNode<K,V> root = (parent != null) ? root() : this;
//回圈所有的節點，如果key沖突，回傳原key對應的物件，如果不存在key沖突，則直接存放物件，并回傳null物件
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//dir：決定節點的位置
if ((ph = p.hash) > h)//當前節點的哈希值大于存放物件的哈希值
dir = -1;
else if (ph < h)//當前節點的哈希值小于存放物件的哈希值
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))//當前節點等于存放物件的哈希值，且key相同，則回傳當前節點
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//如果不按哈希值排序，而是按照比較器排序，則通過比較器回傳值決定進入左右結點
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
//如果p的左節點或右節點為空，證明已經找到存放位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
//創建新節點
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
//根據dir設定存放位置
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//balanceInsertion樹化結構，設定紅黑節點，是否需要旋轉
//moveRootToFront重置根節點
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
2.3 get()
獲取資料
這方法回傳結果：
-
節點(Node);
- null
-
該 key 對應的資料就是 null;
-
HashMap 中不存在該 key
-
public V get(Object key) {
Node<K,V> e;
//hash(key)：根據key的hashCode計算hash值，這個跟put中的的一樣，
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
這個方法就是通過 getNode() 方法來獲取節點，如果節點為null則回傳null，如果節點存在則回傳key對應的value，
2.3.1 getNode()
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return 節點(node)，如果沒有則回傳 null
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//根據hash值獲取table中節點存放位置，并獲取第一個元素，
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一個節點是我們要找的Key，則直接回傳
if (first.hash == hash && //
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//獲取下一個節點的資訊
if ((e = first.next) != null) {
//判斷資料結構是紅黑樹，則通過getTreeNode()獲取節點并回傳
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//否則回圈整個鏈表找到節點并回傳
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2.3.2 getTreeNode()
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
TreeNode<K,V> parent; // 紅黑樹節點
//呼叫樹的find()函式
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
2.3.3 find()
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)//當前節點的哈希值大于給定哈希值，進入左節點
p = pl;
else if (ph < h)//當前節點小于給定哈希值，進入右節點
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))//當前節點等于給定哈希值，且key相同，則回傳當前節點
return p;
else if (pl == null)//如果左節點為null，則進入右節點
p = pr;
else if (pr == null)//如果右節點為null，則進入左節點
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)//如果不按哈希值排序，而是按照比較器排序，則通過比較器回傳值決定進入左右結點
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)//如果在右結點中找到該關鍵字，直接回傳當前節點
return q;
else//進入左節點
p = pl;
} while (p != null);
return null;
}
2.4 remove()
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//判斷table是否存在、資料元素大于>0、index位置元素是否存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//判斷p和傳入的資料一致
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//獲取p的資料
node = p;
else if ((e = p.next) != null) {//和p資料不一致，獲取p下一個節點資料
//判斷p的資料結構是否為紅黑樹
if (p instanceof TreeNode)
//紅黑樹，呼叫find找到node節點
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//鏈表
do {
//回圈找到跟e相同的資料
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//判斷獲取到的資料
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//根據紅黑樹洗掉資料
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//node=p,然后指標指向p節點后一個節點，達到洗掉node的目的
tab[index] = node.next;
else//此時node=p.next,所以node就被干掉了
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
這個方法其實跟上面的 put/get 方法類似，都是先獲取哈希值，然后根據哈希值和Key找到這個節點，進行洗掉，自己探索樂趣多多，
2.5 clear()
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
這個簡單粗暴，直接遍歷table，然后將table的值設定為null，
其實HashMap常用的方法也就這么幾個，你了解了嗎？
三、問答小知識
3.1 為什么Key總喜歡用String、Integer
從HashMap的語法上來講，一切物件都可以作為Key值，如：Integer、Long、String、Object等，但是在實際作業中，最常用的使用String作為Key值，
-
它們都是final修飾的類，不可變性，保證key的不可更改性，不會存在獲取hash值不同的情況，
-
它們內部已重寫了equals()、hashCode()等方法，遵守了HashMap內部的規范，
-
它們具有自己獨立的特性，它們都放在常量區(快速判斷是否相等)，
3.2 HashMap在什么情況下擴容？
在上面的put方法中有這么一段內容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if (++size > threshold)
resize();
...
}
當map的元素大于threshold = capacity(當前Map的大小) * load factor(默認0.75).
呼叫 resize() 進行擴容
static final int MAXIMUM_CAPACITY = 1 << 30;
final Node<K,V>[] resize() {
...
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
}
...
>>:按二進制形式把所有的數字向左移動對應的位數，高位移出（舍棄），低位的空位補零，如將oldCap向左移動1位，限制：最大不能超過2的30次冪
3.3 為什么擴容是2的n次冪?
HashMap為了存取高效，要盡量較少碰撞，就是要盡量把資料分配均勻，每個鏈表長度大致相同，
例如：hashMap.get("name").hashCode()=773564，
773564 轉為二進制：10111100110110111100
取模運算
取模運算：明顯當hashmap大小不為2的n次冪的時候，哈希值的碰撞就多了起來，
tab[(n - 1) & hash])
hash演算法中，為了使元素分布的更加均勻，很多都會使用取模運算，在hashMap中并沒有使用hash%n這樣進行取模運算，而是使用(n - 1) & hash進行代替，原因是在計算機中，&的效率要遠高于%；需要注意的是，只有容量為2的n次冪的時候，(n - 1) & hash 才能等效hash%n，這也是hashMap 初始化初始容量時必須是2的n次冪的原因，
3.4 為什么要先高16位異或低16位再取模運算?
由于hashcode 和（length-1）運算，length 絕大多數情況小于2的16次方，所以始終是hashcode 的低16位（甚至更低）參與運算，要是高16位也參與運算，會讓得到的下標更加散列，
3.5 HashMap 中的 key 為 定義的物體型別別， 則需實作哪些方法？
//未重寫equals()、hashCode()方法
System.out.println("未重寫equals()、hashCode()等方法");
HashMap<User,String> userMap = new HashMap<>();
User userQin = new User("嬴政",20);
userMap.put(userQin,"秦始皇");
//當你定義的MapUser和put時的資料未發生改變，通過Map.get可以獲取到資料
System.out.println(userMap.get(userQin));//秦始皇
System.out.println("Age20:"+userQin.hashCode());//Age20:1531333864
//當MapUser.age發生改變后，通過Map.get無法獲取資料
userQin.age=25;
System.out.println("Age25:"+userQin.hashCode());//Age25:1531333864
System.out.println(userMap.get(userQin));//秦始皇
userMap.put(new User("劉邦",20),"漢高祖");
System.out.println(userMap.get(new User("劉邦",20)));//null
//重寫了equals()、hashCode()方法
System.out.println("重寫了equals()、hashCode()方法");
HashMap<HMUser,String> hmUserMap = new HashMap<>();
HMUser hmUserLi = new HMUser("李世民",20);
hmUserMap.put(hmUserLi,"唐太宗");
//當你定義的MapUser和put時的資料未發生改變，通過Map.get可以獲取到資料
System.out.println(hmUserMap.get(hmUserLi));//唐太宗
System.out.println("Age20:"+hmUserLi.hashCode());//Age20:807921772
//當MapUser.age發生改變后，通過Map.get無法獲取資料
hmUserLi.age=25;
System.out.println("Age25:"+hmUserLi.hashCode());//Age25:807921777
System.out.println(hmUserMap.get(hmUserLi));//null
hmUserMap.put(new HMUser("朱元璋",20),"明太祖");
System.out.println(hmUserMap.get(new HMUser("朱元璋",20)));//明太祖
-
未重寫equals()、hashCode()方法時:
-
同一個物件屬性發生改變后hashCode值還相同，可以從Map.get中獲取到值，
-
不同物件屬性相同，無法從Map.get中獲取到值，
-
-
重寫equals()、hashCode()方法時：
-
同一個物件屬性發生改變后hashCode也發生變化相同，無法從Map.get中獲取到值，
-
不同物件屬性相同，可以從Map.get中獲取到值，
-
3.6 為什么 HashMap 是非執行緒安全
-
HashMap 寫入時：假如 A 執行緒和 B 執行緒同時進行插入操作，計算出了相同的哈希值對應了相同的陣列位置，A 先寫入一個節點，B 也寫入同一節點，那B的寫入操作就會覆寫 A 的寫入操作>造成 A 的寫入資料丟失，
-
HashMap 擴容時：會新生成一個新的容量的陣列，然后對原陣列的所有鍵值對重新進行計算和寫入新的陣列，之后指向新生成的陣列，當多個執行緒同時進來，檢測到總數量超過門限值的時候就會同時呼叫 resize 操作，各自生成新的陣列，最終只有最后一個執行緒生成的新陣列被賦給該 map 底層，其他執行緒的均會丟失，
反正挺多可能會出現執行緒安全問題，總之 HashMap 是非執行緒安全的，有并發問題時，建議使用 ConcrrentHashMap，
ConcrrentHashMap：
-
底層采用分段的陣列+鏈表實作，執行緒安全，
-
通過把整個Map分為N個Segment，可以提供相同的執行緒安全，但是效率提升N倍，默認提升16倍(讀操作不加鎖，由于Node的value變數是 volatile 的，也能保證讀取到最新的值)，
-
ConcurrentHashMap允許多個修改操作并發進行，其關鍵在于使用了鎖分離技術，
-
有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢后，又按順序釋放所有段的鎖，
-
擴容：段內擴容（段內元素超過該段對應Entry陣列長度的75%觸發擴容，不會對整個Map進行擴容），插入前檢測需不需要擴容，有效避免無效擴容，
鎖分段技術：首先將資料分成一段一段的存盤，然后給每一段資料配一把鎖，當一個執行緒占用鎖訪問其中一個段資料的時候，其他段的資料也能被其他執行緒訪問，
ConcurrentHashMap默認將hash表分為16個桶，諸如get、put、remove等常用操作只鎖住當前需要用到的桶，這樣，原來只能一個執行緒進入，現在卻能同時有16個寫執行緒執行，并發性能的提升是顯而易見的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/413938.html
標籤：其他