`

Java LinkedHashMap的实现原理

阅读更多
1. LinkedHashMap概述:
   HashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
   LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。
   注意,此实现不是同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步。

2. LinkedHashMap的实现:
   对于LinkedHashMap而言,它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似,它通过重写父类相关的方法,来实现自己的链接列表特性。下面我们来分析LinkedHashMap的源代码:
  1) Entry元素:
   LinkedHashMap采用的hash算法和HashMap相同,但是它重新定义了数组中保存的元素Entry,该Entry除了保存当前对象的引用外,还保存了其上一个元素before和下一个元素after的引用,从而在哈希表的基础上又构成了双向链接列表。看源代码:
/** 
 * 双向链表的表头元素。 
 */  
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;  
    ……  
}  

2) 初始化:
   通过源代码可以看出,在LinkedHashMap的构造方法中,实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如:
public LinkedHashMap(int initialCapacity, float loadFactor) {  
    super(initialCapacity, loadFactor);  
    accessOrder = false;  
}  

HashMap中的相关构造方法:
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();  
}  

我们已经知道LinkedHashMap的Entry元素继承HashMap的Entry,提供了双向链表的功能。在上述HashMap的构造器
中,最后会调用init()方法,进行相关的初始化,这个方法在HashMap的实现中并无意义,只是提供给子类实现相关的初始化调用。
   LinkedHashMap重写了init()方法,在调用父类的构造方法完成构造后,进一步实现了对其元素Entry的初始化操作。
void init() {  
    header = new Entry<K,V>(-1, null, null, null);  
    header.before = header.after = header;  
}  

3) 存储:
   LinkedHashMap并未重写父类HashMap的put方法,而是重写了父类HashMap的put方法调用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的双向链接列表的实现。
void addEntry(int hash, K key, V value, int bucketIndex) {  
    // 调用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;  
    // 调用元素的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方法,实际在调用父类getEntry()方法取得查找的元素后,再判断当排序模式accessOrder为true时,记录访问顺序,将最新访问的元素添加到双向链表的表头,并从原来的位置删除。由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失。
public V get(Object key) {  
    // 调用父类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);  
    }  
}  

5) 排序模式:
   LinkedHashMap定义了排序模式accessOrder,该属性为boolean型变量,对于访问顺序,为true;对于插入顺序,则为false。
private final boolean accessOrder;  

一般情况下,不必指定排序模式,其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法,如:
public LinkedHashMap(int initialCapacity, float loadFactor) {  
    super(initialCapacity, loadFactor);  
    accessOrder = false;  
}  

这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap,并打算按从近期访问最少到近期访问最多的顺序(即访问顺序)来保存元素,那么请使用下面的构造方法构造LinkedHashMap:
public LinkedHashMap(int initialCapacity,  
         float loadFactor,  
                     boolean accessOrder) {  
    super(initialCapacity, loadFactor);  
    this.accessOrder = accessOrder;  
}  

该哈希映射的迭代顺序就是最后访问其条目的顺序,这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法,在将新条目插入到映射后,put和 putAll将调用此方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序,默认返回false,这样,此映射的行为将类似于正常映射,即永远不能移除最旧的元素。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {  
    return false;  
}  

此方法通常不以任何方式修改映射,相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存,则非常方便,它允许映射通过删除旧条目来减少内存损耗。
   例如:重写此方法,维持此映射只保存100个条目的稳定状态,在每次添加新条目时删除最旧的条目。
private static final int MAX_ENTRIES = 100;  
protected boolean removeEldestEntry(Map.Entry eldest) {  
    return size() > MAX_ENTRIES;  
}  


参考:http://zhangshixi.iteye.com/blog/673789
分享到:
评论

相关推荐

    Java LinkedHashMap工作原理及实现

     在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序:  LinkedHashMap&lt;String&gt; lmap = new LinkedHashMap();  lmap.put(语文, 1)...

    java软件技术文档-深入java8的集合4:LinkedHashMap的实现原理.pdf

    如果 `accessOrder` 属性为 true,LinkedHashMap 将移动该节点到链表的末尾,从而实现按访问顺序排序。 2. **afterNodeInsertion(boolean evict)**: 在插入新节点后调用。在这个方法中,除了添加新节点到哈希表和...

    Java集合系列之LinkedHashMap源码分析

    Linked HashMap的实现原理主要有两个方面:一是链表结构,二是哈希表结构。链表结构是指LinkedHashMap内部采用双向链表来存储元素,哈希表结构是指LinkedHashMap继承自HashMap,使用哈希表来存储元素。...

    Java中LinkedHashMap源码解析

    了解LinkedHashMap的实现原理和使用方法,可以帮助开发者更好地应用Java中的数据结构。 知识点: 1. LinkedHashMap的实现原理是基于哈希表和链表的结合。 2. LinkedHashMap维护着一个运行于所有条目的双重链表结构...

    java集合类原理面试题

    Java集合类是Java编程中非常重要的组成部分,它们提供了一种组织和管理数据的方式。Java集合框架主要由两个...综上所述,Java集合类及其原理是面试中常见的知识点,理解并掌握它们有助于提升编程能力,解决实际问题。

    详解Java中LinkedHashMap

    LinkedHashMap的基本实现思想是多态,可以说,理解多态再去理解LinkedHashMap原理会事半功倍。 在LinkedHashMap中,每个元素是一个Entry对象,Entry对象中包含了Key、Value、Hash值、之前的Entry对象和之后的Entry...

    Java实现LRU缓存机制:深入解析与高效编码实践

    在Java中实现LRU缓存,可以通过使用LinkedHashMap来简化实现,也可以手动实现以获得更好的控制。在多线程环境中,还需要考虑缓存的线程安全问题。通过合理的设计和优化,我们可以有效地提高程序的性能和响应速度。

    LinkedHashmap的使用

    HashMap是Java集合框架中的一员,它是基于哈希表实现的,提供了快速的插入、删除和查找操作,平均时间复杂度为O(1)。然而,HashMap不保证元素的顺序,迭代时元素的顺序可能与插入顺序不同,且不保证在多次运行时保持...

    深入解析java HashMap实现原理

    综上所述,理解HashMap的实现原理对于优化Java程序性能至关重要,尤其是在处理大量数据或并发场景时。在实际应用中,应根据具体需求选择合适的数据结构,例如,如果需要线程安全,可以选择ConcurrentHashMap;如果对...

    深入Java集合学习系列

    文件"深入Java集合学习系列:LinkedHashMap的实现原理 - 莫等闲 - ITeye技术网站.mht"将揭示LinkedHashMap是如何通过双向链表实现这一功能的。 HashSet是基于HashMap实现的,不包含重复元素且不保证元素的顺序。...

    Java HashMap实现原理分析(一)

    总的来说,Java HashMap的实现原理主要包括以下几个关键点: 1. 基于哈希表的数据结构,使用数组+链表的方式存储键值对。 2. 使用键的哈希值计算数组索引,通过异或和位移操作优化哈希分布。 3. 链地址法解决哈希...

    【Java面试+Java学习指南】 一份涵盖大部分Java程序员所需要掌握的核心知识

    Java集合详解1:一文读懂ArrayList,Vector与Stack使用方法和实现原理 Java集合详解2:Queue和LinkedList Java集合详解3:Iterator,fail-fast机制与比较器 Java集合详解4:HashMap和HashTable Java集合详解5:深入...

    郑州大学java实验报告

    Java中的哈希表可以是HashMap、LinkedHashMap等。 三、Java中的容器类 * ArrayList:ArrayList是Java中的一个容器类,用于存储多个对象。ArrayList可以动态增长和缩小。 * LinkedList:LinkedList是Java中的一个...

    java HashMap,TreeMap与LinkedHashMap的详解

    在Java编程语言中,`HashMap`、`TreeMap`和`LinkedHashMap`都是`java.util.Map`接口的实现,它们提供了不同的数据存储和访问策略。本文将深入探讨这三种数据结构的特点、工作原理以及适用场景。 1. **HashMap** `...

Global site tag (gtag.js) - Google Analytics