LinkedHashMap

概述

LinkedHashSet使用适配器模式包装了LinkedHashSet

一个有序的散列表，允许key为null也允许value为空，从名字上可以看出使用链表维护了有序性

在元素存储时，在原来的HashMap的数组+链表的基础上，为每个元素添加了pre和next指针，构成了一个双向链表

注意：内部没有使用红黑树

同样的内部有多个参数

• head：虚拟头结点

• tail：虚拟尾节点

• 初始容量：16

• 负载因子：扩容临界值

插入

• 插入到对应的bucket的单链表中

• 插入到双向链表的尾部

删除

• 删除对应bucket中的元素

• 双向链表中断链

缓存用法

LinkedHashMap有一个子类方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest)，该方法的作用是告诉Map是否要删除“最老”的Entry，所谓最老就是当前Map中最早插入的Entry，如果该方法返回true，最老的那个元素就会被删除。

重写这个子方法可以实现一个LRU缓存

LRU缓存

使用LinkedHashMap实现一个指定容量的LRU缓存

public class LRUCache extends LinkedHashMap<Integer,Integer> {
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

概述：只需要继承LinkedHashMap类，使用构造方法指定容量、负载因子、顺序规则（true访问顺序，false插入顺序），然后重写removeEldestEntry方法即可，在超过指定大小时返回true

如何手写一个LinkedHashMap？

手写LinkedHashMap一般指手动实现一个LRU缓存

其中包含四个部分

• 自定义Node节点：需要使用双向链表

• 自定义一个内部map：需要使用散列表

• 初始化capacity、size、head、tail，其中头尾是虚拟节点

• 实现四个方法

  • moveToHead：移动到头部

  • addToHead：添加到头部

  • removeEldestNode：删除尾巴节点

  • removeNode：删除节点---断链

插入节点

创建Node，添加进map中，添加到链表头部，超容量就删除尾部节点，删除的时候调用removeNode断链，然后在map中也删除

查询节点

查询map中你的Node，移动到头部（先断链，再添加）

实现代码

public class MyLRUCache {

    static class Node {
        int key;
        int value;
        Node pre;
        Node next;
        public Node(){}
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.pre = null;
            this.next = null;
        }
    }

    private Map<Integer, Node> cache = new HashMap<>();
    private int size;
    private int capacity;
    private Node head, tail;

    public MyLRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    private void moveToHead(Node node){
        //移动到头部
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(Node node){
        //添加到头部
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    private void removeEldestNode(){
        //删除尾巴节点
        Node temp = tail.pre;
        removeNode(temp);
        this.cache.remove(temp.key);
    }

    private void removeNode(Node node) {
        //删除节点
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }


    public int get(int key) {
        Node node = this.cache.get(key);
        if(node == null) return -1;
        //移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = this.cache.get(key);
        if(node == null) {
            //不存在就创建,添加进哈希表
            node = new Node(key, value);
            cache.put(key, node);
            //添加进头部
            addToHead(node);
            size++;
            if(size > capacity){
                //删除尾巴节点
                removeEldestNode();
                size--;
            }
        }else {
            node.value = value;
            moveToHead(node);
        }
    }
}

总结

使用HashMap作为存储容器，容器中不是存储元素自身，而是存储Node节点，并且Node节点互相连接形成了一个双向链表