LinkedHashMap源码解析

数据结构

继承于HashMap结构，

 static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
}

• 按照插入顺序进行访问
• 实现了访问最少最先删除功能，其目的是把很久没有访问的key删除

常见属性

    /**
     * 链表头
     */
    transient LinkedHashMap.Entry<K,V> head;
    /**
     * 链表尾
     */
    transient LinkedHashMap.Entry<K,V> tail;
	/**
     * 控制两种访问模式的字段，默认false
     * true 按照访问顺序
     * false 按照插入顺序
     */
    final boolean accessOrder;

操作

按照添加顺序新增

LinkedHashMap继承了HashMap,重写了put方法中的newNode、newTreeNode、afterNodeAccess方法

  //新增节点，并追加到链表尾部
  Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
  }
  private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
  }
  

访问最少删除策略

public void testAccessOrder() {
  // 新建 LinkedHashMap
  LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(4,0.75f,true) {
    {
      put(10, 10);
      put(9, 9);
      put(20, 20);
      put(1, 1);
    }

    @Override
    // 覆写了删除策略的方法，我们设定当节点个数大于 3 时，就开始删除头节点
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
      return size() > 3;
    }
  };

  log.info("初始化：{}",JSON.toJSONString(map));
  Assert.assertNotNull(map.get(9));
  log.info("map.get(9)：{}",JSON.toJSONString(map));
  Assert.assertNotNull(map.get(20));
  log.info("map.get(20)：{}",JSON.toJSONString(map));

}

   public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        //如果设置了LRU策略
        if (accessOrder)
           //这个方法把当前key移动到队尾
            afterNodeAccess(e);
        return e.value;
    }

这个里实现了put的时候的删除操作
void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

总结

LinkedHashMap提供了按照插入顺序访问和删除最小访问元素策略，通过链表就实现了