首页 > 安全资讯 >

LinkedHashMap源码浅析

11-08-11

此系列文章中,上一篇是关于HashMap的源码剖析,这篇文章将向大家剖析一下LinkedHashMap的源码!四. LinkedHashMap我们知道从API的描述中可以看出HashMap与LinkedHashMap最大的不同在于,后者维护者一个运行于所...

 

此系列文章中,上一篇是关于HashMap的源码剖析,这篇文章将向大家剖析一下LinkedHashMap的源码!

 

四. LinkedHashMap

 

我们知道从API的描述中可以看出HashMap与LinkedHashMap最大的不同在于,后者维护者一个运行于所有条目的双向链表。有了这个双向链表,就可以在迭代的时候按照插入的顺序迭代出元素(当然也可以通过LRU算法迭代元素,下面会讲到)。

 

1. 类结构

Java代码 

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

 

我们可以看出LinkedHashMap继承了HashMap!

 

2. 几个重要的成员变量

Java代码 

/**                                                                     

 * The head of the doubly linked list.                                   

 */                                                                      

private transient Entry<K, V> header;                                    

                                                                         

/**                                                                      

 * The iteration ordering method for this linked hash map: <tt>true</tt>

 * for access-order, <tt>false</tt> for insertion-order.                

 *                                                                       

 * @serial                                                              

 */                                                                      

private final boolean accessOrder;                                        

 

 对于父类HashMap中的成员变量这里就不讲了,可参考http://boy00fly.iteye.com/blog/1139845

 其中Entry类是LinkedHashMap的内部类定义,代码片段如下:

Java代码 

//继承了HashMap.Entry                                        

private static class Entry<K, V> extends HashMap.Entry<K, V> 

//新增的两个成员变量                                          

Entry<K, V> before, after;                                   

 

 可以看得出来新增的这两个变量就是双向链表实现的关键!!分别指向当前Entry的前一个、后一个Entry。

 

header就是指向双向链表的头部!

accessOrder:true则按照LRU算法迭代整个LinkedHashMap,false则按照元素的插入顺序迭代!

 

3. 几个重要的构造函数

Java代码 

/**

  * Constructs an empty <tt>LinkedHashMap</tt> instance with the

  * specified initial capacity, load factor and ordering mode.

  *

  * @param  initialCapacity the initial capacity

  * @param  loadFactor      the load factor

  * @param  accessOrder     the ordering mode - <tt>true</tt> for

  *         access-order, <tt>false</tt> for insertion-order

  * @throws IllegalArgumentException if the initial capacity is negative

  *         or the load factor is nonpositive

  */  

 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 

 { 

     super(initialCapacity, loadFactor); 

     this.accessOrder = accessOrder; 

 } 

    是不是很简单,也可参考http://boy00fly.iteye.com/blog/1139845这篇文章的构造函数分析。其中accessOrder就是我们上面所讲的控制迭代顺序的开关,只有此构造函数有这个参数,其他的构造函数默认就是false。

 

4. 几个重要的方法

Java代码 

/**

  * Called by superclass constructors and pseudoconstructors (clone,

  * readObject) before any entries are inserted into the map.  Initializes

  * the chain.

  */ 

 void init() 

 { 

     header = new Entry<K, V>(-1, null, null, null); 

     header.before = header.after = header; 

 } 

 此方法是在父类构造函数初始化的时候调用的,LinkedHashMap重写了init方法。代码中表达的意思也很明确了,这是双向链表的初始化状态。

 

 

 

Java代码 

/**                                                                         

 * 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++;                                                          

}                                                                    

 

/**                                                                   

 * Inserts this entry before the specified existing entry in the list.

 */                                                                    

private void addBefore(Entry<K, V> existingEntry)                      

{                                                                      

    after = existingEntry;                                             

    before = existingEntry.before;                                     

    before.after = this;                                               

    after.before = this;                                                

}                                                                      

 

 addEntry方法是父类HashMap的一个方法,被put相关的方法所调用即在新增元素的时候调用。

 我们通过形象的图来看一个基本的流程:

(从初始化到添加了3个元素过程中,各个元素before、after引用变化,画的有点丑,呵呵,不过意思能够表达清楚,代码的内容就不再累述了,大体和HashMap类似!)

再介绍一个get方法

 

Java代码 

/**                                                                      

 * Returns the value to which the specified key is mapped,                

 * or {@code null} if this map contains no mapping for the key.          

 *                                                                       

 * <p>More formally, if this map contains a mapping from a key           

 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :

 * key.equals(k))}, then this method returns {@code v}; otherwise        

 * it returns {@code null}.  (There can be at most one such mapping.)    

 *                                                                        

 * <p>A return value of {@code null} does not <i>necessarily</i>         

 * indicate that the map contains no mapping for the key; it's also      

 * possible that the map explicitly maps the key to {@code null}.        

 * The {@link #containsKey containsKey} operation may be used to         

 * distinguish these two cases.                                          

 */                                                                       

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;                                                       

}                        

 

/**                                                                   

  * This method is invoked by the superclass whenever the value       

  * of a pre-existing entry is read by Map.get or modified by Map.set.

  * If the enclosing Map is access-ordered, it moves the entry        

  * to the end of the list; otherwise, it does nothing.               

  */                                                                   

 void recordAccess(HashMap<K, V> m)                                     

 {                                                                     

     LinkedHashMap<K, V> lm = (LinkedHashMap<K, V>)m;                  

     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;                  

}                                                                                                   

 

 这里我们来看一下recordAccess方法!

上面我们不是讲过accessOrder这个参数值控制着LinkedHashMap的迭代顺序嘛,这里我们来看一下。

 当accessOrder为true时,remove方法就是将当前元素从双向链表中移除,

 addBefore方法再将当前元素插入到链表的头部去,这样最近读到的元素,在迭代的时候是优先被迭代出来的!

这就是所谓的LRU算法(Least Recently Used):最近最少使用算法。

当accessOrder为false时,不做任何事情,就按照插入顺序迭代出来!

 

还有些其他的方法这里也不再累述了,重点的都在上面阐述了!

相关文章
最新文章
热点推荐