欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java LinkedHashMap 底層實現(xiàn)原理分析

 更新時間：2021年05月21日 09:57:11   作者：yanliang  
LinkedHashMap繼承自HashMap實現(xiàn)了Map接口。基本實現(xiàn)同HashMap一樣，不同之處在于LinkedHashMap保證了迭代的有序性。其內部維護了一個雙向鏈表，解決了 HashMap不能隨時保持遍歷順序和插入順序一致的問題。

在實現(xiàn)上，LinkedHashMap很多方法直接繼承自HashMap，僅為維護雙向鏈表覆寫了部分方法。所以，要看懂 LinkedHashMap 的源碼，需要先看懂 HashMap 的源碼。

默認情況下，LinkedHashMap的迭代順序是按照插入節(jié)點的順序。也可以通過改變accessOrder參數(shù)的值，使得其遍歷順序按照訪問順序輸出。

這里我們只討論LinkedHashMap和HashMap的不同之處，LinkedHashMap的其他操作和特性具體請參考HashMap

我們先來看下兩者的區(qū)別：

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Test04 {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<String, String>();
        map.put("ahdjkf", "1");
        map.put("ifjdj", "2");
        map.put("giafdja", "3");
        map.put("agad", "4");
        map.put("ahdjkge", "5");
        map.put("iegnj", "6");
        System.out.println("LinkedHashMap的迭代順序(accessOrder=false)：");
        Iterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map1 = new LinkedHashMap<String, String>(16,0.75f,true);
        map1.put("ahdjkf", "1");
        map1.put("ifjdj", "2");
        map1.put("giafdja", "3");
        map1.put("agad", "4");
        map1.put("ahdjkge", "5");
        map1.put("iegnj", "6");

        map1.get("ahdjkf");
        map1.get("ifjdj");
        System.out.println("LinkedHashMap的迭代順序(accessOrder=true)：");
        Iterator iterator1 = map1.entrySet().iterator();
        while (iterator1.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator1.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map2 = new HashMap<>();
        map2.put("ahdjkf", "1");
        map2.put("ifjdj", "2");
        map2.put("giafdja", "3");
        map2.put("agad", "4");
        map2.put("ahdjkge", "5");
        map2.put("iegnj", "6");

        System.out.println("HashMap的迭代順序：");    
        Iterator iterator2 = map2.entrySet().iterator();
        while (iterator2.hasNext()) {
            Map.Entry aMap = (Map.Entry) iterator2.next();
            System.out.println(aMap.getKey() + "=" + aMap.getValue());
        }
    }
}
Output：
LinkedHashMap的迭代順序(accessOrder=false)：
ahdjkf=1
ifjdj=2
giafdja=3
agad=4
ahdjkge=5
iegnj=6
LinkedHashMap的迭代順序(accessOrder=true)：
giafdja=3
agad=4
ahdjkge=5
iegnj=6
ahdjkf=1
ifjdj=2
HashMap的迭代順序：
iegnj=6
giafdja=3
ifjdj=2
agad=4
ahdjkf=1
ahdjkge=5

可以看到 LinkedHashMap在每次插入數(shù)據(jù)，訪問、修改數(shù)據(jù)時都會調整鏈表的節(jié)點順序。以決定迭代時輸出的順序。

下面我們來看LinkedHashMap具體是怎么實現(xiàn)的：

LinkedHashMap繼承了HashMap，內部靜態(tài)類Entry繼承了HashMap的Entry，但是LinkedHashMap.Entry多了兩個字段：before和after，before表示在本節(jié)點之前添加到LinkedHashMap的那個節(jié)點，after表示在本節(jié)點之后添加到LinkedHashMap的那個節(jié)點，這里的之前和之后指時間上的先后順序。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

同時類里有兩個成員變量head和tail,分別指向內部雙向鏈表的表頭、表尾。

//雙向鏈表的頭結點
transient LinkedHashMap.Entry<K,V> head;
//雙向鏈表的尾節(jié)點
transient LinkedHashMap.Entry<K,V> tail;

