【Java】Map總結和源碼注釋
- 2020 年 3 月 2 日
- 筆記
前言
Map為一個Java中一個重要的數據結構，主要表示<key, value>的映射關係對。本文包括了相關Map數據結構的總結和源碼的閱讀注釋。
HashMap
初始化，可以選擇第二個初始化函數來設置裝載能力threshold和裝載係數loadFactor：
HashMap()HashMap(int initialCapacity, float loadFactor)
HashMap中定義的一些常量：
-
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;預設的初始大小
-
static final int MAXIMUM_CAPACITY = 1 << 30;最大限定大小，當超過這個值時，會
resize()到Integer.MAX_VALUE -
static final float DEFAULT_LOAD_FACTOR = 0.75f;threshold = capacity*laodFactor
HashMap的大小始終為2的倍數，若插入時超過threshold時，會調用resize()來自動將大小擴大一倍。
值在Node<K,V>[] table中的定位方式為(n-1)&hash(key)，這也是resize的時候直接double的原因
基本方法：
V put(K key, V value)：若key不存在，則插入；若key存在，則更新value值，返回舊的valueV putIfAbsent(K key, V value)V get(Object key)：get不存在的key時會返回null，需要注意NullPointerExceptionint size()
遍歷方式
-
forEach(lambda)通過lambda表達式進行遍歷 -
entrySet().iterator()Iterator iter = map.entrySet().iterator(); while(iter.hasNext()){ Map.Entry e = (Map.Entry)iter.next(); key = e.getKey(); value = e.getValue(); } -
keySet().iterator()Iterator iter = map.keySet().iterator(); while(iter.hasNext()){ key = iter.next(); value = map.get(key); } -
values().iterator()
resize()
final Node<K,V>[] resize() { Node<K,V>[] 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 && // 新大小=舊大小*2 oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // 閾值也一起*2 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // oldCap為0時處於初始化階段，進行初始化 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) { // 將舊map移到新map中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 置為null值方便GC 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 order 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; // 擴容部分節點位置加上了oldCap } } } } } return newTab; }衝突解決
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; // 數組為空的情況 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 沒有衝突直接放入 else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 有衝突但是key相同，則覆蓋原來的值 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) // 如果桶的鏈長度超過閾值則拉成紅黑樹 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 在鏈中找到相同的key則覆蓋其值 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; }Hashtable
初始化函數：
public Hashtable() { this(11, 0.75f); }默認下initialCapacity = 11，loadFactor = 0.75。
插入操作put(K,V)
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { // 找到相同的key則覆蓋原值 V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; }Hashtable的hash定址方法為(hash & 0x7FFFFFFF) % tab.length，當插入的key之前有值時返回舊值，否則返回null。
addEntry(hash, key, value, index)，當table的大小不夠時，執行rehash()擴大table
private void addEntry(int hash, K key, V value, int index) { Entry<?,?> tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; modCount++; }rehash():
protected void rehash() { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1; // 新大小=原大小*2+1 if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; modCount++; threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); // 更新閾值 table = newMap; for (int i = oldCapacity ; i-- > 0 ;) { // 將舊map中的值一道新map for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; newMap[index] = e; } } }與HashMap的區別
-
HashMap 繼承自AbstractMap類，Hashtable繼承自Dictionary類
- Hashtable中的方法均用sychronized關鍵字修飾，為執行緒安全
- 擴容方法不同，HashMap直接double，使得大小始終是2的倍數，Hashtable在double後加1
-
在table中的查找方式不同：HashMap為
hash&(n-1)，Hashtable為(hash & 0x7FFFFFFF) % tab.length
TreeMap
TreeMap的本質是紅黑樹，紅黑樹是一種特殊的二叉查找樹，所以TreeMap中的節點都是有序的。
TreeMap中節點Entry的定義為
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; }初始化函數：
public TreeMap() { comparator = null; } public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }TreeMap支援自定義的比較器，若是使用空初始化函數，則默認為key的自然順序
/** * The comparator used to maintain order in this tree map, or * null if it uses the natural ordering of its keys. * * @serial */ private final Comparator<? super K> comparator;插入操作put(K,V)
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { // root為空則直接new compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { // 自定義comparator時 do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); // 如果key相等則直接覆蓋value } while (t != null); } else { // 使用key的comparable介面 if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); //找到相同的key則直接覆蓋value返回 } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); // 插入節點 if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); // 紅黑樹自平衡過程 size++; modCount++; return null; }插入後紅黑樹的自平衡過程:
private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; // 設插入節點的顏色為紅 while (x != null && x != root && x.parent.color == RED) { // 當x.parent為黑時樹已經平衡 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // x.parent是祖父節點的左子節點 Entry<K,V> y = rightOf(parentOf(parentOf(x))); // x的uncle節點 if (colorOf(y) == RED) { // uncle為紅的時候recolor setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); // 向上變色直到滿足平衡條件 } else { // uncle為黑的時候則需要rotate if (x == rightOf(parentOf(x))) { // 左右的情況，向左旋轉 x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { // 右左的情況，向右旋轉 x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; }如有不對請多指正?
