溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了如何理解Java容器中Map的源碼分析，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
如果沒有特別說明，以下源碼分析基于 JDK 1.8。
為了便于理解，以下源碼分析以 JDK 1.7 為主。
1. 存儲結構
內部包含了一個 Entry 類型的數組 table。
transient Entry[] table;
Entry 存儲著鍵值對。它包含了四個字段，從 next 字段我們可以看出 Entry 是一個鏈表。 即數組中的每個位置被當成一個桶，一個桶存放一個鏈表。HashMap 使用拉鏈法來解決沖突， 同一個鏈表中存放哈希值相同的 Entry。
static class Entry<K,V> implements Map.Entry<K,V> {
//包含了四個字段
final K key;
V value;
//next指向下一個節點，說明是鏈表結構
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final Boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
// k1==k2 比較的是 hashcode 值，
// k1.equals(k2)比較的是k1和k2的內容 equals 未重寫，則等價于 k1 == k2
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
}2. 拉鏈法的工作原理
HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");新建一個 HashMap，默認大小為 16；
插入
插入
插入
應該注意到鏈表的插入是以頭插法方式進行的，例如上面的
查找需要分成兩步進行：
計算鍵值對所在的桶；
在鏈表上順序查找，時間復雜度顯然和鏈表的長度成正比。
3. put 操作
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 鍵為 null 單獨處理
if (key == null)
return putForNullKey(value);
int hash = hash(key);
// 確定桶下標
int i = indexFor(hash, table.length);
// 先找出是否已經存在鍵為 key 的鍵值對，如果存在的話就更新這個鍵值對的值為 value
// 時間復雜度顯然和鏈表的長度成正比。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 插入新鍵值對
addEntry(hash, key, value, i);
return null;
}HashMap 允許插入鍵為 null 的鍵值對。但是因為無法調用 null 的 hashCode() 方法，也就無法確定該鍵值對的桶下標，只能通過強制指定一個桶下標來存放。HashMap 使用第 0 個桶存放鍵為 null 的鍵值對。
private V putForNullKey(V value) {
//HashMap 使用第 0 個桶 table[0] 存放鍵為 null 的鍵值對。
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
// 更新值
e.recordAccess(this);
return oldValue;
// 返回舊值
}
}
modCount++;
//void addEntry(int hash, K key, V value, int bucketIndex)
addEntry(0, null, value, 0);
return null;
}使用鏈表的頭插法，也就是新的鍵值對插在鏈表的頭部，而不是鏈表的尾部。
//TODO:使用鏈表的頭插法，也就是新的鍵值對插在鏈表的頭部，而不是鏈表的尾部。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 頭插法，鏈表頭部指向新的鍵值對
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}4. 確定桶下標
很多操作都需要先確定一個鍵值對所在的桶下標。
int hash = hash(key); int i = indexFor(hash, table.length);
①. 計算 hash 值
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash42((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}②. 取模
令 x = 1<<4，即 x 為 2 的 4 次方，它具有以下性質：
x : 00010000 x-1 : 00001111
令一個數 y 與 x-1 做與運算，可以去除 y 位級表示的第 4 位以上數：
y : 10110010 x-1 : 00001111 y&(x-1) : 00000010
這個性質和 y 對 x 取模效果是一樣的：
y : 10110010 x : 00010000 y%x : 00000010
我們知道，位運算的代價比求模運算小的多，因此在進行這種計算時用位運算的話能帶來更高的性能。
確定桶下標的最后一步是將 key 的 hash 值對桶個數取模： hash%capacity，如果能保證 capacity 為 2 的 n 次方，那么就可以將這個操作轉換為位運算。
static int indexFor(int h, int length) {
return h & (length-1);
}就等價于
static int indexFor(int h, int length) {
return h % length;
}但是效率會更高。
5. 擴容-基本原理
設 HashMap 的 table 長度為 M，需要存儲的鍵值對數量為 N，如果哈希函數滿足均勻性的要求，那么每條鏈表的長度大約為 N/M，因此平均查找次數的復雜度為 O(N/M)。
為了讓查找的成本降低，應該盡可能使得 N/M 盡可能小，因此需要保證 M 盡可能大，也就是說 table 要盡可能大。 HashMap 采用動態擴容來根據當前的 N 值來調整 M 值，使得空間效率和時間效率都能得到保證。
和擴容相關的參數主要有：capacity、size、threshold 和 load_factor。
static final int DEFAULT_INITIAL_CAPACITY = 16; //保證 capacity 為 2 的 n 次方，那么就可以將indexFor方法中操作轉換為位運算 static final int MAXIMUM_CAPACITY = 1 << 30; //保證 capacity 為 2 的 n 次方，那么就可以將 indexFor 方法中操作轉換為位運算 static final float DEFAULT_LOAD_FACTOR = 0.75f; transient Entry[] table; transient int size; int threshold; final float loadFactor; transient int modCount;
從下面的添加元素代碼中可以看出，當需要擴容時，令 capacity 為原來的兩倍。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
//令 capacity 為原來的兩倍
}擴容使用 resize() 實現，需要注意的是，擴容操作同樣需要把 oldTable 的所有鍵值對重新插入 newTable 中，因此這一步是很費時的。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
while (e != null);
}
}
}6. 擴容-重新計算桶下標
在進行擴容時，需要把鍵值對重新放到對應的桶上。HashMap 使用了一個特殊的機制，可以提升重新計算桶下標的效率。
假設原數組長度 capacity 為 16，擴容之后 new capacity 為 32：
capacity : 00010000 new capacity : 00100000
對于一個 Key，
它的哈希值如果在第 5 位上為 0，那么取模得到的結果和之前一樣；
如果為 1，那么得到的結果為原來的結果 +16。
7. 計算數組容量
HashMap 構造函數允許用戶傳入的容量不是 2 的 n 次方，因為它可以自動地將傳入的容量轉換為 2 的 n 次方。
先考慮如何求一個數的掩碼，對于 10010000，它的掩碼為 11111111，可以使用以下方法得到：
mask |= mask >> 1 11011000 mask |= mask >> 2 11111110 mask |= mask >> 4 11111111
mask+1 是大于原始數字的最小的 2 的 n 次方。
num 10010000 mask+1 100000000
以下是 HashMap 中計算數組容量的代碼：
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;
//得到n的掩碼
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}8. 鏈表轉紅黑樹
從 JDK 1.8 開始，一個桶存儲的鏈表長度大于 8 時會將鏈表轉換為紅黑樹。
9. 與 HashTable 的比較
HashMap 是非線程安全的，HashTable 使用 synchronized 來進行同步，是線程安全的。
HashMap 要比 HashTable 效率高一點。Hashtable 基本被淘汰，不要在代碼中使用它。
HashMap 可以插入鍵為 null 的 Entry；HashTable 中插入的鍵只要有一個為 null，直接拋出 NullPointerException。
HashMap 的迭代器是 fail-fast 迭代器。
HashMap 不能保證隨著時間的推移 Map 中的元素次序是不變的。
HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間；Hashtable 沒有這樣的機制。
HashMap 默認的初始化大小為16。之后每次擴充，容量變為原來的2倍；Hashtable 容量默認的初始大小為11，之后每次擴充，容量變為原來的2n+1。 在初始化時如果給定了容量初始值，HashMap 會將其擴充為2的冪次方大小；Hashtable 會直接使用初始值。
10. 與 HashSet 的比較
HashSet 底層就是基于HashMap實現的。 (HashSet 的源碼非常非常少，因為除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不實現之外， 其他方法都是直接調用 HashMap 中的方法。)
1.存儲結構
繼承自 HashMap，因此具有和 HashMap 一樣的快速查找特性。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
內部維護了一個雙向鏈表，用來維護插入順序或者 LRU 順序。
/** * The head (eldest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> head; /** * The tail (youngest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> tail;
accessOrder 決定了順序，默認為 false，此時維護的是插入順序。
final boolean accessOrder;
LinkedHashMap 最重要的是以下用于維護順序的函數，它們會在 put、get 等方法中調用。
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }2.afterNodeAccess()
當一個節點被訪問時，如果 accessOrder 為 true，則會將該節點移到鏈表尾部。也就是說指定為 LRU 順序之后，在每次訪問一個節點時，會將這個節點移到鏈表尾部，保證鏈表尾部是最近訪問的節點，那么鏈表首部就是最近最久未使用的節點。
void afterNodeAccess(Node<K,V> e) {
// move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a; else
b.after = a;
if (a != null)
a.before = b; else
last = b;
if (last == null)
head = p; else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}3.afterNodeInsertion()
在 put 等操作之后執行，當 removeEldestEntry() 方法返回 true 時會移除最晚的節點，也就是鏈表首部節點 first。
evict 只有在構建 Map 的時候才為 false，在這里為 true。
void afterNodeInsertion(Boolean evict) {
// possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}removeEldestEntry() 默認為 false，如果需要讓它為 true，需要繼承 LinkedHashMap 并且覆蓋這個方法的實現，這在實現 LRU 的緩存中特別有用，通過移除最近最久未使用的節點，從而保證緩存空間足夠，并且緩存的數據都是熱點數據。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}4.LRU 緩存
以下是使用 LinkedHashMap 實現的一個 LRU 緩存：
設定最大緩存空間 MAX_ENTRIES 為 3；
使用 LinkedHashMap 的構造函數將 accessOrder 設置為 true，開啟 LRU 順序；
覆蓋 removeEldestEntry() 方法實現，在節點多于 MAX_ENTRIES 就會將最近最久未使用的數據移除。
public class LRUCache<K,V> extends LinkedHashMap<K,V>{
private static final int MAX_ENTRIES = 3;
LRUCache(){
super(MAX_ENTRIES,0.75f,true);
}
/**
* removeEldestEntry() 默認為 false，
* 如果需要讓它為 true，需要繼承 LinkedHashMap 并且覆蓋這個方法的實現，
* 這在實現 LRU 的緩存中特別有用，通過移除最近最久未使用的節點，
* 從而保證緩存空間足夠，并且緩存的數據都是熱點數據。
*/
@Override
protected Boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
public static void main(String[] args) {
LRUCache<Integer,String> cache=new LRUCache<>();
cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");
cache.get(1);
//LRU 鍵值1被訪問過了，則最近最久未訪問的就是2
cache.put(4, "d");
System.out.println(cache.keySet());
}
}[3, 1, 4]
1.存儲結構
WeakHashMap 的 Entry 繼承自 WeakReference，被 WeakReference 關聯的對象在下一次垃圾回收時會被回收。
WeakHashMap 主要用來實現緩存，通過使用 WeakHashMap 來引用緩存對象，由 JVM 對這部分緩存進行回收。
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V>
2.ConcurrentCache
Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 來實現緩存功能。
ConcurrentCache 采取的是分代緩存：
經常使用的對象放入 eden 中，eden 使用 ConcurrentHashMap 實現，不用擔心會被回收；
不常用的對象放入 longterm，longterm 使用 WeakHashMap 實現，這些老對象會被垃圾收集器回收。
當調用 get() 方法時，會先從 eden 區獲取，如果沒有找到的話再到 longterm 獲取，當從 longterm 獲取到就把對象放入 eden 中，從而保證經常被訪問的節點不容易被回收。
當調用 put() 方法時，如果 eden 的大小超過了 size，那么就將 eden 中的所有對象都放入 longterm 中，利用虛擬機回收掉一部分不經常使用的對象。
public final class ConcurrentCache<K, V> {
private final int size;
private final Map<K, V> eden;
private final Map<K, V> longterm;
public ConcurrentCache(int size) {
this.size = size;
this.eden = new ConcurrentHashMap<>(size);
this.longterm = new WeakHashMap<>(size);
}
public V get(K k) {
V v = this.eden.get(k);
if (v == null) {
v = this.longterm.get(k);
if (v != null)
this.eden.put(k, v);
}
return v;
}
public void put(K k, V v) {
if (this.eden.size() >= size) {
this.longterm.putAll(this.eden);
this.eden.clear();
}
this.eden.put(k, v);
}
}上述內容就是如何理解Java容器中Map的源碼分析，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
