Java-Map：LinkedHashMap

1.为什么用LinkedHashMap

HashMap 的输出顺序与输入顺序不一致
LinkedHashMap 的输出顺序是有序的

2.LinkedHashMap的底层

LinkedHashMap继承了HashMap，实现了Map接口
LinkedHashMap可以认为是HashMap+LinkedList，
也就是说,它使用HashMap操作数据结构，也用LinkedList维护插入元素的先后顺序。

LinkedHashMap和HashMap的区别在于他们的基本数据机构Entry节点上，它的Entry内部类继承了HashMap的Node类，并且多了两个Entry类型的before，after字段。相当于有了链表的功能。

    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);}}

3.LinkedHashMap的accessOrder字段

accessOrder = false，插入顺序，put元素的时候会put到链表的尾部
accessOrder = true，访问顺讯，put元素或者访问元素的时候会把当前元素放到链表的尾部，
代表最近访问的元素在尾部，可以用来实现LRU算法。

4. 底层实现

#1 那么LinkedHashMap是如何实现LinkedList的功能的

1. 首先LinkedHashMap 中有两个字段head，tail字段指向链表的头尾节点，
2. LinkedHashMap没有重写HashMap的put方法，
   而是重写了HashMap中的newNode（）方法，重写后的方法会将新创建的节点插入LinkedList的尾部，

#2 那么LinkedHashMap是如何实现LRU

1. LinkedHashMap有一个字段accessOrder
   accessOrder = false：LinkedList的节点顺序是插入顺序
   accessOrder = true：LinkedList的节点顺序是访问顺序
2. HashMap中有三个空方法
   void afterNodeAccess(Node<K,V> p) { }
   void afterNodeInsertion(boolean evict) { }
   void afterNodeRemoval(Node<K,V> p) { }
3. LinkedHashMap重写了这三个方法
   1）void afterNodeAccess(Node<K,V> p) ：如果accessOrder = true，会将访问的节点移动到LinkedList的尾部。
   会在get（），replace（）方法中调用
   2）void afterNodeInsertion(boolean evict)：该方法的作用是是否删除LinedList的头部节点，如果accessOrder = true，也就是删除最近最少访问的。该方法受removeEldestEntry方法返回结果的影响。
   通过重写removeEldestEntry(Map.Entry<K, V> entry)方法来实现什么情况下删除LinkedList的头节点
   会在put（）方法中调用
   3）void afterNodeRemoval(Node<K,V> p) ：该方法的作用是在调用remove(Object key)方法时，调整LinedList的结构。

5. LRU的实现

方法1：使用LinkedHashMap

public class LRU_LinkedHashMap<K,V> extends LinkedHashMap<K, V> implements Map<K, V>{
    private static final long serialVersionUID = 1L;private int cap;public LRU_LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder, int cap) {
    super(initialCapacity, loadFactor, accessOrder);this.cap = cap;}public boolean removeEldestEntry(Map.Entry<K, V> entry) {
    if(size() > cap)return true;return false;}public V get(Object key) {
    return super.get(key);}public V put(K key, V val) {
    return super.put(key, val);}public void printLru(LRU_LinkedHashMap<K, V> lru_LinkedHashMap) {
    for(Entry<K, V> entry : lru_LinkedHashMap.entrySet())System.out.println(entry.getKey() + " " + entry.getValue());}public static void main(String[] args) {
    // TODO Auto-generated method stubLRU_LinkedHashMap<Character, Integer> lru = new LRU_LinkedHashMap<>(16, 0.75f, true, 5);String s = "abcdefg";int i = 0;for(Character c : s.toCharArray())lru.put(c, i++);lru.printLru(lru);lru.get('c');lru.printLru(lru);		}}

方法2：自己写，LinkedList + HashMap;

5. LFU的实现

方法：HashMap + TreeSet，
自定义节点Node，然后思路同LRU

class Node implements Comparable<Node>{
    int cnt;  //频率int time; //时间int key;int val;public Node(int cnt, int time, int key, int val) {
    this.cnt = cnt;this.time = time;this.key = key;this.val = val;}public boolean equals(Object obj) {
    if(this == obj)return true;if(obj instanceof Node) {
    Node node = (Node)obj;return this.cnt == node.cnt && this.time == node.time;}return false;}@Overridepublic int compareTo(Node o) {
    // TODO Auto-generated method stubreturn this.cnt == o.cnt ? this.cnt - o.cnt : this.time - o.time;}}