LinkedHashMap、HashMap、HashTabel

可以理解为:LinkedHashMap = HashMap + LinkedList

HashMap：

• jdk1.7是通过数组+链表实现，jdk1.8是通过数组+链表+红黑树实现
• 遇到冲突时，HashMap 是采用的链地址法来解决

HashTable

与HashMap几乎功能一样，区别在于

• 线程安全性不同
  • Hashtable线程安全
  • HashMap线程不安全
• kv是否为null不同
  • HashMap中，null可以作为键，这样的键只有一个。value可以多个为null
  • Hashtable中，key和value都不允许出现null值

LinkedHashMap:

• HashMap+双向链表实现
• 调用无参的 HashMap 构造函数，具有默认初始容量（16）和加载因子（0.75）。并且设定了 accessOrder = false，表示默认按照插入顺序进行遍历。
• 有参构造，若是将第三个参数accessOrder = true，表示按照访问顺序进行遍历，即根据访问更新位置

  public LRUCache(int capacity) {
        super(capacity, 0.75F, true);//第二个参数为加载因子默认0.75
        this.capacity = capacity;
    }

• 新添加的元素放置到链表的尾端
• get操作之后，accessOrder = true的话就将此节点更新为链表尾端。
• 移除最老的首节点，boolean removeEldestEntry()默认为false，LRU算法就是重写此方法变成return size()>capacity,作为什么时候移除最老元素的条件。

  void afterNodeInsertion(boolean evict) { // 是否移除最老的节点
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }