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 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 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 before, after;

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

public static void main(String[] args)
{
    LinkedHashMap<String, String> linkedHashMap =
            new LinkedHashMap<String, String>();
    linkedHashMap.put("111", "111");
    linkedHashMap.put("222", "222");
}

public LinkedHashMap() {
     super();
     accessOrder = false;
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
 }

void init() {
     header = new Entry(-1, null, null, null);
     header.before = header.after = header;
}

//这个方法应该挺熟悉的，如果看了HashMap的解析的话
public V put(K key, V value) {
    //key为null的情况
    if (key == null)
        return putForNullKey(value);
    //通过key算hash，进而算出在数组中的位置，也就是在第几个桶中
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //查看桶中是否有相同的key值，如果有就直接用新值替换旧值，而不用再创建新的entry了
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    //上面度是熟悉的东西，最重要的地方来了，就是这个方法，LinkedHashMap执行到这里，addEntry()方法不会执行HashMap中的方法，
    //而是执行自己类中的addEntry方法，
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    //调用create方法，将新元素以双向链表的的形式加入到映射中
    createEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed, else grow capacity if appropriate
    // 删除最近最少使用元素的策略定义
    Entry 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 old = table[bucketIndex];
    Entry e = new Entry(hash, key, value, old);
    table[bucketIndex] = e;
    //将该节点插入到链表尾部
    e.addBefore(header);
    size++;
}

private void addBefore(Entry existingEntry) {
    after = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

/**
 * 通过key获取value，与HashMap的区别是：当LinkedHashMap按访问顺序排序的时候，会将访问的当前节点移到链表尾部(头结点的前一个节点)
 */
public V get(Object key) {
    // 调用父类HashMap的getEntry()方法，取得要查找的元素。 
    Entry e = (Entry)getEntry(key);
    if (e == null)
        return null;
    // 记录访问顺序。
    e.recordAccess(this);
    return e.value;
}

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

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

private void addBefore(Entry 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 e = (Entry)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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

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

private void addBefore(Entry 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)
{
    SetString, String>> set = inkedHashMap.entrySet();
    IteratorString, 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