理解LinkedHashMap

成都創(chuàng)新互聯(lián)公司是專業(yè)的靖安網(wǎng)站建設(shè)公司，靖安接單;提供網(wǎng)站設(shè)計、網(wǎng)站建設(shè),網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行靖安網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊,希望更多企業(yè)前來合作!

1. LinkedHashMap概述：

LinkedHashMap是HashMap的一個子類，它保留插入的順序，如果需要輸出的順序和輸入時的相同，那么就選用LinkedHashMap。

   LinkedHashMap是Map接口的哈希表和鏈接列表實現(xiàn)，具有可預(yù)知的迭代順序。此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
   LinkedHashMap實現(xiàn)與HashMap的不同之處在于，后者維護(hù)著一個運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。
   注意，此實現(xiàn)不是同步的。如果多個線程同時訪問鏈接的哈希映射，而其中至少一個線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步。

根據(jù)鏈表中元素的順序可以分為：按插入順序的鏈表，和按訪問順序(調(diào)用get方法)的鏈表。

默認(rèn)是按插入順序排序，如果指定按訪問順序排序，那么調(diào)用get方法后，會將這次訪問的元素移至鏈表尾部，不斷訪問可以形成按訪問順序排序的鏈表。可以重寫removeEldestEntry方法返回true值指定插入元素時移除最老的元素。

2. LinkedHashMap的實現(xiàn)：

對于LinkedHashMap而言，它繼承與HashMap、底層使用哈希表與雙向鏈表來保存所有元素。其基本操作與父類HashMap相似，它通過重寫父類相關(guān)的方法，來實現(xiàn)自己的鏈接列表特性。下面我們來分析LinkedHashMap的源代碼：

類結(jié)構(gòu)：

public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V>

1) 成員變量：

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了數(shù)組中保存的元素Entry，該Entry除了保存當(dāng)前對象的引用外，還保存了其上一個元素before和下一個元素after的引用，從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表?？丛创a：

//true表示按照訪問順序迭代，false時表示按照插入順序
private final boolean accessOrder;

/**
* 雙向鏈表的表頭元素。
*/
private transient Entry<K,V> header;
/**
* LinkedHashMap的Entry元素。
* 繼承HashMap的Entry元素，又保存了其上一個元素before和下一個元素after的引用。
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
……
}

HashMap.Entry:

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}

2) 初始化：

通過源代碼可以看出，在LinkedHashMap的構(gòu)造方法中，實際調(diào)用了父類HashMap的相關(guān)構(gòu)造方法來構(gòu)造一個底層存放的table數(shù)組。如：

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}

HashMap中的相關(guān)構(gòu)造方法：

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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}

我們已經(jīng)知道LinkedHashMap的Entry元素繼承HashMap的Entry，提供了雙向鏈表的功能。在上述HashMap的構(gòu)造器中，最后會調(diào)用init()方法，進(jìn)行相關(guān)的初始化，這個方法在HashMap的實現(xiàn)中并無意義，只是提供給子類實現(xiàn)相關(guān)的初始化調(diào)用。
LinkedHashMap重寫了init()方法，在調(diào)用父類的構(gòu)造方法完成構(gòu)造后，進(jìn)一步實現(xiàn)了對其元素Entry的初始化操作。

void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}

3) 存儲：

LinkedHashMap并未重寫父類HashMap的put方法，而是重寫了父類HashMap的put方法調(diào)用的子方法void recordAccess(HashMap m) ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的雙向鏈接列表的實現(xiàn)。

HashMap.put:

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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;
}

重寫方法：

void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

void addEntry(int hash, K key, V value, int bucketIndex) {
// 調(diào)用create方法，將新元素以雙向鏈表的的形式加入到映射中。
createEntry(hash, key, value, bucketIndex);
// 刪除最近最少使用元素的策略定義
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}

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;
// 調(diào)用元素的addBrefore方法，將元素加入到哈希、雙向鏈接列表。
e.addBefore(header);
size++;
}

private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}

4) 讀取：

LinkedHashMap重寫了父類HashMap的get方法，實際在調(diào)用父類getEntry()方法取得查找的元素后，再判斷當(dāng)排序模式accessOrder為true時，記錄訪問順序，將最新訪問的元素添加到雙向鏈表的表頭，并從原來的位置刪除。由于的鏈表的增加、刪除操作是常量級的，故并不會帶來性能的損失。

HashMap.containsValue:

public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}

/*查找Map中是否包含給定的value，還是考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。
*/
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;
}