將LinkedHashMap的accessOrder字段設置為true后，每次訪問哈希表中的節(jié)點都將該節(jié)點移到鏈表的末尾，表示該節(jié)點是最新訪問的節(jié)點。即循環(huán)雙向鏈表的頭部存放的是最久訪問的節(jié)點或最先插入的節(jié)點，尾部為最近訪問的或最近插入的節(jié)點。

由于增加了一個accessOrder屬性，LinkedHashMap相對HashMap來說增加了一個構造方法用來控制迭代順序。

final boolean accessOrder;
public LinkedHashMap() {
    super();
    accessOrder = false;
}
//指定初始化時的容量，
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
//指定初始化時的容量，和擴容的加載因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
//指定初始化時的容量，和擴容的加載因子，以及迭代輸出節(jié)點的順序
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
//利用另一個Map 來構建
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    //該方法上文分析過，批量插入一個map中的所有數(shù)據(jù)到 本集合中。
    putMapEntries(m, false);
}

添加元素

LinkedHashMap在添加元素的時候，依舊使用的是HashMap中的put方法。不同的是LinkedHashMap重寫了newNode()方法在每次構建新節(jié)點時，通過linkNodeLast(p);將新節(jié)點鏈接在內部雙向鏈表的尾部。

//將新增的節(jié)點，連接在鏈表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    //如果集合之前是空的
    if (last == null)
        head = p;
    else {//將新節(jié)點連接在鏈表的尾部
        p.before = last;
        last.after = p;
    }
}

刪除元素

LinkedHashMap并沒有重寫HashMap的remove()方法，但是他重寫了afterNodeRemoval()方法，這個方法的作用是在刪除一個節(jié)點時，同步將該節(jié)點從雙向鏈表中刪除。該方法將會在remove中被回調。

//在刪除節(jié)點e時，同步將e從雙向鏈表上刪除
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //將待刪除節(jié)點 p 的前置后置節(jié)點都置空
    p.before = p.after = null;
    //如果前置節(jié)點是null，則說明現(xiàn)在的頭結點應該是后置節(jié)點a
    if (b == null)
        head = a;
    else//否則將前置節(jié)點b的后置節(jié)點指向a
        b.after = a;
    //同理如果后置節(jié)點時null ，則尾節(jié)點應是b
    if (a == null)
        tail = b;
    else//否則更新后置節(jié)點a的前置節(jié)點為b
        a.before = b;
}

刪除過程總的來說可以分為三步：

  1. 根據(jù) hash 定位到桶位置
  2. 遍歷鏈表或調用紅黑樹相關的刪除方法
  3. 回調afterNodeRemoval，從 LinkedHashMap 維護的雙鏈表中移除要刪除的節(jié)點

更新元素

// 清除節(jié)點時要將頭尾節(jié)點一起清除 
public void clear() {
    super.clear();
    head = tail = null;
}

查找元素

