關于HashMap源碼解讀
一、概述
- HashMap 是基于哈希表實現(xiàn)的,每一個元素是一個 key-value 對,其內(nèi)部通過單鏈表解決沖突問題,容量不足(超過了閾值)時,同樣會自動增長。
- HashMap 是非線程安全的,只是適用于單線程環(huán)境,多線程環(huán)境可以采用并發(fā)包下的concurrentHashMap
- HashMap 實現(xiàn)了Serializable接口,支持序列化,實現(xiàn)了Cloneable接口,能被克隆。
- HashMap是基于哈希表的Map接口的非同步實現(xiàn).此實現(xiàn)提供所有可選的映射操作,并允許使用null值和null鍵。此類不保證映射的順序,特別是它不保證該順序恒久不變。
- Java8中又對此類底層實現(xiàn)進行了優(yōu)化,比如引入了紅黑樹的結構以解決哈希碰撞
JDK1.7和JDK1.8的區(qū)別
比較 | HashMap1.7 | HashMap1.8 |
---|---|---|
數(shù)據(jù)結構 | 數(shù)組+鏈表 | 數(shù)組+鏈表+紅黑樹 |
節(jié)點 | Entry(hash是可變的,因為有rehash的操作) | Node TreeNode(為了轉(zhuǎn)換紅黑樹、hash是final修飾,也就是說hash值一旦確定,就不會再重新計算hash值了) |
Hash算法 | 較為復雜 | 異或Hash右移16位 |
對Null的處理 | 單獨寫一個putForNull()方法處理 | 作為以一個Hash值為0的普通節(jié)點處理 |
初始化 | 賦值給一個空數(shù)值,put時初始化 | 沒有賦值,懶加載,put時初始化 |
擴容 | 插入前擴容 | 插入后,初始化,樹化時擴容 |
節(jié)點插入 | 頭插法 | 尾插法 |
什么是懶加載?
- 即延遲加載(Lazyload)。
- 簡單的說就是只有當我們?nèi)フ{(diào)用到它時才會去做加載。
二、HashMap的數(shù)據(jù)結構
HashMap 底層采用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結構實現(xiàn)。
數(shù)組是 HashMap 的主體,用于存儲鍵值對;鏈表用于解決哈希沖突;紅黑樹是在鏈表長度超過一定閾值(默認為8)時,將鏈表轉(zhuǎn)換為紅黑樹,以提高查找效率。
三、迭代方式
HashMap的迭代種類
- 分別遍歷Key和Value
- 使用Iterator迭代器迭代
- 通過get的方式(不建議使用)
- Map接口中的默認方法(映射方式)JDK1.8
public class HashMapExam { public static void main(String[] args) { Map<Integer, String> map = new HashMap<>(); for (int i = 0; i < 15; i++) { map.put(i, new String(new char[]{(char) ('A'+ i)})); } System.out.println("======Key和Value======="); for (Integer key:map.keySet()) { System.out.println(key); } for (String value:map.values()) { System.out.println(value); } System.out.println("======Iterator迭代器======="); Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Integer, String> mapEntry = iterator.next(); System.out.println(mapEntry.getKey()+ "====" + mapEntry.getValue()); } System.out.println("======Get的方式======="); Set<Integer> keySet = map.keySet(); for (Integer key : keySet) { System.out.println(key + "====" + map.get(key)); } System.out.println("======forEach======="); map.forEach((key,value) -> System.out.println(key+ "----" + value)); } }
四、源碼分析
1、HashMap繼承關系
- Cloneable 空接口:表示可以克隆。創(chuàng)建并返回HashMap對象的一個副本;
- Serializable 序列化接口:屬于標記性接口。HashMap 對象可以倍序列化和反序列化。
- AbstractMap:父類提供了Map實現(xiàn)接口。以最大限度地減少實現(xiàn)此接口所需的工作。
HashMap 繼承關系如下圖所示:
補充:通過上述繼承關系我們發(fā)現(xiàn)一個很奇怪的現(xiàn)象, 就是HashMap已經(jīng)繼承了AbstractMap而AbstractMap類實現(xiàn)了Map接口,那為什么HashMap還要在實現(xiàn)Map接口呢?同樣在ArrayList中LinkedList中都是這種結構。
據(jù) java 集合框架的創(chuàng)始人Josh Bloch描述,這樣的寫法是一個失誤。在java集合框架中,類似這樣的寫法很多,最開始寫java集合框架的時候,他認為這樣寫,在某些地方可能是有價值的,直到他意識到錯了。顯然的,JDK的維護者,后來不認為這個小小的失誤值得去修改,所以就這樣存在下來了。
2、成員變量
// 序列化版本號 private static final long serialVersionUID = 362498820763181265L; // 默認的初始容量是16 --> 1<<4 相當于 1*2的4次方也就是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量(傳入容量過大將被這個替換) static final int MAXIMUM_CAPACITY = 1 << 30; // 默認加載因子為0.75,通過這個來算出臨界值 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 當桶(bucket)上的結點數(shù)大于這個值時會轉(zhuǎn)換成紅黑樹 static final int TREEIFY_THRESHOLD = 8; // 當桶(bucket)上的結點數(shù)小于這個值時樹轉(zhuǎn)鏈表 static final int UNTREEIFY_THRESHOLD = 6; // 桶中結構轉(zhuǎn)化為紅黑樹對應的數(shù)組長度最小的值 static final int MIN_TREEIFY_CAPACITY = 64; //存儲元素的數(shù)組 transient Node<K,V>[] table; //存放具體元素的集合 transient Set<Map.Entry<K,V>> entrySet; //存放元素的個數(shù),注意這個不等于數(shù)組的長度。 transient int size; // 每次擴容和更改map結構的計數(shù)器 transient int modCount; // 臨界值 當實際大小(容量*負載因子)超過臨界值時,會進行擴容 int threshold; // 負載因子實際大小 final float loadFactor;
3、構造方法
①HashMap()
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 將默認的加載因子0.75賦值給loadFactor,并沒有創(chuàng)建數(shù)組 }
②HashMap(int initialCapacity)
// 指定“容量大小”的構造函數(shù) public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
③HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) { //判斷初始化容量initialCapacity是否小于0 if (initialCapacity < 0) //如果小于0,則拋出非法的參數(shù)異常IllegalArgumentException throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //判斷初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次冪 if (initialCapacity > MAXIMUM_CAPACITY) //如果超過MAXIMUM_CAPACITY,會將MAXIMUM_CAPACITY賦值給initialCapacity initialCapacity = MAXIMUM_CAPACITY; //判斷負載因子loadFactor是否小于等于0或者是否是一個非數(shù)值 if (loadFactor <= 0 || Float.isNaN(loadFactor)) //如果滿足上述其中之一,則拋出非法的參數(shù)異常IllegalArgumentException throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //將指定的加載因子賦值給HashMap成員變量的負載因子loadFactor this.loadFactor = loadFactor; /* tableSizeFor(initialCapacity) 判斷指定的初始化容量是否是2的n次冪,如果不是那么會變?yōu)楸戎? 定初始化容量大的最小的2的n次冪。這點上述已經(jīng)講解過。 但是注意,在tableSizeFor方法體內(nèi)部將計算后的數(shù)據(jù)返回給調(diào)用這里了,并且直接賦值給threshold邊 界值了。有些人會覺得這里是一個bug,應該這樣書寫: this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; 這樣才符合threshold的意思(當HashMap的size到達threshold這個閾值時會擴容)。 但是,請注意,在jdk8以后的構造方法中,并沒有對table這個成員變量進行初始化,table的初始化被推 遲到了put方法中,在put方法中會對threshold重新計算,put方法的具體實現(xiàn)我們下面會進行講解 */ this.threshold = tableSizeFor(initialCapacity); } 最后調(diào)用了tableSizeFor,來看一下方法實現(xiàn): /** * Returns a power of two size for the given target capacity. 返回比指定初始化容量大的最小的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(Map<? extends K, ? extends V> m)
//構造一個映射關系與指定 Map 相同的新 HashMap。 public HashMap(Map<? extends K, ? extends V> m) { //負載因子loadFactor變?yōu)槟J的負載因子0.75 this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } // 最后調(diào)用了putMapEntries,來看一下方法實現(xiàn): final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //獲取參數(shù)集合的長度 int s = m.size(); if (s > 0) { //判斷參數(shù)集合的長度是否大于0,說明大于0 if (table == null) // 判斷table是否已經(jīng)初始化 { // pre-size // 未初始化,s為m的實際元素個數(shù) float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 計算得到的t大于閾值,則初始化閾值 if (t > threshold) threshold = tableSizeFor(t); } // 已初始化,并且m元素個數(shù)大于閾值,進行擴容處理 else if (s > threshold) resize(); // 將m中的所有元素添加至HashMap中 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、成員方法
①Node類
Node 類是 HashMap 中的靜態(tài)內(nèi)部類,實現(xiàn)Map·Entry 接口,定義了 key 鍵、value 值、next 節(jié)點,也就是說元素之間構成單向鏈表。
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; } 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; } }
②TreeNode類(Java新加的)
紅黑樹結構包含前、后、左、右節(jié)點,以及標志是否為紅黑樹的字段
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { .... } final TreeNode<K,V> find(int h, Object k, Class<?> kc) { .... } final TreeNode<K,V> getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } static int tieBreakOrder(Object a, Object b) { .... } final void treeify(Node<K,V>[] tab) { .... } final Node<K,V> untreeify(HashMap<K,V> map) { .... } final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { .... } final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { .... } final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { .... } static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { .... } static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { .... } static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { .... } static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) { .... } static <K,V> boolean checkInvariants(TreeNode<K,V> t) { .... } }
③Hash方法
在JDK1.8及之后對Hash算法進行了改良,使用較為復雜 異或Hash右移16位。
static final int hash(Object key) { int h; // (h = key.hashCode()) ^ (h >>> 16):異或Hash右移16位算法 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
④Get方法
下面是JDK1.8中HashMap的Get方法的簡要實現(xiàn)過程:
- 首先,需要計算鍵的哈希值,并通過哈希值計算出在數(shù)組中的索引位置。
- 如果該位置上的元素為空,說明沒有找到對應的鍵值對,直接返回null。
- 如果該位置上的元素不為空,遍歷該位置上的元素,如果找到了與當前鍵相等的鍵值對,那么返回該鍵值對的值,否則返回null。
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
get方法看起來很簡單,就是通過同樣的 hash 得到 key 的 hash 值。重點看下 getNode 方法:
final Node<K,V> getNode(int hash, Object key) { // 當前 HashMap 的散列表的引用 Node<K,V>[] tab; // first:桶頭元素 // e:用于存儲臨時元素 Node<K,V> first, e; // n:table 數(shù)組的長度 int n; // 元素中的 k K k; // 將 table 賦值給 tab,不等于 null 說明有數(shù)據(jù),(n = table.length)> 0 同理說明 table 中有值 if ((tab = table) != null && (n = tab.length) > 0 && // 同時將 該位置的元素賦值為 first (first = tab[(n - 1) & hash]) != null) { // 定位到了桶的到的位置就是想要獲取的 key 對應的,直接返回該元素 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 到這一步說明定位到的元素不是想要的,且該位置不僅僅有一個元素,想要判斷是鏈表還是樹 if ((e = first.next) != null) { // 是否已經(jīng)樹化 if (first instanceof TreeNode) return ((TreeNode<K,V>)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); } } // 遍歷不到返回null return null; }
⑤Put方法
下面是 JDK 1.8 中 HashMap 的 put 方法的簡要實現(xiàn)過程:
- 首先,put 方法會計算鍵的哈希值(通過調(diào)用 hash 方法),并通過哈希值計算出在數(shù)組中的索引的位置。
- 如果該位置上的元素為空,那么直接將鍵值對存儲在該位置上。
- 如果該位置上的元素不為空,那么遍歷該位置上的元素,如果找到了與當前鍵相等的鍵值對,那么將該鍵值對的值更新為當前值,并返回舊值。
- 如果該位置上的元素不為空,但沒有與當前鍵相等的鍵值對,那么將鍵值對插入到鏈表或紅黑樹中(如果該位置上的元素數(shù)量超過一個閾值,就會將鏈表轉(zhuǎn)化為紅黑樹來提高效率)。
- 如果插入成功,返回被替換的值;如果插入失敗,返回null。
- 插入成功后,如果需要擴容,那么就進行一次擴容操作。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
核心其實是通過putValue方法實現(xiàn)的,在傳給putValue的參數(shù)中,先調(diào)用hash獲取了一個hashCode。
putValue 方法主要實現(xiàn)如下,給大家增加了注釋:
/** * Implements Map.put and related methods. * * @param hash key 的 hash 值 * @param key key 值 * @param value value 值 * @param onlyIfAbsent true:如果某個 key 已經(jīng)存在那么就不插了;false 存在則替換,沒有則新增。這里為 false * @param evict 不用管理。我也不認識 * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // tab 表示當前 hash 散列表的引用 Node<K,V>[] tab; // 表示具體的散列表中的元素 Node<K,V> p; // n:表示散列表數(shù)組的長度 // i:表示路由尋址的結果 int n, i; // 將 table 賦值發(fā)給 tab,如果 tab == null,說明 table 還沒有被初始化。則此時是需要去創(chuàng)建 table 的 // 為什么這個時候才去創(chuàng)建散列表,因為可能創(chuàng)建了 HashMap 時候可能并沒有存放數(shù)據(jù),如果在初始化 HashMap 的時候創(chuàng)建散列表,勢必會造成空間的浪費 // 這里也就是延遲初始化的邏輯 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 如果 p == null,說明尋址到的桶沒有元素。那么就將 key-value 封裝到 Node 中,并放到尋址到的下標為 i 的位置 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 到這里說明 該位置已經(jīng)有數(shù)據(jù)了,且此時可能是鏈表結構,也可能是樹結構 else { // e 表示找到了一個與當前要插入的 key-value 一致的元素 Node<K,V> e; // 臨時的 key K k; // p 的值就是上一步 if 中的結果即:此時的(p = tab[i = (n - 1) & hash])不等于 null // p 是原來的已經(jīng)在 i 的位置的元素,且新插入的 key 是等于 p 中的 key // 說明找到了和當前需要插入的元素相同的元素(其實就是需要替換而且) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 將 p 的值賦值給 e e = p; // 說明已經(jīng)樹化,紅黑樹會有單獨的文章介紹,本文不再闡述 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 如果 p.next == null 說明 p 是最后一個元素,說明,該元素在鏈表中也沒有重復的 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 直接將 key-value 封裝到 Node 中并且添加到 p 的后面 p.next = newNode(hash, key, value, null); // 當元素已經(jīng)是 7 了,再來一個就是 8 個了,那么就需要進行樹化 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; // 將e(即p.next)賦值給e,這就是為了繼續(xù)遍歷鏈表的下一個元素(沒啥好說的)下面的有張圖幫助大家理解 p = e; } } // 如果條件成立,說明找到了需要替換的數(shù)據(jù) if (e != null) { // 這里不就是使用新的值賦值為舊的值嘛 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 這個方法沒用,里面啥都沒有 afterNodeAccess(e); // HashMap put 方法的返回值是原來位置的元素值 return oldValue; } } // 上面說過,對于散列表 結構修改次數(shù),那么就修改 modCount 的次數(shù) ++modCount; // size 即散列表中的元素個數(shù),添加后需要自增,如果自增后的值大于擴容的閾值,那么就觸發(fā)擴容操作 if (++size > threshold) resize(); // 啥也沒干 afterNodeInsertion(evict); // 原來位置沒有值,那么就返回 null 唄 return null; }
⑥Resize方法
什么情況下會擴容(擴原來的2倍):
- 容器初始化的時候
- 元素個數(shù)大于臨界值的時候
- 桶中的個數(shù)大于8時,并且數(shù)量小于64時
HashMap的擴容是什么: - 首先會新建一個比原來大于2倍的哈希表
- 遍歷舊哈希表的每個桶,重新計算桶的元素的新位置(rehash方式)
- 如果高位新增1,則 原位置+舊容器
- 如果高位沒有新增1,則 原位置
- 將計算出新位置的元素放進新哈希表中,
- 并且將舊哈希表中對應的元素設置為null,方便后面GC回收
final Node<K,V>[] resize() { //得到當前數(shù)組 Node<K,V>[] oldTab = table; //如果當前數(shù)組等于null長度返回0,否則返回當前數(shù)組的長度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //當前閥值點 默認是12(16*0.75) int oldThr = threshold; int newCap, newThr = 0; //如果老的數(shù)組長度大于0 //開始計算擴容后的大小 if (oldCap > 0) { // 超過最大值就不再擴充了,就只好隨你碰撞去吧 if (oldCap >= MAXIMUM_CAPACITY) { //修改閾值為int的最大值 threshold = Integer.MAX_VALUE; return oldTab; } /* 沒超過最大值,就擴充為原來的2倍 1)(newCap = oldCap << 1) < MAXIMUM_CAPACITY 擴大到2倍之后容量要小于最大容量 2)oldCap >= DEFAULT_INITIAL_CAPACITY 原數(shù)組長度大于等于數(shù)組初始化長度16 */ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //閾值擴大一倍 newThr = oldThr << 1; // double threshold } //老閾值點大于0 直接賦值 else if (oldThr > 0) // 老閾值賦值給新的數(shù)組長度 newCap = oldThr; else {// 直接使用默認值 newCap = DEFAULT_INITIAL_CAPACITY;//16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 計算新的resize最大上限 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //新的閥值 默認原來是12 乘以2之后變?yōu)?4 threshold = newThr; //創(chuàng)建新的哈希表 @SuppressWarnings({"rawtypes","unchecked"}) //newCap是新的數(shù)組長度--》32 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //判斷舊數(shù)組是否等于空 if (oldTab != null) { // 把每個bucket都移動到新的buckets中 //遍歷舊的哈希表的每個桶,重新計算桶里元素的新位置 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { //原來的數(shù)據(jù)賦值為null 便于GC回收 oldTab[j] = null; //判斷數(shù)組是否有下一個引用 if (e.next == null) //沒有下一個引用,說明不是鏈表,當前桶上只有一個鍵值對,直接插入 newTab[e.hash & (newCap - 1)] = e; //判斷是否是紅黑樹 else if (e instanceof TreeNode) //說明是紅黑樹來處理沖突的,則調(diào)用相關方法把樹分開 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 采用鏈表處理沖突 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; //通過上述講解的原理來計算節(jié)點的新位置 do { // 原索引 next = e.next; //這里來判斷如果等于true e這個節(jié)點在resize之后不需要移動位置 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 原索引+oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 原索引放到bucket里 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 原索引+oldCap放到bucket里 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
流程圖:
⑦Remove方法
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) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // index 元素只有一個元素 node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) // index處是一個紅黑樹 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // index處是一個鏈表,遍歷鏈表返回node do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 分不同情形刪除節(jié)點 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; --size; afterNodeRemoval(node); return node; } } return null; }
五、擴展
源碼符號(位運算符)的解釋
>>> 和 >> 的區(qū)別
無符號右移運算符。它將操作數(shù)的二進制表示向右移動指定的位數(shù)。
- >>>:它在右移時,無論正數(shù)還負數(shù),高位都補 0。
- >>:它在右移時,正數(shù)高位補 0,負數(shù)高位都補 1。
例子如下:
n = n >>> 2; // 假設n等于-15 00000000 00000000 00000000 00001111 // 15 0000000000 00000000 00000000 00001111 //15的二進制從高位右移2位 ------------------------------------------------- 00000000 00000000 00000000 00000011 //15右移之后3 n = n >> 2; // 假設n等于-15 00000000 00000000 00000000 00001111 // -15 11000000 00000000 00000000 0000001111 //-15的二進制從高位右移2位 ------------------------------------------------- 11000000 00000000 00000000 00000011 //-15右移之后3
^ 和 & 的區(qū)別
- ^(按位與運算):運算規(guī)則:相同的二進制數(shù)位上,都是1的時候,結果為 1,否則為 0。
- &(按位異或運算):運算規(guī)則:相同的二進制數(shù)位上,數(shù)字相同,結果為 0,不同為 1。
例子如下:
n = i^j // 假設i等于10,j 等于15 00000000 00000000 00000000 00001000 // i=10 00000000 00000000 00000000 00001100 // j=15 ------------------------------------------------- 00000000 00000000 00000000 00001000 // n=10 n = i&j // 假設i等于10,j 等于15 00000000 00000000 00000000 00001000 // i=10 00000000 00000000 00000000 00001100 // j=15 ------------------------------------------------- 00000000 00000000 00000000 00000100 // n=5
總結
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關文章
java使用MulticastSocket實現(xiàn)組播
這篇文章主要為大家詳細介紹了java使用MulticastSocket實現(xiàn)組播,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-01-01Spring Boot 2.X整合Spring-cache(讓你的網(wǎng)站速度飛起來)
這篇文章主要介紹了Spring Boot 2.X整合Spring-cache(讓你的網(wǎng)站速度飛起來),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2019-09-09ObjectInputStream 和 ObjectOutputStream 介紹_動力節(jié)點Java學院整理
ObjectInputStream 和 ObjectOutputStream 的作用是,對基本數(shù)據(jù)和對象進行序列化操作支持。本文給大家詳細介紹了ObjectInputStream 和 ObjectOutputStream的相關知識,感興趣的朋友一起學習吧2017-05-05SpringBoot+Shiro+LayUI權限管理系統(tǒng)項目源碼
本項目旨在打造一個基于RBAC架構模式的通用的、并不復雜但易用的權限管理系統(tǒng),通過SpringBoot+Shiro+LayUI權限管理系統(tǒng)項目可以更好的幫助我們掌握springboot知識點,感興趣的朋友一起看看吧2021-04-04