摘要:否則,繼續判斷頭節點是否是的實例,是一個紅黑樹,若是,則直接在樹中插入。在中有一個屬性為,這是一個閾值,若數量超過它,鏈表會轉化為紅黑樹,小于它則會換回鏈表。所以同時用到了數組,鏈表,紅黑樹這三種數據結構。
1. HashMap中Node類:
static class Nodeimplements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node 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) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry,?> e = (Map.Entry,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
重寫hashCode,key和value的hashcode取異或。
重寫equals,當為同一個對象或是同一個key和同一個value都認為這兩個對象相等。
2.散列值的計算static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
與無符號右移的自己異或同時兼顧了hash高16位和低16位,讓散列值更散。
3. 關注 get(Object key)public V get(Object key) { Nodee; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node getNode(int hash, Object key) { Node [] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode )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; }
可以看出,get()是拿著key的hash和key去找的值。
在getNode()中先是一系列判斷和賦值,然后通過下標找定位到key在table中的位置
定位的方式:(n - 1) & hash,這樣取出的值總是小于table長度n的。
然后對比key是否相等,相等就返回,不相等則判斷是否是紅黑樹存儲結構,若是則在紅黑樹上查找。
若不是則在鏈表結構上查找。
4.核心put(K key, V value)public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node 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 { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode )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) // -1 for 1st 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; }
首先調用了putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict),
第一步做初始化工作。
然后,定位到table沒有沖突,則直接存到table上。
若是沖突了,則判斷key是否相等,若相等則,直接將舊德的Node覆蓋。
否則,繼續判斷頭節點是否是TreeNode的實例,TreeNode是一個紅黑樹,若是,則直接在樹中插入。
如果不是紅黑樹,插到鏈表的尾部。
在hashmap中有一個屬性為TREEIFY_THRESHOLD,這是一個閾值,若數量超過它,鏈表會轉化為紅黑樹,小于它則會換回鏈表。所以hashMap同時用到了數組,鏈表,紅黑樹這三種數據結構。
每次新添一個節點都會判斷是否需要擴容。
5. 擴容機制resize()首先涉及三個成員變量:
capacity:容量
loadFactor:裝載因子(0-1之間)
threshold:判斷是否需要擴容的標志threshold = capacity * loadFactor
所以裝載因子控制著HashMap沖突比例。
每次擴容都擴大到之前的兩倍。
擴容會重新建table等變量,因此開銷比較大。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74231.html
摘要:簡介繼續分析源碼,上一篇文章把的分析完畢。本文開始分析簡單的介紹一下。存儲的元素是無序的并且允許使用空的元素。 1.簡介 繼續分析源碼,上一篇文章把HashMap的分析完畢。本文開始分析HashSet簡單的介紹一下。 HashSet是一個無重復元素集合,內部使用HashMap實現,所以HashMap的特征耶繼承了下來。存儲的元素是無序的并且HashSet允許使用空的元素。 HashSe...
摘要:當前的部分代碼狀態超時再縮小了范圍以后,進一步進行排查。函數是一個很簡單的一次性函數,在第一次被觸發時調用函數。因為上述使用的是,而非,所以在獲取的時候,肯定為空,那么這就意味著會繼續調用函數。 有時候,所見并不是所得,有些包,你需要去翻他的源碼才知道為什么會這樣。 背景 今天調試一個程序,用到了一個很久之前的NPM包,名為formstream,用來將form表單數據轉換為流的形式進行...
摘要:前言本文的目的是閱讀理解的源碼,作為集合中重要的一個角色,平時用到十分多的一個類,深入理解它,知其所以然很重要。 前言 本文的目的是閱讀理解HashMap的源碼,作為集合中重要的一個角色,平時用到十分多的一個類,深入理解它,知其所以然很重要。本文基于Jdk1.7,因為Jdk1.8改變了HashMap的數據結構,進行了優化,我們先從基礎閱讀,之后再閱讀理解Jdk1.8的內容 HashMa...
摘要:部分源碼分析小記底層數據結構底層的數據結構就是數組,數組元素類型為類型,即可以存放所有類型數據。初始容量大于初始化元素數組新建一個數組初始容量為為空對象數組初始容量小于,拋出異常無參構造函數。 JDK1.8 ArrayList部分源碼分析小記 底層數據結構 底層的數據結構就是數組,數組元素類型為Object類型,即可以存放所有類型數據。我們對ArrayList類的實例的所有的操作底層都...
閱讀 3916·2021-11-16 11:44
閱讀 3116·2021-11-12 10:36
閱讀 3373·2021-10-08 10:04
閱讀 1257·2021-09-03 10:29
閱讀 391·2019-08-30 13:50
閱讀 2605·2019-08-29 17:14
閱讀 1735·2019-08-29 15:32
閱讀 1081·2019-08-29 11:27