LinkedHashMap重寫了get()和getOrDefault()方法
默認情況下，LinkedHashMap是按插入順序維護鏈表。不過如果我們在初始化 LinkedHashMap時，指定 accessOrder參數(shù)為 true，即可讓它按訪問順序維護鏈表。訪問順序的原理是，當我們調用get/getOrDefault/replace等方法時，會將這些方法訪問的節(jié)點移動到鏈表的尾部。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)  // 回調afterNodeAccess(Node<K,V> e)
        afterNodeAccess(e);  // 將節(jié)點e移至雙向鏈表的尾部（保證迭代順序）
    return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);    // 作用同上
   return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;//原尾節(jié)點
    //如果accessOrder 是true ，且原尾節(jié)點不等于e
    if (accessOrder && (last = tail) != e) {
        //節(jié)點e強轉成雙向鏈表節(jié)點p
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //p現(xiàn)在是尾節(jié)點， 后置節(jié)點一定是null
        p.after = null;
        //如果p的前置節(jié)點是null，則p以前是頭結點，所以更新現(xiàn)在的頭結點是p的后置節(jié)點a
        if (b == null)
            head = a;
        else//否則更新p的前直接點b的后置節(jié)點為 a
            b.after = a;
        //如果p的后置節(jié)點不是null，則更新后置節(jié)點a的前置節(jié)點為b
        if (a != null)
            a.before = b;
        else//如果原本p的后置節(jié)點是null，則p就是尾節(jié)點。 此時 更新last的引用為 p的前置節(jié)點b
            last = b;
        if (last == null) //原本尾節(jié)點是null  則，鏈表中就一個節(jié)點
            head = p;
        else {//否則 更新 當前節(jié)點p的前置節(jié)點為 原尾節(jié)點last， last的后置節(jié)點是p
            p.before = last;
            last.after = p;
        }
        //尾節(jié)點的引用賦值成p
        tail = p;
        //修改modCount。
        ++modCount;
    }
}
// 因為LinkedHashMap中維護了一個雙向鏈表所以相對于HashMap中的雙重循環(huán)遍歷這個方法要優(yōu)化很多
LinkedHashMap
public boolean containsValue(Object value) {     
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {   // 通過雙向鏈表來遍歷
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}
HashMap
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

其他方法

LinkedHashMap還有一個比較神奇的存在。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根據(jù)條件判斷是否移除最近最少被訪問的節(jié)點
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
// 移除最近最少被訪問條件之一，通過覆蓋此方法可實現(xiàn)不同策略的緩存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

上面的方法一般不會被執(zhí)行，但是當我們基于 LinkedHashMap 實現(xiàn)緩存時，通過覆寫removeEldestEntry方法可以實現(xiàn)自定義策略的 LRU 緩存。比如我們可以根據(jù)節(jié)點數(shù)量判斷是否移除最近最少被訪問的節(jié)點，或者根據(jù)節(jié)點的存活時間判斷是否移除該節(jié)點等。

迭代器

public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        //返回LinkedEntrySet
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
    }
