# Map接口 Map結構用于存儲鍵值對，是一個接口，其常見的實現類有HashMap、Hashtable、TreeMap等。在該接口中定義的統一操作有： 1. 添加元素： ~~~ ?// 用于鍵值對的綁定，當鍵不存在是返回null，當鍵存在是返回舊值。 ?V put(K key, V value); ~~~ 2. 判斷 ~~~ ?// 是否包含鍵 ?boolean containsKey(Object key); ?// 是否包含值 ?boolean containsValue(Object value); ?// 是否為空 ?boolean isEmpty(); ?// 判斷兩個map是否相同 ?boolean equals(Object o); ~~~ 3. 獲取元素 ~~~ ?// 根據鍵獲取value值，不存在則返回null ?V get(Object key); ?// 獲取所有鍵 ?Set<K> keySet(); ?// 獲取所有的值 ?Collection<V> values(); ?// 獲取所有鍵值對 ?Set<Map.Entry<K,V>> entrySet(); ?// 大小 ?int size(); ~~~ 4. 移除元素 ~~~ ?// 移除某個鍵 ?V remove(object key); ?// 清空map的內容 ?void clear(); ~~~ &nbsp; ****** Map接口的實現類： ## HashMap HashMap是JDK1.2版本之后開始增加的，在1.8版本之前其底層使用數組+鏈表的方式來作為哈希表的存儲結構，在1.8版本及之后改成了數組+鏈表/紅黑樹的方式來作為哈希表的存儲結構，當鏈表的長度大于8的時候會將鏈表轉換成一顆紅黑樹。 在分析HashMap的源碼之前，先來看看一個鍵值對放入一個Map中應該經過什么步驟？ :-:  **源碼分析** 1. 幾個重要成員屬性 ~~~ ?// 初始容量，必須為2的冪次方，默認為16 ?static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; ?? ?// 最大的容量 ?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; ?// 哈希表的桶大于64時才會轉換成樹結構 ?static final int MIN_TREEIFY_CAPACITY = 64; ?? ?//----------------字段----------------------- ?// 底層數組結構 ?transient Node<K,V>[] table; ?// 鍵值對集合，可以用于鍵值對的遍歷 ?transient Set<Map.Entry<K,V>> entrySet; ?// 鍵值對的數量 ?transient int size; ?// 修改容器的次數 ?transient int modCount; ?// 容量閾值 ?int threshold; ?// 負載因子 ?final float loadFactor; ~~~ 2. 構造方法 ~~~ ?public HashMap() { ? ? ?this.loadFactor = DEFAULT_LOAD_FACTOR; // 設置為默認的負載因子 ?} ?? ?// 設置初始化容量，在阿里的開發手冊中要求在創建HashMap時要指定初始化容量的大小 ?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; ? ? ?// 這里會將初始化容量轉化成第一個比其大的一個2的冪次方的數 ? ? ?this.threshold = tableSizeFor(initialCapacity); ? ? ?// n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); ? ? ?// numberOfLeadingZeros可以獲取前導0的數量。 ?} ~~~ 3. 關鍵操作 * put添加元素方法 ~~~ ?// 不存在映射則會關聯值，存在則直接替換值 ?public V put(K key, V value) { ? ? ?return putVal(hash(key), key, value, false, true); ?} ?// 計算hash值，從這里可以看出HashMap的key可以為null，其hash值為0 --> 面試可能會問。 ?static final int hash(Object key) { ? ? ?int h; ? ? ?return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); ?} ?/** ? hash – 密鑰的散列 ? key——鑰匙 ? value – 要放置的值 ? onlyIfAbsent – 如果為真，則不更改現有值 ? evict – 如果為 false，則表處于創建模式。 ? 返回：以前的值，如果沒有，則為 null ?*/ ?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)))) ? ? ? ? ? ? ?// 進一步判斷key是否相等，或者是key重寫equals方法后相等 ? ? ? ? ? ? ?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) ? ? ? ? ? ? ? ? ? ? ? ? ?// 鏈表長度大于8的時候轉化成樹結構，但是在里面還會判斷桶的數量是否大于64，如果沒有的話則進行擴容操作 ? ? ? ? ? ? ? ? ? ? ? ? ?treeifyBin(tab, hash); ? ? ? ? ? ? ? ? ? ? ?break; ? ? ? ? ? ? ? ? } ? ? ? ? ? ? ? ? ?if (e.hash == hash && ? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k)))) ? ? ? ? ? ? ? ? ? ? ?break; ? ? ? ? ? ? ? ? ?p = e; ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? ?if (e != null) { // key相等會直接替換值并返回舊值 ? ? ? ? ? ? ?V oldValue = e.value; ? ? ? ? ? ? ?if (!onlyIfAbsent || oldValue == null) ? ? ? ? ? ? ? ? ?e.value = value; ? ? ? ? ? ? ?// 給LinkedHashMap擴展用的 ? ? ? ? ? ? ?afterNodeAccess(e); ? ? ? ? ? ? ?return oldValue; ? ? ? ? } ? ? } ? ? ?++modCount; ? ? ?if (++size > threshold) ? ? ? ? ?resize(); ? ? ?afterNodeInsertion(evict); ? ? ?return null; ?} ?? ?// 初始化容量或加倍表的大小 HashMap的底層數組table并不會在構造方法中創建，而是延遲到添加元素時創建 ?final Node<K,V>[] resize() { ? ? ?Node<K,V>[] oldTab = table; ? ? ?// 第一次添加元素進來resize時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) ? ? ? ? ? ? ?// 新的閾值×2 ? ? ? ? ? ? ?newThr = oldThr << 1; // double threshold ? ? } else if (oldThr > 0) { ? ? ? ? ?newCap = oldThr; ? ? } else { ? ? ? ? ?// 第一次添加元素，且使用空構造方法沒有指定閾值大小時進入這個分支 ? ? ? ? ?newCap = DEFAULT_INITIAL_CAPACITY; // 初始化容量為16 ? ? ? ? ?// 設置閾值大小 ? ? ? ? ?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; ? ? ?// 對老結構中所有的元素都進行重新hash ? ? ?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) ? ? ? ? ? ? ? ? ? ? ?// 如果當前桶只有一個Node節點，則不用起改變其在桶的位置 ? ? ? ? ? ? ? ? ? ? ?newTab[e.hash & (newCap - 1)] = e; ? ? ? ? ? ? ? ? ?else if (e instanceof TreeNode) ? ? ? ? ? ? ? ? ? ? ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); ? ? ? ? ? ? ? ? ?else { // e的后續仍有節點，且e不是樹節點 ? ? ? ? ? ? ? ? ? ? ?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) { // 索引為0的位置 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if (loTail == null) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?loHead = e; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?else ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?loTail.next = e; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?loTail = e; ? ? ? ? ? ? ? ? ? ? ? ? } else { // 索引為非0的位置 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?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; ?} ~~~ 總結put操作的過程： 1. 第一次添加元素時會調用resize方法擴容。該方法對所有的元素進行rehash，對于索引為0的桶的元素不改變其位置，對于其他元素則將整條鏈掛到當前索引+老容量的索引（j + oldCap）位置上去。 2. 如果桶中沒有元素則直接放入。 3. 如果桶中有元素了，有相同的鍵值替換值，沒有相同的鍵則發生沖突，采用尾插法的方式進行插入。 4. 在插入節點之后如果鏈表的長度大于8且桶的數量大于64則會轉成一棵樹結構。 &nbsp; ## TreeMap 底層是一個紅黑樹結構，能夠保證數據根據key排序，注意key不能為空。其結構如下 ~~~ Entry = (key、value、左子樹地址、右子樹地址、父節點地址、顏色) ~~~ ~~~ ?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類型來表示紅黑，BLACK和RED是一個常量 ? ? ?boolean color = BLACK; ?? ? // 新增的節點默認為黑色 ? ? ?Entry(K key, V value, Entry<K,V> parent) { ? ? ? ? ?this.key = key; ? ? ? ? ?this.value = value; ? ? ? ? ?this.parent = parent; ? ? } ?} ~~~ 源碼： ~~~ ?public class TreeMap<K,V> ? ? ?extends AbstractMap<K,V> ? ? ?implements NavigableMap<K,V>, Cloneable, java.io.Serializable ?{ ? ? ?// 比較器，TreeMap需要內部比較器或者外部比較器 ? ? ?private final Comparator<? super K> comparator; ? // 紅黑樹的樹根 ? ? ?private transient Entry<K,V> root; ? // 紅黑樹節點數量 ? ? ? ? ?private transient int size = 0; ? // 修改次數 ? ? ?private transient int modCount = 0; ? ? ? ? ? ?// 構造方法，key需要實現Comparable接口來實現內部的比較 ? ? ?public TreeMap() { ? ? ? ? ?comparator = null; ? ? } ? ? ?// 傳入自定義外部比較器 ? ? ?public TreeMap(Comparator<? super K> comparator) { ? ? ? ? ?this.comparator = comparator; ? ? } ? ? ? ? ? ? ? ? ?// -------------常見操作------------------------- ? ? ?// 添加元素 ? ? ?public V put(K key, V value) { // key和Value的類型在創建的時候就確定了 ? ? ? ? ?Entry<K,V> t = root; ? ? ? ? ?if (t == null) { ? ? ? ? ? ? ?// 比較兩個元素，有外部比較器優先調用外部比較器，沒有時調用內部比較器 ? ? ? ? ? ? ?compare(key, key); ? ? ? ? ? ? ?root = new Entry<>(key, value, null); ? ? ? ? ? ? ?size = 1; ? ? ? ? ? ? ?modCount++; ? ? ? ? ? ? ?return null; ? ? ? ? } ? ? ? ? ?int cmp; ? ? ? ? ?Entry<K,V> parent; ? ? ? ? ?// 將外部比較器賦值給cpr，看構造函數 ? ? ? ? ?Comparator<? super K> cpr = comparator; ? ? ? ? ?// cpr不等于null，意味著創建對象時調用有參構造器 ? ? ? ? ?if (cpr != null) { ? ? ? ? ? ? ?do { ? ? ? ? ? ? ? ? ?parent = t; ? ? ? ? ? ? ? ? ?cmp = cpr.compare(key, t.key); // 比較元素的key值 ? ? ? ? ? ? ? ? ?// cmp返回的就是int類型的數據 ? ? ? ? ? ? ? ? ?if (cmp < 0) ? ? ? ? ? ? ? ? ? ? ?t = t.left; ? ? ? ? ? ? ? ? ?else if (cmp > 0) ? ? ? ? ? ? ? ? ? ? ?t = t.right; ? ? ? ? ? ? ? ? ?else// cmp=0,即鍵相等，直接替換value的值，但是key不變，唯一的 ? ? ? ? ? ? ? ? ? ? ?return t.setValue(value); ? ? ? ? ? ? } while (t != null); ? ? ? ? } ? ? ? ? ?// 創建對象的時候沒有指定外部比較器，使用的是內部比較器 ? ? ? ? ?else { ? ? ? ? ? ? ?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); ? ? ? ? ? ? } 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; ? ? } ? ? ? ? ? ?// 獲取key對應的值 ? ? ?public V get(Object key) { ? ? ? ? ?Entry<K,V> p = getEntry(key); ? ? ? ? ?return (p==null ? null : p.value); ? ? } ? ? ? ? ? ?final Entry<K,V> getEntry(Object key) { ? ? ? ? ?// 由外部比較器則使用外部比較器比較獲取值 ? ? ? ? ?if (comparator != null) ? ? ? ? ? ? ?return getEntryUsingComparator(key); ? ? ? ? ?if (key == null) ? ? ? ? ? ? ?throw new NullPointerException(); ? ? ? ? ?@SuppressWarnings("unchecked") ? ? ? ? ? ? ?Comparable<? super K> k = (Comparable<? super K>) key; ? ? ? ? ?Entry<K,V> p = root; ? ? ? ? ?while (p != null) { ? ? ? ? ? ? ?int cmp = k.compareTo(p.key); ? ? ? ? ? ? ?if (cmp < 0) ? ? ? ? ? ? ? ? ?p = p.left; ? ? ? ? ? ? ?else if (cmp > 0) ? ? ? ? ? ? ? ? ?p = p.right; ? ? ? ? ? ? ?else ? ? ? ? ? ? ? ? ?return p; ? ? ? ? } ? ? ? ? ?return null; ? ? } ? ?} ~~~ &nbsp; 總結： 1. TreeMap底層就是一顆紅黑樹結構。 2. 節點的key需要實現內部比較器或者有自定義的外部比較器，有自定義的外部比較器的時候先使用外部比較器。 3. 節點的key不管在put還是在get都不能為空。 &nbsp; ## LinkedHashMap LinkedHashMap繼承HashMap，可以在HashMap的基礎上實現順序的訪問，其底層使用了雙向鏈表+HashMap來實現。由于新版本的HashMap會將鏈表轉化成樹結構，因此這里稱為“Linked”有點混淆，但是官方仍然采用了這個命名方式。 同時使用頭尾節點和回調函數來維護雙向鏈表的結構。回調函數在操作：access、insertion、removal后觸發。 更重要的一點是LinkedHashMap底層使用了LRU算法來維護節點的順序。 源碼： ~~~ ?public class LinkedHashMap<K,V> ? ? ?extends HashMap<K,V> ? ? ?implements Map<K,V> ?{ ? ? ?/** ? ? ? * 頭節點、也是最久沒有使用的節點 ? ? ? */ ? ? ?transient LinkedHashMap.Entry<K,V> head; ?? ? ? ?/** ? ? ? * 尾結點、也是最近使用的節點 ? ? ? */ ? ? ?transient LinkedHashMap.Entry<K,V> tail; ? ? ? ? ? ?/** ? * true：按照訪問順序遍歷、LRU算法 ? * false：按照插入順序遍歷 ? ? ? */ ? ? ?final boolean accessOrder; ? ? ? ? ? ? ? ? ?public LinkedHashMap(int initialCapacity, float loadFactor) { ? ? ? ? ?super(initialCapacity, loadFactor); ? ? ? ? ?accessOrder = false; ? ? } ? ? ?public LinkedHashMap(int initialCapacity) { ? ? ? ? ?super(initialCapacity); ? ? ? ? ?accessOrder = false; ? ? } ? ? ?public LinkedHashMap() { ? ? ? ? ?super(); ? ? ? ? ?accessOrder = false; ? ? } ? ? ?// 要使用LRU算法則需將accessOrder設置為true ? ? ?public LinkedHashMap(int initialCapacity, ? ? ? ? ? ? ? ? ? ? ? ? ? float loadFactor, ? ? ? ? ? ? ? ? ? ? ? ? ? boolean accessOrder) { ? ? ? ? ?super(initialCapacity, loadFactor); ? ? ? ? ?this.accessOrder = accessOrder; ? ? } ? ? ? ? ? ? ? ? ?/**---------------------常用操作----------------------------*/ ? ? ?public V get(Object key) { ? ? ? ? ?Node<K,V> e; ? ? ? ? ?if ((e = getNode(hash(key), key)) == null) ? ? ? ? ? ? ?return null; ? ? ? ? ?if (accessOrder) ? ? ? ? ? ? ?// 如果是按照訪問順序只要調用回調函數 ? ? ? ? ? ? ?afterNodeAccess(e); ? ? ? ? ?return e.value; ? ? } ? ? ?// 將當前最近一次訪問的節點移動到鏈表尾部 ? ? ?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：當前訪問節點的上一個節點，a：當前訪問節點的下一個節點 ? ? ? ? ? ? b = p.before, a = p.after; ? ? ? ? ? ? ?p.after = null; ? ? ? ? ? ? ?if (b == null) ? ? ? ? ? ? ? ? ?// p就是頭結點 ? ? ? ? ? ? ? ? ?head = a; ? ? ? ? ? ? ?else ? ? ? ? ? ? ? ? ?// p節點要移除到最后一個位置的 ? ? ? ? ? ? ? ? ?b.after = a; ? ? ? ? ? ? ? ? ? ? ? ? ? ?if (a != null) ? ? ? ? ? ? ? ? ?// p不是最后一個元素 ? ? ? ? ? ? ? ? ?a.before = b; ? ? ? ? ? ? ?else ? ? ? ? ? ? ? ? ?last = b; ? ? ? ? ? ? ? ? ? ? ? ? ? ?if (last == null) ? ? ? ? ? ? ? ? ?// 第一次訪問， ? ? ? ? ? ? ? ? ?head = p; ? ? ? ? ? ? ?else { ? ? ? ? ? ? ? ? ?p.before = last; ? ? ? ? ? ? ? ? ?last.after = p; ? ? ? ? ? ? } ? ? ? ? ? ? ?tail = p; ? ? ? ? ? ? ?++modCount; ? ? ? ? } ? ? } ?} ~~~ &nbsp; ### 使用LinkedHashMap實現LRU緩存 ```java class LRUCache extends LinkedHashMap<Integer, Integer>{ private int capacity; public LRUCache(int capacity) { // 傳遞true會使用LRU算法 super(capacity, 0.75f, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } // 重寫這個方法，實現超過容量時移除 @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { // 節點數大于容量時需要移除 return size() > capacity; } } ``` &nbsp; ## 總結 1. HashMap、TreeMap、LinkedHashMap底層都是由紅黑樹結構的存在。 2. TreeMap可以實現key有序，LinkedHashMap可以實現訪問有序和LRU緩存。