摘要:當鏈表長度即將超過閥值,會把鏈表轉化為紅黑樹。然后再判斷是鏈表還是紅黑樹如果值相同,并且相同表示數組中第一個元素即為相同的將數組中第一個元素賦值給如果當前元素類型為表示為紅黑樹,返回待存放的。
前提:學習HashMap的底層代碼之前,首先要對數據結構要個大致的了解。其中重點了解數組,鏈表,樹的概念和用法。
一.圖示分析HashMap的結構(1)圖示為JDK1.8之前的HashMap結構。數組+鏈表,數組中的元素為鏈表的頭節點。如果不同的key對應相同的hash值,則會在頭節點后形成鏈表。
通過代碼的實現,我們可以分析出:如果在儲存數據時,某一個鏈表過長,則會影響查詢性能。(下面會分析put和get方法,解釋鏈表過長如何影響性能)
(2)JDK1.8中進行了優化。當鏈表長度即將超過閥值(TREEIFY_THRESHOLD),會把鏈表轉化為紅黑樹。底層實現變為數組+鏈表+紅黑樹
(1)數組和鏈表中的每個元素都是Node
static class Nodeimplements Map.Entry { final int hash;//通過key的hashCode方法獲取的hash值。hash值相同的key會在數組中找到同一個位置 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; } }
(2)當鏈表長度達到閥值,鏈表轉化為紅黑樹。此時數組和紅黑樹中的元素是TreeNode
static final class TreeNodeextends LinkedHashMap.Entry { TreeNode parent; // 父節點 TreeNode left; //左子樹 TreeNode right;//右子樹 TreeNode prev; // needed to unlink next upon deletion boolean red; //顏色屬性 TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } }
(3)HashMap中幾個常用的屬性和構造方法
public class HashMapextends AbstractMap implements Map , Cloneable, Serializable { // 序列號 private static final long serialVersionUID = 362498820763181265L; // 默認的初始容量是16,通過移位運算獲得結果。在計算機底層位運算速度最快 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; // 默認的加載因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 鏈表轉紅黑樹的閥值 static final int TREEIFY_THRESHOLD = 8; // 擴容時紅黑樹轉鏈表的閥值 static final int UNTREEIFY_THRESHOLD = 6; // 鏈表轉化為紅黑樹對應的table的最小值 static final int MIN_TREEIFY_CAPACITY = 64; // 存儲節點的數組,一定是2的冪次方 transient Node [] table; // transient Set > entrySet; // 數組中元素的個數,注意這個不是數組的長度。 transient int size; // 修改HashMap的次數 transient int modCount; // 閥值,當數組中的元素大于threshold時HashMap進行擴容 threshold = (數組長度)capacity * loadFactor int threshold; // 填充因子 final float loadFactor; //無參構造函數,比較常用 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } //一個參數,數組容量 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //兩個參數,數組容量和加載因子 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; //因為我們的入參指定了數組大小,但是傳入的值可能不滿足HashMap要求。 //因此HashMap使用tableSizeFor保證數組大小一定是2的n次冪 this.threshold = tableSizeFor(initialCapacity); } /** 此方法的目的是:保證有參構造傳入的初始化數組長度是>=cap的最小2的冪次方。 對n不斷的無符號右移并且位或運算,可以將n從最高位為1開始的所有右側位數變成1, 最后n+1即成為大于cap的最小2的冪次方。 第一行 n=cap-1 是為了保證如果cap本身就是2^n,那么結果也將是其本身 */ 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; } //傳入一個HashMap實例 public HashMap(Map extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } //如果傳入的HashMap中有元素,遍歷它并且把其中的元素put到當前HashMap中 final void putMapEntries(Map extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { //當前數組為空 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t);//計算數組長度,并且保證長度是2的冪次方 } 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); } } } }
(4)put方法解析
/**如果key等于null就返回0,因此key為null時的數據存儲在數組中的第一個位置 *如果key不為null,將key的hashCode值賦值給h。然后將h無符號位移16位后再和該key的hashCode值進行異或 *作用:將hashCode的高16位和低16位進行異或,混合hashCode的高位和低位。以此加大低位的隨機性。 *當在計算key的位置時,(n - 1) & hash對數組長度取模,如果只取低位會造成大量碰撞。所以進行高低位異或。 */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /*當多個key的hash值相同時,會形成鏈表。如果此時又在該鏈表上插入一個元素,就要遍歷整個鏈表對比是否有相同的key,如果有則直接 *替換,如果沒有找到鏈表尾部,插入新元素。因此在JDK1.7中鏈表過長,引起效率低下 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //定義變量 Node[] tab; Node p; int n, i; //將table數組賦值給tab,將數組長度賦值給n。判斷當前map中的table數組是否為空(第一次肯定為空) if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;//將擴容后的數組賦值給tab,然后獲取數組長度賦值給n if ((p = tab[i = (n - 1) & hash]) == null)//計算key在數組中的位置,然后判斷該位置是否為null并賦值給p tab[i] = newNode(hash, key, value, null);//該位置沒有元素,直接創建一個節點放入 else {//進入下面代碼,表示該位置有元素。然后再判斷是鏈表還是紅黑樹 Node e; K k; //如果hash值相同,并且key相同表示數組中第一個元素即為相同的key if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;將數組中第一個元素賦值給e else if (p instanceof TreeNode)//如果當前元素類型為TreeNode表示為紅黑樹,putTreeVal返回待存放的Node。 e = ((TreeNode )p).putTreeVal(this, tab, hash, key, value); e可能為null else {//鏈表結構,遍歷鏈表找到插入的位置 for (int binCount = 0; ; ++binCount) { //遍歷至鏈表尾部,如果沒有相同的key,則插入尾部一個節點 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //插入后,如果鏈表長度大于等于樹化的閥值,將鏈表轉化為紅黑樹 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 = e; } } if (e != null) { // e不為null,代表存在相同的key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value;//將新值直接覆蓋老值 afterNodeAccess(e);//一個空方法 return oldValue;//返回老值 } } //代碼走到這里說明,數組中新增了一個Node ++modCount;//修改HashMap的次數 if (++size > threshold)//如果增加節點后,數組中元素的個數大于了擴容的閥值,則進行擴容 resize(); afterNodeInsertion(evict);//一個空方法 return null;//第一次增加節點,返回null }
(5)get方法解析
//調用getNode方法返回一個Node節點并賦值給e。如果e為null,則返回null。否則返回Node節點中的value屬性 public V get(Object key) { Nodee; return (e = getNode(hash(key), key)) == null ? null : e.value; } //hash(key)計算獲取hash,即key位于數組中的位置 final Node getNode(int hash, Object key) { Node [] tab; Node first, e; int n; K k; //取值前保證當前map中的table不為null,并且該key所在數組中的Node不為null,如果不滿足條件直接返回null if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))//先檢查第一個Node return first;//如果第一個Node滿足條件,證明這個就是我們要找的元素,直接返回 if ((e = first.next) != null) {//上面條件不滿足,則從紅黑樹,鏈表中找元素 if (first instanceof TreeNode)//如果該節點屬于TreeNode,則從紅黑樹中查找 return ((TreeNode )first).getTreeNode(hash, key); do {//遍歷鏈表找到相同的key則返回元素,否則跳出循環,返回null if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
(6)resize方法解析
//resize()是HashMap實現擴容機制的核心。在put方法中出現兩次,第一次初始化數組時,第二次數組元素達到閥值時。 //將原來數組中的元素重新hash到新的位置。新的位置和原位置相同,或者是原來位置的兩倍 final Node[] resize() { Node [] 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"}) Node [] newTab = (Node [])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node 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 )e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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; }
未完待續
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75134.html
摘要:概述主要來存放鍵值對。之前使用數組鏈表的形式,之后進行了改變,使用了數組鏈表或者紅黑樹的形式。如果為,則按照字段中保存的初始容量進行分配。并且之前在中的元素應呆在原處或者移動到倍位置處。 概述 HashMap主要來存放鍵值對。JDK1.8之前使用數組+鏈表的形式,JDK1.8之后進行了改變,使用了數組+鏈表或者紅黑樹的形式。 小概念普及 關系運算簡介 0 0 0 1 1 1 ...
摘要:之前,其內部是由數組鏈表來實現的,而對于鏈表長度超過的鏈表將轉儲為紅黑樹。非線程安全,即任一時刻可以有多個線程同時寫,可能會導致數據的不一致。有時兩個會定位到相同的位置,表示發生了碰撞。 原文地址 HashMap HashMap 是 Map 的一個實現類,它代表的是一種鍵值對的數據存儲形式。 大多數情況下可以直接定位到它的值,因而具有很快的訪問速度,但遍歷順序卻是不確定的。 HashM...
摘要:值得位數有的次方,如果直接拿散列值作為下標訪問主數組的話,只要算法比較均勻,一般是很難出現碰撞的。但是內存裝不下這么大的數組,所以計算數組下標就采取了一種折中的辦法,就是將得到的散列值與數組長度做一個與操作。 hashMap簡單介紹 hashMap是面試中的高頻考點,或許日常工作中我們只需把hashMap給new出來,調用put和get方法就完了。但是hashMap給我們提供了一個絕佳...
閱讀 472·2021-11-22 12:05
閱讀 1533·2021-11-17 09:33
閱讀 3579·2021-11-11 16:54
閱讀 2659·2021-10-14 09:49
閱讀 4024·2021-09-06 15:01
閱讀 1821·2019-08-29 17:23
閱讀 693·2019-08-29 14:09
閱讀 712·2019-08-29 12:28