最近使用的会移至尾部,LinkedHashMap输出时其元素是有顺序的,HashMap是无序的,因为hashMap没有双向链表,只是根据hashcode的值决定存储在数组中哪个位置;

LinkedHashMap可以作为LRU的一个实现,自带核心方法 removeEldestEntry(),默认返回false。

自己可以继承这个类,重写 removeEldestEntry方法,当put时,会调用。

一般场景,当map.size()>maxCapacity 时,返回true,意味着在put时会移除掉最老的那个。

 

JDK8

主结构为Node<K,V>数组。数组下标为(size()-1)&hash。注意TreeNode为Node子类。所以数组中实际存储的可能为Node,也可能为TreeNode红黑树结构。

Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
}

当冲突小于阈值时,数组中存储Node链表。

当大于阈值时,数组中存储的是TreeNode。存储时有将Node转换为TreeNode的操作过程。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

网上有人说是将自动HashMap转换为TreeMap是严重错误,实际是Node转为TreeNode。

Entry<K,V> extends HashMap.Node<K,V>;

TreeNode 继承 LinkedHashMap.Entry 继承 Node

 

resize() to double currentCapacity

default init capacity 16

default loadFactor 0.75

threshHold=loadFactor*capacity