LinkedHashMap是為了解決遍歷Hash表的無序問題，它內部維護了一個鏈表用于記錄你插入元素（或你訪問元素的順序）的位置，遍歷時直接遍歷鏈表，元素的順序即為你插入的順序，但是Entry對象要多加兩個成員變量before和after用于記錄鏈表的前驅和后繼。所以LinkedHashMap的的存儲效率要低于HashMap，但是遍歷效率要高于HashMap。?

import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;


/**
?* LinkedHashMap內部不僅存儲了一個散列表，
?* 也維護了一個鏈表，
?* 根據鏈表中元素的順序可以分為：按插入順序的鏈表，和按訪問順序(調用get方法)的鏈表。
?* 默認是按插入順序排序，如果指定按訪問順序排序，那么調用get方法后，會將這次訪問的元素
?* 移至鏈表尾部，不斷訪問可以形成按訪問順序排序的鏈表。
?* 可以重寫removeEldestEntry方法返回true值指定插入元素時移除最老的元素
?*/
public class LinkedHashMap<K,V> extends HashMap<K,V>
? ? implements Map<K,V>
{


? ? private static final long serialVersionUID = 3801124242820219131L;


? ? /**
? ? ?* 此Map中維護的一個雙向循環鏈表的頭節點
? ? ?*/
? ? private transient Entry<K,V> header;


? ? /**
? ? ?*?
? ? ?* 遍歷Map的順序的變量，
? ? ?* true為按訪問順序遍歷
? ? ?* false為按插入順序遍歷
? ? ?*/
? ? private final boolean accessOrder;


? ? /**
? ? ?*?
? ? ?* 構造一個空的，按插入順序遍歷的LinkedHashMap實例，
? ? ?* 初始容量與加載因子由自己指定
? ? ?*/
? ? public LinkedHashMap(int initialCapacity, float loadFactor) {
? ? ? ? super(initialCapacity, loadFactor);
? ? ? ? accessOrder = false;
? ? }


? ? /**
? ? ?* 構造一個空的，按插入順序遍歷的LinkedHashMap實例，
? ? ?* 初始容量由自己指定
? ? ?*/
? ? public LinkedHashMap(int initialCapacity) {
? ? super(initialCapacity);
? ? ? ? accessOrder = false;
? ? }


? ? /**
? ? ?*?
? ? ?* 構造一個空的，按插入順序遍歷的LinkedHashMap實例
? ? ?* 初始容量與加載因子按HashMap的默認值16與0.75
? ? ?*/
? ? public LinkedHashMap() {
? ? super();
? ? ? ? accessOrder = false;
? ? }


? ? /**
? ? ?* 構造一個非空，按插入順序遍歷的LinkedHashMap實例
? ? ?*/
? ? public LinkedHashMap(Map<? extends K, ? extends V> m) {
? ? ? ? super(m);
? ? ? ? accessOrder = false;
? ? }


? ? public LinkedHashMap(int initialCapacity,
float loadFactor,
? ? ? ? ? ? ? ? ? ? ? ? ?boolean accessOrder) {
? ? ? ? super(initialCapacity, loadFactor);
? ? ? ? this.accessOrder = accessOrder;
? ? }
? ??
? ? /**
? ? ?*?
? ? ?* 在HashMap每個構造方法中都會調用一次此init()方法
? ? ?* 這里是初始化一個雙向循環鏈表的頭節點
? ? ?*/
? ? void init() {
? ? ? ? header = new Entry<K,V>(-1, null, null, null);
? ? ? ? header.before = header.after = header;
? ? }


? ? /**
? ? ?*?
? ? ?* 在父類HashMap進行容量擴充時會調用此方法
? ? ?* 把原來Entry數組中的對象經過重新計算索引轉移到此newTable中
? ? ?* 這里與HashMap中的transfer方法的實現不再相同，而且比它更快。
? ? ?*?
? ? ?* HashMap是遍歷Entry數組，需要檢查是否為null，如果不為空的話則就需
? ? ?* 要遍歷數組中的鏈表，而這里所有的元素都鏈接成了一個鏈表，直接遍歷此
? ? ?* 鏈表就可以遍歷出LinkedHashMap中的所有元素。
? ? ?*/
? ? void transfer(HashMap.Entry[] newTable) {
? ? ? ? int newCapacity = newTable.length;
? ? ? ? for (Entry<K,V> e = header.after; e != header; e = e.after) {
? ? ? ? ? ? int index = indexFor(e.hash, newCapacity); //根據新容量重新計算index
? ? ? ? ? ? e.next = newTable[index]; //最后添加的節點放最前面
? ? ? ? ? ? newTable[index] = e;
? ? ? ? }
? ? }




? ? /**
? ? ?*?
? ? ?* ?查找Map中是否含有本值，這里重寫了HashMap的containsValue方法
? ? ?* ?因為在LinkedHashMap中只需要遍歷鏈表查找，這比HashMap遍歷table查找更加
? ? ?* ?高效和快速
? ? ?*/
? ? public boolean containsValue(Object value) {
? ? ? ? // Overridden to take advantage of faster iterator
? ? ? ? if (value==null) {
? ? ? ? ? ? for (Entry e = header.after; e != header; e = e.after)
? ? ? ? ? ? ? ? if (e.value==null)
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? } else {
? ? ? ? ? ? for (Entry e = header.after; e != header; e = e.after)
? ? ? ? ? ? ? ? if (value.equals(e.value))
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? return false;
? ? }


? ? /**
? ? ?*?
? ? ?* 通過key值獲得value，如果沒有找到此key則返回null。
* 不過返回null也可能是其value為null
* 通過contain方法可判斷Map中是否含有此鍵
*?
* 重寫此方法的原因是：
* 如果map中鏈表是按照訪問順序進行排序，
* 就需要把本次訪問的元素移到鏈表尾部，表示
* 這是你最新訪問的元素,以后可能會繼續訪問它
*?
? ? ?*/
? ? public V get(Object key) {
? ? ? ? Entry<K,V> e = (Entry<K,V>)getEntry(key);
? ? ? ? if (e == null)
? ? ? ? ? ? return null;
? ? ? ? e.recordAccess(this);
? ? ? ? return e.value;
? ? }


? ? /**
? ? ?* 移除元素，清空鏈表
? ? ?*/
? ? public void clear() {
? ? ? ? super.clear();
? ? ? ? header.before = header.after = header;
? ? }


? ? /**
? ? ?* LinkedHashMap 的Entry對象.
? ? ?*/
? ? private static class Entry<K,V> extends HashMap.Entry<K,V> {
? ? ? ? // 包含其前驅和后繼的信息.
? ? ? ? Entry<K,V> before, after;


? ? ? ? Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
? ? ? ? ? ? super(hash, key, value, next);
? ? ? ? }


? ? ? ? /**
? ? ? ? ?*?
? ? ? ? ?* 在鏈表中移除此對象只需要修改前驅和后繼的指針
? ? ? ? ?*/
? ? ? ? private void remove() {
? ? ? ? ? ? before.after = after;
? ? ? ? ? ? after.before = before;
? ? ? ? }


? ? ? ? /**
? ? ? ? ?*?
? ? ? ? ?* 把元素插入到指定的存在的元素之前
? ? ? ? ?* 鏈表的插入也是修改指針
? ? ? ? ?*/
? ? ? ? private void addBefore(Entry<K,V> existingEntry) {
? ? ? ? ? ? after ?= existingEntry;
? ? ? ? ? ? before = existingEntry.before;
? ? ? ? ? ? before.after = this;
? ? ? ? ? ? after.before = this;
? ? ? ? }


? ? ? ? /**
? ? ? ? ?*?
? ? ? ? ?* 當調用父類的put或putAll方法，發現要插入的鍵已經存在時會調用此方法，
? ? ? ? ?* 當調用LinkedHashMap的get方法時會調用此方法。
? ? ? ? ?* 如果LinkedHashMap是按訪問順序遍歷的，就移動此Entry
? ? ? ? ?* 到鏈表的最后位置，否則do nothing
? ? ? ? ?*/
? ? ? ? void recordAccess(HashMap<K,V> m) {
? ? ? ? ? ? LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
? ? ? ? ? ? if (lm.accessOrder) {
? ? ? ? ? ? ? ? lm.modCount++;
? ? ? ? ? ? ? ? remove(); //移除它
? ? ? ? ? ? ? ? addBefore(lm.header); //再把她添加到鏈表尾部
? ? ? ? ? ? }
? ? ? ? }


? ? ? ? /**
? ? ? ? ?* 在移除元素時會調用此方法，即調用
? ? ? ? ?* 父類的remove(key)方法時調用它
? ? ? ? ?* 這里是改變鏈表指針，移除鏈表中的此元素
? ? ? ? ?*/
? ? ? ? void recordRemoval(HashMap<K,V> m) {
? ? ? ? ? ? remove();
? ? ? ? }
? ? }


? ? private abstract class LinkedHashIterator<T> implements Iterator<T> {
? ? Entry<K,V> nextEntry ? ?= header.after; //初始為第一個元素
? ? Entry<K,V> lastReturned = null;


? ? /**
? ? * 檢測同步
? ? */
int expectedModCount = modCount;


public boolean hasNext() {
? ? ? ? ? ?return nextEntry != header;
}


public void remove() {
? ?if (lastReturned == null)
? ? throw new IllegalStateException();
? ?if (modCount != expectedModCount)
? ? throw new ConcurrentModificationException();

? ? ? ?LinkedHashMap.this.remove(lastReturned.key);
? ? ? ?lastReturned = null;
? ? ? ?expectedModCount = modCount;
}


Entry<K,V> nextEntry() {
? ?if (modCount != expectedModCount)
? ? throw new ConcurrentModificationException();
? ? ? ?if (nextEntry == header)
? ? ? ? ? ?throw new NoSuchElementException();

? ? ? ?Entry<K,V> e = lastReturned = nextEntry;
? ? ? ?nextEntry = e.after;
? ? ? ?return e;
}
? ? }


? ? //依次重寫next方法，返回不同的迭代器。
? ? private class KeyIterator extends LinkedHashIterator<K> {
? ? public K next() { return nextEntry().getKey(); }
? ? }


? ? private class ValueIterator extends LinkedHashIterator<V> {
? ? public V next() { return nextEntry().value; }
? ? }


? ? private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
? ? public Map.Entry<K,V> next() { return nextEntry(); }
? ? }


