Java集合-08HashMap源碼解析及使用實例
- 2019 年 10 月 8 日
- 筆記
HashMap 簡介
HahMap是基於hash表的Map介面實現。該實現提供所有可選的映射操作，且允許key和value為null。同時
它不是執行緒安全以及不能保證有序。初始容量(initial capacity)和載入因子(initial capacity)是影響
HashMap的兩個因素。容量表示hash表中桶(buckets)的數量，初始容量就是表示hash表在創建時候容量大小。
載入因子就是hash表在其容量自動增加時候被允許填滿程度的指標。當hash表中條目數超過當前hash表容量
與載入因子的乘積時候，hash表將進行rehash操作(重建內部數據結構)，從而hash表的桶數目大約增長兩倍。
通常載入因子為0.75，這個值是時間和空間消耗的一個平衡值。過高的值降低了空間消耗但是卻增加了查詢成本。
在設置初始化容量時候需要考慮Map中的條目數和載入因子，以便減少rehash操作。如果初始容量的值大於最大條目數除以載入因子，
將不會發生rehash操作。
如果你要使用HashMap存儲映射關係時候，有一個充足的容量是比讓HashMap自動rehash來增加容量更加有效率。需要提醒的是
使用具有相同的hashCode()的鍵是會降低hash表的表現。為了避免hash碰撞，鍵如果是Comparable的話，對解開結有一定的幫助。
因為HashMap不是執行緒安全的，在多執行緒並發編程時候，如果有至少一個執行緒在對HashMap結構修改(結構修改指的是添加
或者減少映射關係，對於原來有的一個映射改變它的值不是結構上的修改)，必須保證同步化操作。通常來說使用某一對象加鎖，
如果沒有這麼一個對象的話，該HashMap需要用Collections#synchronizedMap對其重新包裹
HashMap 構造函數
public HashMap()
定義一個初始容量為16，載入因子為0.75的HashMap
public HashMap(int initialCapacity)
定義一個指定初始容量，載入因子為0.75的HashMap
public HashMap(int initialCapacity, float loadFactor)
定義一個指定初始容量和載入因子的HashMap
public HashMap(Map<? extends K, ? extends V> m)
定義一個初始容量為不小於(m.size()/0.75+1)的2的最小指數，載入因子為0.75,包含了m中映射關係的HashMap
HashMap 結構圖
- table
用於存儲數據
- entrySet
entrySet()方法的快取值
- size
map中映射個數
- modCount
fail-fast判斷使用
- threshold
resize操作的闕值，大小為capacity * load facto
- loadFacto
載入因子
HashMap 源碼分析
- Node
- hash表中每個節點存儲對象
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; } //省略set、get等方法 }
- 擴容方法
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//擴容前的hash表指向oldTab 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"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) {//原來的數據移動到新的容器裡面 for (int j = 0; j < oldCap; ++j) { 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 TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve orde 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; }
- 添加方法
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) {//hash函數，用於索引定位 int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;//存儲數據Node沒有初始化，此時初始化 if ((p = tab[i = (n - 1) & hash]) == null)//(n-1)&hash用於定位，若為null，表明Node數組該位置沒有Node對象，即沒有碰撞 tab[i] = newNode(hash, key, value, null);//對應位置添加Node對象 else {//表明對應位置是有Node對象的，hash碰撞了 Node<K,V> 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<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) // -1 for 1st//鏈表長度大於TREEIFY_THRESHOLD值，轉換為紅黑樹結構 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//如果找到重複的key，判斷該節點和要插入的元素key是否相等，如果相等，出循環 break; p = e;//為了遍歷，和e = p.next結合來遍歷 } } if (e != null) { // existing mapping for key//key映射的節點不為空 V oldValue = e.value;//取出節點值記錄為老的節點值 if (!onlyIfAbsent || oldValue == null)//如果onlyIfAbsent為false，或者老的節點值為null，賦予新的值 e.value = value; afterNodeAccess(e);//訪問後回調 return oldValue; } } ++modCount;//結構性修改記錄 if (++size > threshold)//判斷是否需要擴容 resize(); afterNodeInsertion(evict);//插入後回調 return null; }
- put流程
1.通過hash函數計算key的hash值，調用putVal方法
2.如果hash表為空，調用resize()方法創建一個hash表
3.根據hash值索引hash表對應桶位置，判斷該位置是否有hash碰撞
3.1 沒有碰撞，直接插入映射入hash表
3.2 有碰撞，遍歷桶中節點
3.2.1 第一個節點匹配，記錄該節點
3.2.2 第一個節點沒有匹配，桶中結構為紅黑樹結構，按照紅黑樹結構添加數據，記錄返回值
3.2.3 第一個節點沒有匹配，桶中結構是鏈表結構。遍歷鏈表，找到key映射節點，記錄，退出循環。
沒有則在鏈表尾部添加節點。插入後判斷鏈表長度是否大於轉換為紅黑樹要求，符合則轉為紅黑樹結構
3.2.4 用於記錄的值判斷是否為null，不為則是需要插入的映射key在hash表中原來有，替換值，返回舊值putValue方法結束
4.結構性修改記錄，判斷是否需要擴容
- get方法
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {//hash表存在且長度大於0且對應的key定位的桶不為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<K,V>)first).getTreeNode(hash, key);//按照紅黑樹結構查找 do {//遍歷鏈表，查詢hash 和equals相等的，有則返回，一直到鏈尾 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
- 修改方法
public V replace(K key, V value) { Node<K,V> e; if ((e = getNode(hash(key), key)) != null) {//根據key查詢 有則修改 V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; }
- 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; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {//hash表存在且長度大於0且對應的key定位的桶不為null Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p;//判斷第一個節點，符合記錄 else if ((e = p.next) != null) {//第一個節點不符合 if (p instanceof TreeNode)//判斷是否為紅黑樹結構 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); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {//判斷是否符合有要移除的node if (node instanceof TreeNode)//為紅黑樹結構 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p)//第一個節點就是符合的 tab[index] = node.next;//刪除第一個節點(第一個節點指向null，或者指向原來第二個節點) else p.next = node.next;//鏈表結構，指向後面的一個節點 ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
HashMap遍歷
遍歷HashMap鍵值對
根據map.entrySet()獲得鍵值對Set集合，後續遍歷
for (Map.Entry<Integer, String> entry : maps.entrySet()) { System.out.println(entry.getKey()+":"+entry.getValue()); }
遍歷HashMap的鍵視圖
根據maps.keySet()獲得HashMap的鍵的Set集合，後續遍歷
for (Integer integer : maps.keySet()) { System.out.println(integer); }
遍歷HashMap的值視圖
根據maps.values()獲得HashMap的鍵的Collection集合，後續遍歷
for (String value : maps.values()) { System.out.println(value); }
喜歡的給個支援，謝謝
