溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Java HashMap使用源碼分析”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java HashMap使用源碼分析”吧！
首先我們先看一下 HashMap 有哪些成員變量
/** * 默認的初始大小，16，值必須是 2 的冪值 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大值，必須是 2 冪值且 小于等于 2 的30 次冪 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默認加載因子，0.75，就是map里的元素值超過 75% 就會觸發擴容 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; //下面還有三個樹化的參數 //如果哈希值相同的元素超過 8 個，則樹化 static final int TREEIFY_THRESHOLD = 8; //樹的節點小于 6 個，則轉成鏈表 static final int UNTREEIFY_THRESHOLD = 6; //如果 map 的元素小于 64，即便是 哈希值相同的元素超過 8 個了，也不樹化，會擴容 static final int MIN_TREEIFY_CAPACITY = 64;
下面還有一個 Node 類，這個類就是 HashMap 存儲元素的容器，其實很簡單
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//... ...
}沒有多少復雜的內容，類似于鏈表的Node節點，key、value、next，因為大量的地方都需要用到對象的 hash 值，所以又記錄了下 key 的 hash 值。
繼續往下看
//求 key 的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}也沒什么好說的，就是通過對象的 hashCode 計算出一個 int 值。
下面有個 comparableClassFor 方法，這個方法的主要是判斷入參 x 是否實現了 Comparable 接口。不過寫的格式有點緊湊，我們需要展開以下。
static Class<?> myComparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c = x.getClass();
// 獲取 x 實現的所有接口
Type[] ts = c.getGenericInterfaces();
Type[] as;
Type t;
ParameterizedType p;
//如果 x 是 String 類型 直接返回
if (c == String.class) {
return c;
}
if (ts != null) {
// 遍歷實現的所有接口
for (int i = 0; i < ts.length; ++i) {
t = ts[i];
// 如果接口有泛型
if (t instanceof ParameterizedType) {
p = (ParameterizedType) t;
// 如果泛型對象是 Comparable
if (p.getRawType() == Comparable.class) {
as = p.getActualTypeArguments();
// 只有一個泛型參數，且參數類型是 x.class
if (as != null && as.length == 1 && as[0] == c) {
return c;
}
}
}
}
}
}
return null;
}舉個例子:
class MyTest implements Comparable<MyTest> {}
會返回 MyTest.class
class MyTest implements Comparable<Integer> {}
會返回 null這個方法就結束了，如果還是不能理解，可以將代碼復制出來，打個斷點跑一下。繼續往下看。
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}這個方法有意思，注釋是說，如果 x 是 kc 的類型，返回 k.compareTo(x) （k 是篩選過的比較類）。如果你查找下這個方法的使用地方就會發現，kc 這個參數就是上面 comparableClassFor 返回的類型。
這么一看是不是就清晰了？ comparableClassFor(x) 拿到類型，然后傳入 compareComparables(kc,k,x) 去比較。
下面又是一個方法：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}這個方法也很有意思，看著很復雜，其實功能很簡單，返回第一個大于等于 cap 的 2 的冪值。還是那句話， main 方法試試就知道了。不多說。
再往下就是一些變量了。其中最核心的變量就是 table
transient Node<K,V>[] table;
通過注釋我們就可以知道這個是存儲 HashMap 元素的數組，在第一次使用時被初始化，并且根據需要調整大小，長度適中是 2 的冪。
table 數組就是存儲 HashMap 元素的底層結構，具體怎么存儲我們后面再看。不過需要注意的是這個變量使用了一個 transient 修飾符，這在我們平常的編碼中是很少見到的。這個修飾符的作用是在序列化時跳過該屬性。是跟 Serializable 相對應的。其實就是當一個 HashMap 對象被序列化到文件中時，其中的元素是沒有寫到文件里的。所以通過反序列化也是拿不到元素的。
我們知道了它的功能，但是 HashMap 為什么要這么做呢？其實這個是跟 HashMap 的 put 方法有關系，我們稍后再說。繼續往下看。
下面還有一些其他的屬性，其中有兩個比較重要。
int threshold; final float loadFactor;
threshold 是下次擴容時 HashMap 的容量。 loadFactor 是加載因子，當 HashMap 的容量達到總容量的一定比例就會觸發擴容。這兩個字段都跟擴容有關，等看到擴容時再說。
再往下就是幾個構造方法了，前面三個構造方法都只是在確定 threshold、loadFactor 這兩個屬性的默認值。沒有什么好說的
threshold 如果初始化時沒有傳值就是 0 ，loadFactor 默認值是 DEFAULT_LOAD_FACTOR = 0.75f。也就是說，如果 HashMap 的當前容量達到總容量的 75% 就會觸發擴容。
后面還有一個構造方法是傳入了一個 Map 集合，它會把入參中集合里的元素 put 到當前的 HashMap 集合中。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}這個構造方法首先初始化了 loadFactor 屬性，然后調了putMapEntries 方法，這個方法就在下面。同樣格式有點亂，沒關系，我們先調整下格式。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s <= 0){
return;
}
if (table == null) {
float ft = ((float)s / loadFactor) + 1.0F;
int t;
if (ft < (float)MAXIMUM_CAPACITY){
t = (int)ft;
}else {
t = MAXIMUM_CAPACITY
}
if (t > threshold){
threshold = tableSizeFor(t);
}
}
else if (s > threshold){
resize();
}
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);
}
}如果 map 里沒有元素，直接結束。因為我們是構造方法進入到這個方法里的，所以 table 一定為 null，然后計算了一下 ft ，表示放入 m 個元素后，HashMap 的最大容量，（如果 s = 75,那 ft = 101）。
然后計算了一下 t 就是 map 需要的最大容量。并且判斷一下是否超限。然后判斷了一下是否要更新 threshold ，因為我們是構造方法進來的，所以一定是需要更新的。更新結束后就是 for 循環依次調用 putVal 將元素放入到當前的 HashMap 里。
然后我們跳到 putVal 方法。這個方法的格式依然不太好閱讀，我們需要修改下。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K, V> e;
K k;
if (p.hash == hash) {
k = p.key;
if (k == key || key != null && key.equals(k)) {
e = p;
}
} else {
if (p instanceof HashMap.TreeNode) {
e = ((HashMap.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);
if (binCount >= TREEIFY_THRESHOLD - 1) {
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;
}首先判斷了 table 是否進行了初始化，沒有的話進行 resize， 這個方法我們一會再看。它的作用就是返回一個 Node 數組，數組的長度就是 threshold。初始化好之后就是判斷下這個數組的(n - 1) & hash 位置是否有值，沒有值的話直接創建一個 Node 存到數組里就結束了。其實 (n - 1) & hash 相當于 hash % (n-1) 的作用，但是與操作的效率比取模的效率高。二者達到的效果是一樣的。
如果有值，并且 key 相等，說明是同一個元素，這個時候 e 就是 HashMap 里的元素，后面對 e 的判斷就會直接返回 e 對應的 value。
如果 key 不相等，說明發生了 hash 沖突。兩個 hash 值不一樣的元素應該存儲到數組的同一個位置。這個時候判斷了一下 Node 的類型。如果是 TreeNode 那么調用 putTreeVal 方法。
如果不是，則依次遍歷當前位置節點的 next 指針，直到為空，插入新節點。其實就是講新節點掛到了已當前節點為表頭的鏈表尾部。插入成功之后判斷了一下鏈表的長度，如果需要則進行樹化。將當前鏈表轉成一個紅黑樹。這個主要是解決鏈表太長，查詢效率低的問題。而且在遍歷鏈表期間依然判斷了 key 是否相等，相等則直接返回舊元素的 value。
好像也不是很難，這個就是 HashMap 最核心的方法之一了。從這個方法中也可以知道，HashMap 的底層存儲結構是一個數組。如果發生 hash 沖突后，會采用鏈表的方式存儲，當鏈表長度過長時，會將鏈表轉成紅黑樹結構，提高查詢效率。
下面我們看一下resize() 方法
final HashMap.Node<K, V>[] resize() {
HashMap.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"})
HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.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 HashMap.TreeNode)
((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
HashMap.Node<K, V> loHead = null, loTail = null;
HashMap.Node<K, V> hiHead = null, hiTail = null;
HashMap.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 數組中的元素超過一定的數量后，對 table 數組進行擴容，以便減少 hash 碰撞發生的概率。 最前面一大串的 if 、else 判斷主要是為了確定兩個變量的值 newCap 和 newThr 。newCap 是指擴容后新的 table 數組的長度。newThr 是指新數組的元素超過多少時需要擴容。
計算的方式分幾種場景。第一種 oldCap > 0: 這種是正常擴容，oldTable 已經有元素了，而且元素的數量也達到了擴容的數量。這時 newCap 和 newThr 是原來數值的 2 倍（<< 是右移操作） 而且判斷了下是否超過了最大值。如果 oldCap 已經大于等于最大值了，那直接把下次擴容的閾值調整到最大就結束了，因為 table 數組已經無法擴容了。
(newCap = oldCap << 1) < MAXIMUM_CAPACITY 這一行代碼很有意思它的執行邏輯是，先將 oldCap 右移一位后的數值賦值給 newCap，然后判斷 newCap 是否超過了 MAXIMUM_CAPACITY 。有意思的點在于，它沒有關注 newCap 的溢出情況！！這個其實也是 HashMap 的的容量永遠都是 2 的整數次冪的原因。因為，把一個2 的整數次冪的數值右移一位后，依然是一個2 的整數次冪，而 MAXIMUM_CAPACITY 就是允許的最大的 2的整數次冪。因為之前已經判斷過是否等于 MAXIMUM_CAPACITY 了。所以，oldCap 右移后，最大只能是等于 MAXIMUM_CAPACITY ，不會溢出。而且，當 newCap 等于 MAXIMUM_CAPACITY 是沒有對 newThr 賦值的，對 newThr 賦值的邏輯是在下面的 if (newThr == 0) 的地方。
第二個場景 else if (oldThr > 0) 執行到這個 if 里的情況是，初始化的時候傳了 initialCapacity 這個參數。還記得之前初始化時 threshold 的賦值邏輯么？
this.threshold = tableSizeFor(initialCapacity)
當初始時傳了 initialCapacity 參數，在第一次 put 操作時，就會觸發首次擴容（或者說初始化 table 數組）。
這里有個小知識點：我們在平時寫代碼使用到 HashMap 時，為了提高效率，不讓 HashMap 觸發擴容，都會指定 HashMap 的容量，比如：
Map<String, String> map = new HashMap<>(40);
這個時候我們往 Map 里放 5 個元素，應該是只擴容一次即初始化 table 那次。好像沒有什么問題。這時因為在第一次初始化時 tableSizeFor 這個參數返回的是大于等于 initialCapacity 的最小的 2 的整數冪的值。比如你傳 50，初始化的結果是 64 。而默認的 loadFactor 是 0.75，也就是在元素達到 48 時才會觸發擴容。
但是，如果你給的值是 48 以上的呢? 或者說恰好是 64 的時候。這個時候就會在插入第 49 個元素時再次觸發一次擴容。所以，如果你明確的知道元素的容量的話，可以初始化 2 倍元素容量的 HashMap ，這樣就不會觸發兩次擴容了。
繼續往下說，計算好 newCap 和 newThr 的值后，就創建了一個 newTab，然后就是遍歷 oldTab 不斷的將元素轉移到 newTab 里去。
首先將 oldTab 的引用置為 null，避免內存泄露。然后當前元素會有三種情況： 第一種 e.next == null 就是當前位置只有這一個元素，沒有發生 hash 沖突。這種最簡單，直接放到 newTab 里就可以了。 第二種 e instanceof TreeNode，就是發生了 hash 沖突，且已經把鏈表轉成了紅黑樹的結構了（還記的 putVal 方法么？）。這種就需要按照紅黑樹的操作，把 e 這個節點從 oldTab 上摘下來，掛到 newTab 上去（有點復雜，已經超過了本文的內容。需要了解的可以搜一下紅黑樹）。 第三種，就是發生了 hash 沖突，但是存儲結構還是鏈表的情況。這種情況如果按照正常的思路的話，無非就是遍歷鏈表，依次將鏈表的元素放入到 newTab 就好了。但是這樣就會有一個問題，就是鏈表上的元素依然有可能出現 hash 沖突，如果在遍歷鏈表期間多個元素發生了 hash 沖突怎么辦呢？
很顯然，從代碼上來看，并沒有按照我們的思路來。代碼邏輯是根據元素的 hash 值將一個鏈表分成了兩個鏈表。loHead 和 hiHead。等拆分完成后，直接將鏈表的表頭保存到了 newTab 的兩個元素里。是不是很神奇？？就好像是在說，擴容前發生了 hash 沖突的元素，那么擴容后也有可能發生 hash 沖突，并且這些元素一定應該放到 newTab[j] 或者是 newTab[j+oldCap] 這兩個位置。事實就是這樣！！
其實，你可以寫代驗證下，擴容前發生 hash 沖突的元素，如果 (e.hash & oldCap) == 0 那么它一定會落在 newTab[j]上，否則一定落在 newTab[j+oldCap] 上。數學就是這么完美~~
好了，resize()方法到這里就結束了。我們回到 putMapEntries() 方法這里繼續往下看。
再往下，szie() 和 isEmpty() 都沒有什么好說的，下面是 get(Object key) 方法，這個是 HashMap 最常用的方法之一。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}好像也沒有特別復雜，計算 key 的 hash 值，然后通過 getNode 方法獲取 node 對象，找不到就返回 null，找到了就返回對應的 value。getNode()方法就在下面。
如果你對 putVal() 方法已經非常熟悉了，其實 getNode() 就非常清晰了。首先判斷了 table 是否為空，不為空的話就通過 hash 找對應位置的元，如果對應的位置有值，就判斷 key 是否相等。相等直接返回。
如果不相等，則判斷當前位置是否有其他元素，如果是 TreeNode 則從紅黑樹里找，如果是鏈表則遍歷鏈表找。
這里需要注意下，還記得之前我們說過 table 這個變量加了 transient 修飾符么，就是為了不讓 table 元素進行序列化。其實是跟hash(key) 這個方法有關系。你可以翻看下hash() 這個方法，里面有這樣一段 h = key.hashCode()。這里的 hashCode() 你找到它的定義會發現是下面這樣的,
public native int hashCode();
這是一個本地方法。這個方法在不同的 JVM 上可能會有不同的實現，所以，就有可能出現，序列化前和序列化后的對象 hashCode() 方法返回的值不同。但是在序列化后，HashMap 保存在 table 中的位置沒有變，就會出現找不到的情況，這就是 HashMap 中的一些元素不能序列化的原因。
繼續往下就沒有什么好說的了，剩下的除了像 clear()、remove() 這種比較簡單的方法外，就剩一個最復雜的treeify和untreeify。這個是 HashMap 里最復雜的部分，都是 TreeNode 里的方法，已經超出了本文的內容。
感謝各位的閱讀，以上就是“Java HashMap使用源碼分析”的內容了，經過本文的學習后，相信大家對Java HashMap使用源碼分析這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