? ? // These Overrides alter the behavior of superclass view iterator() methods
? ? Iterator<K> newKeyIterator() ? { return new KeyIterator(); ? }
? ? Iterator<V> newValueIterator() { return new ValueIterator(); }
? ? Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }


? ? /**
? ? ?*?
? ? ?* 重寫父類addEntry方法
? ? ?*/
? ? void addEntry(int hash, K key, V value, int bucketIndex) {
? ? ? ? createEntry(hash, key, value, bucketIndex);


? ? ? ??
? ? ? ? /*如果子類重寫了removeEldestEntry方法并返回true，
? ? ? ? ? ? ? ? ? ? ? ? ? 將在map中移除鏈表中的第一個元素，否則檢測是否需要擴充容量。
? ? ? ? ? eldest元素即為鏈表中的第一個元素*/
? ? ? ? Entry<K,V> eldest = header.after;
? ? ? ? if (removeEldestEntry(eldest)) {
? ? ? ? ? ? removeEntryForKey(eldest.key);
? ? ? ? } else {
? ? ? ? ? ? if (size >= threshold)
? ? ? ? ? ? ? ? resize(2 * table.length); //擴充至原來的2倍
? ? ? ? }
? ? }


? ? /**
? ? ?*?
? ? ?* 重寫父類的createEntry方法，此方法不需要檢測是否要擴充容量，
? ? ?* 與HashMap中此方法的唯一區別時，這里不僅把元素插入到散列表中，
? ? ?* 而且將元素插入到了鏈表尾
? ? ?*/
? ? void createEntry(int hash, K key, V value, int bucketIndex) {
? ? ? ? HashMap.Entry<K,V> old = table[bucketIndex];
? ? ? ? Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
? ? ? ? table[bucketIndex] = e;
? ? ? ? e.addBefore(header);
? ? ? ? size++;
? ? }


