LinkedHashMap如何保證有序問題
LinkedHashMap如何保證有序
我們常說linkedHashMap是有序的,這個有序也是分為兩種的,分別是:插入順序和訪問順序,我們可以通俗的認為:linkedHashMap = hashmap + 雙向鏈表
以下的學習是基于jdk8

根據(jù)linkedHashMap的結構來看,是依賴于hashmap的,通過查看源碼,我們也會發(fā)現(xiàn),linkedHashMap只是維護了一個鏈表,并沒有put、remove方法的具體實現(xiàn),
因為linkedHashMap的設計思想是:對數(shù)據(jù)的操作,是依賴于hashmap中的方法,只是在其中的一些細節(jié)方法,linkedHashMap會進行擴展,接下來我們先說屬性有哪些
屬性信息
/**
* The head (eldest) of the doubly linked list.
* 鏈表的head節(jié)點
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
* 鏈表的尾結點
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* false:表示插入順序;true表示讀取順序
* @serial
*/
final boolean accessOrder;AccessOrder
該屬性是來區(qū)分當前l(fā)inkedHashMap是按照訪問順序排序,還是按照put順序有序,當該參數(shù)為true的時候,表示按照讀取順序有序;默認為false,按照put順序有序
newNode()
在調(diào)用put方法的時候,會調(diào)用父類hashmap的put方法,那linkedHashMap如何維護節(jié)點之間的順序呢?
在put方法中,如果得到當前key要存儲的位置,會調(diào)用newNode()方法,初始化一個node節(jié)點,

linkedHashMap對該方法,進行了覆寫,
/**
* 在向map中put元素的時候,是會初始化一個node節(jié)點,如果是linkedHashMap,調(diào)用的是該方法
* 在該方法中,可以看到,會初始化一個LinkedHashMap.Entry節(jié)點,然后將該節(jié)點插入到linkedHashMap的雙向鏈表中
* 默認是加到鏈表尾部
* @param hash
* @param key
* @param value
* @param e
* @return
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}這里可以看到,除了初始化一個節(jié)點之外,還會調(diào)用linkNodeLast方法,在linkedNodeLast方法中,會將p節(jié)點添加到自己維護的雙向鏈表的尾部
/**
* 這是加入到鏈表尾部的方法
* 如果當前是第一個put的元素,那p就是head,否則,就把節(jié)點放到tail的后面
* @param p
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}按訪問順序有序
假如在初始化linkedHashMap對象的時候,指定accessOrder為true,那表示按照訪問順序有序,在get方法中,會對訪問到的元素進行處理
public V get(Object key) {
Node<K,V> e;
// 這里的getNode調(diào)用的是hashmap中的方法,獲取到當前key所對應的value
if ((e = getNode(hash(key), key)) == null)
return null;
/**
* 如果是按照訪問順序有序,會把獲取到的e節(jié)點插入到鏈表的尾部,然后返回e.value
*/
if (accessOrder)
afterNodeAccess(e);
return e.value;
}這里可以看到,如果是按照訪問順序有序的話,會額外調(diào)用afterNodeAccess()方法,如果為false,會直接返回獲取到的節(jié)點value值,afterNodeAccess方法簡單而言,就是將e節(jié)點移到鏈表的尾部,所以,我們可以認為,最近訪問的在元素在鏈表的最后面
所以:對于按照put順序有序的設置,在put元素的時候,本身就會把最新插入的元素放入到鏈表的尾部,如果是按照訪問順序有序的話,在get的時候,會把訪問的元素移到鏈表的尾部,根據(jù)該特點,也可以實現(xiàn)一個簡單的LRU算法
對于hashmap和linkedHashMap來說,最大的區(qū)別就是:hashmap是無序的,linkedHashMap自己維護了節(jié)點的順序
LinkedHashMap實現(xiàn)有序的原理
LinkedHashMap采用的hash算法和HashMap相同,但是它重新定義了數(shù)組中保存的元素Entry,該Entry除了保存當前對象的引用外,還保存了其上一個元素before和下一個元素after的引用,從而在哈希表的基礎上又構成了雙向鏈接列表。
這樣就能按照插入的順序遍歷原本無序的HashMap了,是不是很方便?
看源代碼:
/**
* 雙向鏈表的表頭元素。
*/
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;
……
} 以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關文章
SpringCloud的@RefreshScope 注解你了解嗎
這篇文章主要介紹了Spring Cloud @RefreshScope 原理及使用,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-09-09
Springboot整合Socket實現(xiàn)單點發(fā)送,廣播群發(fā),1對1,1對多實戰(zhàn)
本文主要介紹了Springboot整合Socket實現(xiàn)單點發(fā)送,廣播群發(fā),1對1,1對多實戰(zhàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2022-08-08
Springboot @Validated和@Valid的區(qū)別及使用詳解
這篇文章主要介紹了Springboot @Validated和@Valid的區(qū)別及使用詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
JavaWeb response完成重定向實現(xiàn)過程詳解
這篇文章主要介紹了JavaWeb response完成重定向實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-02-02

