自己动手写写：LinkedHashMap源码浅析

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

 

四. LinkedHashMap

 

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

 

1. 类结构

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

 

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

 

2. 几个重要的成员变量

/**                                                                     
 * 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的内部类定义，代码片段如下：

//继承了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. 几个重要的构造函数

   /**
     * 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. 几个重要的方法

   /**
     * 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方法。代码中表达的意思也很明确了，这是双向链表的初始化状态。

 

 

 

/**                                                                        
 * 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方法

 

/**                                                                      
 * 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时，不做任何事情，就按照插入顺序迭代出来！

 

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

评论

1 楼 whg333 2013-04-25  

最后的解释recordAccess方法中说道：
addBefore方法再将当前元素插入到链表的头部去

代码中这里是addBefore(lm.header);，其实是插入到链表的尾部去吧。
正如代码注释所说的：
If the enclosing Map is access-ordered, it moves the entry to the end of the list; otherwise, it does nothing.