? ? /**
? ? ?*?
? ? ?* 此方法會在調用put()或putAll()方法時調用，此方法告訴linkedHashMap
? ? ?* 是否在添加一個元素后移除最老的元素
? ? ?* 比如下面代碼會讓LinedHashMap的大小始終保持在100
? ? ?* ? ? private static final int MAX_ENTRIES = 100;
? ? ?*
? ? ?* ? ? protected boolean removeEldestEntry(Map.Entry eldest) {
? ? ?* ? ? ? ?return size() > MAX_ENTRIES;
? ? ?* ? ? }
? ? ?* ?此方法默認返回false，需要子類去復寫此方法
? ? ?* ?
? ? ?* ?什么是eldest元素?
? ? ?* ?如果按插入問順序來說，是map中最先插入的元素
? ? ?* ?如果按訪問順序來說，是map中最久未被訪問的元素
? ? ?*/
? ? protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
? ? ? ? return false;
? ? }
}
關于LinkedHashSet?

/**
?* LinkedHashSet實際上是基于LinkedHashMap的基礎上實現的，
?* LinkedHashSet繼承自HashSet，在HashSet中有一構造方法
?* HashSet(int initialCapacity, float loadFactor, boolean dummy)?
?* 第三個參數dummy為true時new出了一個LinkedHashMap實例，以Set中的
?* 元素為鍵，以一個Object的虛假的對象為值，所以HashSet中的元素不可能重復。
?* 以下構造函數dummy都為true
?*/
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {


private static final long serialVersionUID = -2851667679971038690L;




public LinkedHashSet(int initialCapacity, float loadFactor) {
? ? super(initialCapacity, loadFactor, true);
}




public LinkedHashSet(int initialCapacity) {
? ? super(initialCapacity, .75f, true);
}




public LinkedHashSet() {
? ? super(16, .75f, true);
}




public LinkedHashSet(Collection<? extends E> c) {
? ? super(Math.max(2*c.size(), 11), .75f, true);
? ? addAll(c);
}
}

總結

以上是生活随笔為你收集整理的集合框架源码分析五之LinkedHashMap，LinkedHashSet的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。