Java集合之LinkedHashMap

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

/**
 * The head of the doubly linked list.
 * 双向链表的头节点
 */
private transient Entry<K,V> header;
/**
 * The iteration ordering method for this linked hash map: true
 * for access-order, false for insertion-order.
 * true表示最近最少使用次序，false表示插入顺序
 */
private final boolean accessOrder;

// 构造方法1，构造一个指定初始容量和负载因子的、按照插入顺序的LinkedList
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// 构造方法2，构造一个指定初始容量的LinkedHashMap，取得键值对的顺序是插入顺序
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// 构造方法3，用默认的初始化容量和负载因子建立一个LinkedHashMap，取得键值对的顺序是插入顺序
public LinkedHashMap() {
    super();
    accessOrder = false;
}
// 构造方法4，经过传入的map建立一个LinkedHashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}
// 构造方法5，根据指定容量、装载因子和键值对保持顺序建立一个LinkedHashMap
public LinkedHashMap(int initialCapacity,
             float loadFactor,
                         boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }
    ...
}

1 public static void main(String[] args)
2 {
3     LinkedHashMap<String, String> linkedHashMap =
4             new LinkedHashMap<String, String>();
5     linkedHashMap.put("111", "111");
6     linkedHashMap.put("222", "222");
7 }

1 public LinkedHashMap() {
2     super();
3     accessOrder = false;
4 }

1 public HashMap() {
2     this.loadFactor = DEFAULT_LOAD_FACTOR;
3     threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
4     table = new Entry[DEFAULT_INITIAL_CAPACITY];
5     init();
6 }

1 void init() {
2      header = new Entry<K,V>(-1, null, null, null);
3      header.before = header.after = header;
4 }

 1 //这个方法应该挺熟悉的，若是看了HashMap的解析的话
 2 public V put(K key, V value) {
 3     //key为null的状况
 4     if (key == null)
 5         return putForNullKey(value);
 6     //经过key算hash，进而算出在数组中的位置，也就是在第几个桶中
 7     int hash = hash(key.hashCode());
 8     int i = indexFor(hash, table.length);
 9     //查看桶中是否有相同的key值，若是有就直接用新值替换旧值，而不用再建立新的entry了
10     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
11         Object k;
12         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
13             V oldValue = e.value;
14             e.value = value;
15             e.recordAccess(this);
16             return oldValue;
17         }
18     }
19 
20     modCount++;    
21     //上面度是熟悉的东西，最重要的地方来了，就是这个方法，LinkedHashMap执行到这里，addEntry()方法不会执行HashMap中的方法，
22     //而是执行本身类中的addEntry方法，
23     addEntry(hash, key, value, i);
24     return null;
25 }

 1 void addEntry(int hash, K key, V value, int bucketIndex) {
 2     //调用create方法，将新元素以双向链表的的形式加入到映射中
 3     createEntry(hash, key, value, bucketIndex);
 4 
 5     // Remove eldest entry if instructed, else grow capacity if appropriate
 6     // 删除最近最少使用元素的策略定义  
 7     Entry<K,V> eldest = header.after;
 8     if (removeEldestEntry(eldest)) {
 9         removeEntryForKey(eldest.key);
10     } else {
11         if (size >= threshold)
12             resize(2 * table.length);
13     }
14 }

1 void createEntry(int hash, K key, V value, int bucketIndex) {
2     HashMap.Entry<K,V> old = table[bucketIndex];
3     Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
4     table[bucketIndex] = e;
5     //将该节点插入到链表尾部
6     e.addBefore(header);
7     size++;
8 }

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

/**
 * 经过key获取value，与HashMap的区别是：当LinkedHashMap按访问顺序排序的时候，会将访问的当前节点移到链表尾部(头结点的前一个节点)
 */
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;
}

/**
 * 在HashMap的put和get方法中，会调用该方法，在HashMap中该方法为空
 * 在LinkedHashMap中，当按访问顺序排序时，该方法会将当前节点插入到链表尾部(头结点的前一个节点)，不然不作任何事
 */
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //当LinkedHashMap按访问排序时
    if (lm.accessOrder) {
        lm.modCount++;
        //移除当前节点
        remove();
        //将当前节点插入到头结点前面
        addBefore(lm.header);
    }
}

/**
 * 移除节点，并修改先后引用
 */
private void remove() {
    before.after = after;
    after.before = before;
}

private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }

public class LRUCache extends LinkedHashMap
{
    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        return size() > maxElements;
    }

    private static final long serialVersionUID = 1L;
    protected int maxElements;
}

public LinkedHashMap(int initialCapacity,
         float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

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;
}

 1 public V put(K key, V value) {
 2     if (key == null)
 3         return putForNullKey(value);
 4     int hash = hash(key.hashCode());
 5     int i = indexFor(hash, table.length);
 6     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
 7         Object k;
 8         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
 9             V oldValue = e.value;
10             e.value = value;
11             e.recordAccess(this);
12             return oldValue;
13         }
14     }
15 
16     modCount++;
17     addEntry(hash, key, value, i);
18     return null;
19 }

void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}

private void remove() {
    before.after = after;
    after.before = before;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

public static void main(String[] args)
{
    LinkedHashMap<String, String> linkedHashMap =
            new LinkedHashMap<String, String>(16, 0.75f, true);
    linkedHashMap.put("111", "111");
    linkedHashMap.put("222", "222");
    linkedHashMap.put("333", "333");
    linkedHashMap.put("444", "444");
    loopLinkedHashMap(linkedHashMap);
    linkedHashMap.get("111");
    loopLinkedHashMap(linkedHashMap);
    linkedHashMap.put("222", "2222");
    loopLinkedHashMap(linkedHashMap);
}
    
public static void loopLinkedHashMap(LinkedHashMap<String, String> linkedHashMap)
{
    Set<Map.Entry<String, String>> set = inkedHashMap.entrySet();
    Iterator<Map.Entry<String, String>> iterator = set.iterator();
    
    while (iterator.hasNext())
    {
        System.out.print(iterator.next() + "\t");
    }
    System.out.println();
}

111=111    222=222    333=333    444=444    
222=222    333=333    444=444    111=111    
333=333    444=444    111=111    222=2222