final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
    abstract class LinkedHashIterator {
        //下一個節(jié)點
        LinkedHashMap.Entry<K,V> next;
        //當前節(jié)點
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;
        LinkedHashIterator() {
            //初始化時，next 為 LinkedHashMap內部維護的雙向鏈表的扁頭
            next = head;
            //記錄當前modCount，以滿足fail-fast
            expectedModCount = modCount;
            //當前節(jié)點為null
            current = null;
        }
        //判斷是否還有next
        public final boolean hasNext() {
            //就是判斷next是否為null，默認next是head  表頭
            return next != null;
        }
        //nextNode() 就是迭代器里的next()方法 。
        //該方法的實現(xiàn)可以看出，迭代LinkedHashMap，就是從內部維護的雙鏈表的表頭開始循環(huán)輸出。
        final LinkedHashMap.Entry<K,V> nextNode() {
            //記錄要返回的e。
            LinkedHashMap.Entry<K,V> e = next;
            //判斷fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //如果要返回的節(jié)點是null，異常
            if (e == null)
                throw new NoSuchElementException();
            //更新當前節(jié)點為e
            current = e;
            //更新下一個節(jié)點是e的后置節(jié)點
            next = e.after;
            //返回e
            return e;
        }
        //刪除方法 最終還是調用了HashMap的removeNode方法
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

該方法的實現(xiàn)可以看出，迭代LinkedHashMap，就是從內部維護的雙鏈表的表頭開始循環(huán)輸出。而雙鏈表節(jié)點的順序在LinkedHashMap的增、刪、改、查時都會更新。以滿足按照插入順序輸出，還是訪問順序輸出。

總結

在日常開發(fā)中LinkedHashMap 的使用頻率沒有HashMap高，但它也個重要的實現(xiàn)。
在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三個映射類基于不同的數(shù)據(jù)結構，并實現(xiàn)了不同的功能。
HashMap 底層基于拉鏈式的散列結構，并在 JDK 1.8 中引入紅黑樹優(yōu)化過長鏈表的問題。基于這樣結構，HashMap 可提供高效的增刪改查操作。
LinkedHashMap 在其之上，通過維護一條雙向鏈表，實現(xiàn)了散列數(shù)據(jù)結構的有序遍歷。
TreeMap 底層基于紅黑樹實現(xiàn)，利用紅黑樹的性質，實現(xiàn)了鍵值對排序功能。具體實現(xiàn)我們下次分析。

以上就是Java LinkedHashMap 底層實現(xiàn)原理分析的詳細內容，更多關于Java LinkedHashMap 底層實現(xiàn)原理的資料請關注腳本之家其它相關文章！

相關文章

  • 淺談Springboot2.0防止XSS攻擊的幾種方式

    淺談Springboot2.0防止XSS攻擊的幾種方式

    本文主要介紹了Springboot2.0防止XSS攻擊的幾種方式，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2022-08-08
  • Java中List＜T＞和List＜?＞的區(qū)別詳解

    Java中List＜T＞和List＜?＞的區(qū)別詳解

    這篇文章主要介紹了Java中List＜T＞和List＜?＞的區(qū)別詳解。文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2020-12-12
  • Java?Calendar類使用之日期和時間處理指南

    Java?Calendar類使用之日期和時間處理指南

    這篇文章主要給大家介紹了關于Java?Calendar類使用之日期和時間處理指南的相關資料,Calendar類是Java中用于處理日期和時間的抽象類,它提供了一種獨立于特定日歷系統(tǒng)的方式來處理日期和時間,需要的朋友可以參考下
    2023-12-12
  • java圖形用戶界面實現(xiàn)菜單功能

    java圖形用戶界面實現(xiàn)菜單功能

    這篇文章主要為大家詳細介紹了java圖形用戶界面實現(xiàn)菜單功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2018-05-05
  • 手把手教你JAVA進制之間的轉換

    手把手教你JAVA進制之間的轉換

    這篇文章主要介紹了Java實現(xiàn)的進制轉換,結合完整實例形式分析了Java實現(xiàn)二進制、十六進制、字符串、數(shù)組等相關轉換操作技巧,需要的朋友可以參考下
    2021-08-08
  • Springboot整合RabbitMQ實現(xiàn)發(fā)送驗證碼的示例代碼

    Springboot整合RabbitMQ實現(xiàn)發(fā)送驗證碼的示例代碼

    這篇文章主要介紹了Springboot整合RabbitMQ實現(xiàn)發(fā)送驗證碼的功能,基于AMQP協(xié)議實現(xiàn)的消息隊列，它是一種應用程序之間的通信方法，消息隊列在分布式系統(tǒng)開 發(fā)中應用非常廣泛，需要的朋友可以參考下
    2022-02-02
  • Java設計模式之單例和原型

    Java設計模式之單例和原型

    這篇文章介紹了Java設計模式之單例和原型，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
    2022-09-09
  • Java Web開發(fā)之基于Session的購物商店實現(xiàn)方法

    Java Web開發(fā)之基于Session的購物商店實現(xiàn)方法

    這篇文章主要介紹了Java Web開發(fā)之基于Session的購物商店實現(xiàn)方法,涉及Java針對session的操作及數(shù)據(jù)庫操作技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-10-10
  • 關于spring中不同包中類名相同報錯問題的總結

    關于spring中不同包中類名相同報錯問題的總結

    這篇文章主要介紹了關于spring中不同包中類名相同報錯問題的總結，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2023-06-06
  • SpringBoot統(tǒng)一處理功能實現(xiàn)的全過程

    SpringBoot統(tǒng)一處理功能實現(xiàn)的全過程

    最近在做項目時需要對異常進行全局統(tǒng)一處理,主要是一些分類入庫以及記錄日志等,下面這篇文章主要給大家介紹了關于SpringBoot統(tǒng)一功能處理實現(xiàn)的相關資料,文中通過圖文以及實例代碼介紹的非常詳細,需要的朋友可以參考下
    2023-03-03

最新評論