/*該transfer()是HashMap中的實現(xiàn)：遍歷整個表的各個桶位，然后對桶進(jìn)行遍歷得到每一個Entry，重新hash到newTable中，
//放在這里是為了和下面LinkedHashMap重寫該法的比較，
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);
}
}
}
*/
/**
*transfer()方法是其父類HashMap調(diào)用resize()的時候調(diào)用的方法，它的作用是表擴(kuò)容后，把舊表中的key重新hash到新的表中。
*這里從寫了父類HashMap中的該方法，是因為考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。
*/
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);
e.next = newTable[index];
newTable[index] = e;
}
}

public V get(Object key) {
// 調(diào)用父類HashMap的getEntry()方法，取得要查找的元素。
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 記錄訪問順序。
e.recordAccess(this);
return e.value;
}

void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果定義了LinkedHashMap的迭代順序為訪問順序，
// 則刪除以前位置上的元素，并將最新訪問的元素添加到鏈表表頭。
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}

/**clear鏈表，設(shè)置header為初始狀態(tài)*/
public void clear() {
super.clear();
header.before = header.after = header;
}

5) 排序模式：

LinkedHashMap定義了排序模式accessOrder，該屬性為boolean型變量，對于訪問順序，為true；對于插入順序，則為false。

private final boolean accessOrder;

一般情況下，不必指定排序模式，其迭代順序即為默認(rèn)為插入順序?？碙inkedHashMap的構(gòu)造方法，如：

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}

這些構(gòu)造方法都會默認(rèn)指定排序模式為插入順序。如果你想構(gòu)造一個LinkedHashMap，并打算按從近期訪問最少到近期訪問最多的順序（即訪問順序）來保存元素，那么請使用下面的構(gòu)造方法構(gòu)造LinkedHashMap：

public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

該哈希映射的迭代順序就是最后訪問其條目的順序，這種映射很適合構(gòu)建LRU緩存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法。該方法可以提供在每次添加新條目時移除最舊條目的實現(xiàn)程序，默認(rèn)返回false，這樣，此映射的行為將類似于正常映射，即永遠(yuǎn)不能移除最舊的元素。

當(dāng)有新元素加入Map的時候會調(diào)用Entry的addEntry方法，會調(diào)用removeEldestEntry方法，這里就是實現(xiàn)LRU元素過期機(jī)制的地方，默認(rèn)的情況下removeEldestEntry方法只返回false表示元素永遠(yuǎn)不過期。

/**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
/**
* This override differs from addEntry in that it doesn't resize the
* table or remove the eldest entry.
*/
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++;
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}

此方法通常不以任何方式修改映射，相反允許映射在其返回值的指引下進(jìn)行自我修改。如果用此映射構(gòu)建LRU緩存，則非常方便，它允許映射通過刪除舊條目來減少內(nèi)存損耗。

例如：重寫此方法，維持此映射只保存100個條目的穩(wěn)定狀態(tài)，在每次添加新條目時刪除最舊的條目。

private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}

其實LinkedHashMap幾乎和HashMap一樣，不同的是它定義了一個Entry<K,V> header，這個header不是放在Table里，它是額外獨立出來的。LinkedHashMap通過繼承hashMap中的Entry<K,V>,并添加兩個屬性Entry<K,V> before,after,和header結(jié)合起來組成一個雙向鏈表，來實現(xiàn)按插入順序或訪問順序排序。

本文名稱：理解LinkedHashMap
文章網(wǎng)址：http://bm7419.com/article42/igdoec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、網(wǎng)站制作、云服務(wù)器、自適應(yīng)網(wǎng)站、網(wǎng)站內(nèi)鏈、App設(shè)計

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容