注意以下文章可能有描述和理解上的錯誤，如果出現錯誤請到評論區指出，我會第一時間修改問題，也希望文章能解決你的疑惑，
HashMap結構圖
HashMap底層資料結構：Entry陣列+鏈表+紅黑樹（JDK1.8版本） Entry+鏈表（JDK1.7版本）
這里寫目錄標題
- HashMap結構圖
- 代碼分析
- 常見的引數及意義
- 原始碼解釋
- 構造方法
- size函式
- isEmpty函式
- get具體程序函式
- containsKey函式
- put函式
- resize函式
- remove函式
- clear函式
- containsValue函式
- keySet函式
- values函式
- entrySet函式
- 面試常見的問題
代碼分析
常見的引數及意義
//默認的Hash表的長度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//Hash表的最大長度
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//當鏈表的長度為8的時候轉化為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//桶中元素個數小于6的時候紅黑樹轉換為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//只有當陣列的長度大于等于64并且鏈表個數大于8才會轉換為紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
//Hash表
transient Node<K,V>[] table;
//遍歷的時候使用回傳一個K-V集合
transient Set<Map.Entry<K,V>> entrySet;
//表中K-V的個數
transient int size;
//對集合的修改次數，主要是后面出現的集合校驗
transient int modCount;
//閾值當size大于threshold時就會進行resize
int threshold;
//加載因子
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;
//回傳的是2的整數次冪
this.threshold = tableSizeFor(initialCapacity);
}
//指定HashMap的容量
public HashMap(int initialCapacity) {
//呼叫如上的雙參建構式
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//無參建構式
public HashMap() {
//初始化加載因子為默認的加載因子
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//構造一個映射關系與指定 Map 相同的新 HashMap，
public HashMap(Map<? extends K, ? extends V> m) {
//初始化加載因子為默認的加載因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
//構造的程序函式
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//獲取m集合中元素個數
int s = m.size();
//如果m集合元素個數是0個那么下面這些操作也就沒有必要了
if (s > 0) {
if (table == null) { //表示的拷貝建構式呼叫putMapEntries函式，或者是構造了HashMap但是還沒有存放元素
//計算的值存在小數所以+1.0F向上取整
float ft = ((float)s / loadFactor) + 1.0F;
//將ft強制轉換為整形
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果計算出來的值大于當前HashMap的閾值更新新的閾值為2次方
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)//如果Map集合元素大于當前集合HashMap的閾值則進行擴容
resize();
//將Map集合中元素存放到當前集合中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
size函式
//回傳key-val的數量
public int size() {
return size;
}
isEmpty函式
//當前的集合是否為null
public boolean isEmpty() {
return size == 0;
}
get具體程序函式
//根據key獲取對應的val
public V get(Object key) {
Node<K,V> e;
//通過hash值，key找到目標節點再回傳對應的val
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//獲取key對應的節點
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果集合為空和對應的下標陣列中的值為空直接回傳null
//first = tab[(n - 1) & hash]陣列的長度是2n次方減1后對應位全部變為1，這樣為與操作永遠都會在陣列下標范圍內不會越界
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // 如果第一個節點hash與對應hash相等，并且key也相等則回傳當前節點
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//第一個節點的下一個節點不為null
if ((e = first.next) != null) {
//判斷節點是否為樹形
if (first instanceof TreeNode)
//在樹形結構中查找節點并回傳
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {//通過do...while結構遍歷找對應key的節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//找到節點并回傳
return e;
} while ((e = e.next) != null);
}
}
//未找到對應的節點
return null;
}
containsKey函式
//查看是否包含指定key
public boolean containsKey(Object key) {
//通過getNode回傳是否為null判斷是否存在key
return getNode(hash(key), key) != null;
}
put函式
在此之前先看一下put的程序
//呼叫putVal向當前集合中存放元素并回傳對應的val
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//存放對應的key-val
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果當前集合為null則將集合擴容并且將新的存放結構賦值給tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//找到key存放的鏈表，如果為空直接將當前節點存放鏈表在第一個位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //當前為鏈表不為null
Node<K,V> e; K k;
//表示當前鏈表第一個位置key已經存在，將當前節點賦值給e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//查看當前的節點是否屬于樹形結構如果是則在TreeNode中查找并將賦值給e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//找到當前存放位置節點的最后一個節點的next并將當前要插入的節點插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 鏈表的長度為8的時候轉化為紅黑樹減一是因為元素從0開始
treeifyBin(tab, hash);
//跳出死回圈
break;
}
//表示的是當前鏈表已經存在當前要插入的key，HashMap不存在重復的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//將節點后移
p = e;
}
}
if (e != null) { // 當前節點不為null將e.val存放在oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//不管oldValue是否為null都會發生value賦值給e.value
//當出現重復的key之后上面會將節點保存給e并未修改新的val值，在此更新
e.value = value;
//將結點向后調整到最后面
afterNodeAccess(e);
//如果為null回傳null，不為null回傳對應的val
return oldValue;
}
}
//++modCount對其集合操作的次數+1
++modCount;
if (++size > threshold)//如果在放入元素以后大于閾值則進行2倍擴容
resize();
afterNodeInsertion(evict);
return null;
}
resize函式
//將集合擴容
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;//將整型最大的值賦值給threshold
return oldTab;
}
//當前集合陣列長度擴大二倍賦值給newCap小于MAXIMUM_CAPACITY
//并且集合的容量大于等于默認容量將當前閾值擴大二倍賦值給新的閾值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//若沒有經歷過初始化，通過建構式指定了initialCapcity，將當前容量設定為大于它最小的2的n次方
else if (oldThr > 0)
newCap = oldThr;
else { // 初始的時候長度和閾值都使用默認值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//重新計算threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新當前集合閾值
threshold = newThr;
//從這里開始便是將oldTab資料重新hash放入擴容后的newTab
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//將table指向的oldTab指向newTab
table = newTab;
if (oldTab != null) {
//遍歷哈希表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//當前鏈表是否為null、并且將就鏈表賦值給e
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//將原來位置的鏈表置為null方便垃圾回收
if (e.next == null)//鏈表的長度為1直接將鏈表中的一個節點重新hash存放到相應的位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //表示節點型別為樹形結構
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //鏈表是非樹形結構，并且節點數量是大于1
//將鏈表拆分為兩個子鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do { //通過do...while遍歷鏈表
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) {//在新表的j位置存放鏈表
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//在新表的j+oldCap位置存放鏈表
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
remove函式
// 移除指向key回傳對應的val
public V remove(Object key) {
Node<K,V> e;
//回傳如果為慷訓傳null否則回傳e.val
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;
//常規的判斷表不為null，key有對應的存盤位置
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;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//表示的是key存盤在當前鏈表的第一個位置
node = p;
else if ((e = p.next) != null) {//表示的是鏈表的長度大于1
if (p instanceof TreeNode)//判斷是否是樹的實列
//回傳對應key在紅黑樹存盤的位置
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {//當前結構為鏈表
do {//遍歷鏈表
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {//找到對應的節點保存并跳出回圈
node = e;
break;
}
//將節點后移
p = e;
} while ((e = e.next) != null);
}
}
//表示要洗掉的key存在并且找到
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)//表示的鏈表中的第一個節點
tab[index] = node.next;
else
p.next = node.next;//移除節點
++modCount;//操作+1
--size;//長度-1
afterNodeRemoval(node);
//回傳節點
return node;
}
}
return null;
}
clear函式
//清除集合中的所有key-value
public void clear() {
Node<K,V>[] tab;
//集合操作+1
modCount++;
if ((tab = table) != null && size > 0) {//表不為null才進行遍歷
size = 0;
for (int i = 0; i < tab.length; ++i)//遍歷集合所有元素都置為null，方便垃圾回收
tab[i] = null;
}
}
containsValue函式
//查看集合是否包含指定value
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {//表不為null
for (int i = 0; i < tab.length; ++i) {//遍歷陣列
for (Node<K,V> e = tab[i]; e != null; e = e.next) {//遍歷鏈表
if ((v = e.value) == value ||
(value != null && value.equals(v)))
//存在指定的value直接回傳true
return true;
}
}
}
//集合中不存在指定value回傳false
return false;
}
keySet函式
//回傳key的所有集合set
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
values函式
//回傳所有的value集合
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
entrySet函式
// 回傳所有的key-value集合
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
面試常見的問題
-
為什么HashMap默認的長度為2的整數次冪?
就是因為獲取索引h&(length-1)可以保證散列的均勻，避免不必要的hash沖突，
-
為什么加載因子是0.75？大了會怎么樣？小了會怎么樣？
首先加載因子是表示hash表的填滿程度，當為0.75的時候是在對提高空間利用率和減少查詢成本的折中，當大于0.75的時候填滿的元素越多，空間利用率越高，但是沖突的概率變大；當小于0.75的時候填滿的元素越少，空間利用率越低，但是沖突的概率變小，
-
什么是哈希沖突？如何解決？
哈希沖突是指hash出來的地址被其他元素所占用；
解決的方法
1.鏈地址法
解決的思路就是當出現沖突的時候將沖突的元素加入當前的鏈表之中
2.開放地址法
開放地址法也稱之為再散列，
思路：如果映射的地址被占用了，在哈希函式值的基礎上加上指定數值，這樣就可以把沖突的地址給錯開，然后重新開辟新的地址用來存盤，根據增量值的不同，分為線性探測再散列和二次探測再散列
3.再哈希法
這種方法就是構造多個不同的哈希函式，當哈希地址Hi=RH1(Key)發生沖突時，再計算Hi=RH2(Key)…直到哈希不沖突，這樣的方法增加了計算的時間，
4.建立公共溢區
就是哈希表分成了兩個表：一個是基礎表，另外一個則是溢位表，凡是與基礎表發生沖突的資料都會被添加到溢位表， -
什么是擾動函式？怎么設計的？為什么這個設計？
擾動函式是hash函式拿到k的hashcode值，這個值是一個32位的int，讓高16位與低16位進行異或，
理論上來說字串的hashCode是一個int型別值，那可以直接作為陣列下標了，且不會出現碰撞，但是這個hashCode的取值范圍是[-2147483648, 2147483647]，有將近40億的長度，誰也不能把陣列初始化的這么大，記憶體也是放不下的，
混合原始哈希碼的高位和低位，以此來加大低位的隨機性，這樣設計在一定的程度上減少了hash碰撞，優化了散列的效果 ， -
JDK1.8在對HashMap較1.7有什么優化？
1.首先是最重要的就是底層的資料結構，1.7的時候底層資料結構是陣列+鏈表；而在1.8的時候變成了陣列+鏈表+紅黑樹
2.在哈希上1.7擾動四次，1.8做了一次擾動，可以提高效率
3.1.7在進行resize擴容的時候是重新哈希，1.8的時候采用的是索引位置不變或者就是就哈希表的容量+當前索引，
4.1.7采用插入方式是頭插法，1.8采用的是尾插法， -
為什么1.8擴容不用重新哈希？
-
HashMap執行緒安全嗎？為什么不安全？怎么解決不安全？
首先HashMap是執行緒不安全的，JDK1.7的時候采用頭插法，多執行緒同時插入的時候，A執行緒在插入節點B，B執行緒也在插入，遇到容量不夠開始擴容，重新hash，放置元素，采用頭插法，后遍歷到的B節點放入了頭部，這樣形成了環，JDK1.8采用尾插法，會造成兩種情況兩個執行緒同時插入只有一個成功插入，還有就是可能會造成兩次resize(++size > threshold) ，解決的方案：一、使用HashTable效率比較差，二、使用ConcurrentHashMap比較常用的，三、使用Collections.synchronizedMap() 以上三種執行緒安全，
-
HashMap內部節點是有序的嗎？
不是有序的，有序的Map集合有LinkedHashMap、TreeMap
-
HashMap一般采用什么作為key？
HashMap一般采用String、Integer 等類作為key、因為這些類底層已經重寫了hashcode、equals方法，用的是final修飾類在多執行緒情況下相對安全，
-
為什么重寫equals還要重寫hashcode？
比如HashMap中不允許存在相同的key，當重寫了equals方法沒有重寫hashcode方法，當兩個物件中的值相同，但是他們hashcode不同會造成比如
class newInstance1 = new class(1);
class newInstabce2 = new class(2);
以上的比較物件的時候hashcode不同，equal方法比較回傳false；但是重寫Hashcode后，可以達到回傳true，
如果看完覺得得到幫助就留下你的一鍵三連，謝謝 注意如果有錯誤的地方評論區提出來我立即更正謝謝大佬的指正，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/282611.html
標籤：java
下一篇：用戶登錄功能的實作