可以理解为: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);
      }
  }