使用LinkedHashMap实现LRU算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class LRUTest
{
    int capacity;
    LinkedHashMap<Integer, Integer> cache;

    LRUTest(int capacity)
    {
        cache = new LinkedHashMap<>();
        this.capacity = capacity;
    }

    //访问元素
    public int get(int key)
    {
        if(!cache.containsKey(key))
        {
            return -1;
        }

        //存在，先从链表头部删除删除，在插入到链表尾部
        int val = cache.get(key);
        cache.remove(key);
        cache.put(key, val);

        return val;
    }

    //添加元素
    public void put(int key, int val)
    {
        if(cache.containsKey(key))
        {
            cache.remove(key);
        }

        //如果链表已经满了，则删除头部节点
        if(cache.size() == capacity)
        {
            Set<Integer> keySet = cache.keySet();
            Iterator<Integer> iterator = keySet.iterator();
            cache.remove(iterator.next());
        }

        cache.put(key, val);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LRUTest extends LinkedHashMap<String, String>
{
    private int capacity;

    /**
     * 当LinkedHashMap的accessOrder参数为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
     */
    public LRUTest(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    /**
     * LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest)
    {
        return size() > capacity;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    public static void main(String[] args)
    {
        Map<String, String> linkedHashMap = new LRUTest(6);

        linkedHashMap.put("1", "1");
        linkedHashMap.put("2", "2");
        linkedHashMap.put("3", "3");
        linkedHashMap.put("4", "4");
        linkedHashMap.put("5", "5");
        linkedHashMap.put("6", "6");
        linkedHashMap.put("7", "7");
        linkedHashMap.put("8", "8");
        linkedHashMap.put("9", "9");

        System.out.println("size="+linkedHashMap.size());
        System.out.println(linkedHashMap.get("8"));

        linkedHashMap.forEach((k,v) ->{
            System.out.print(k + ":"+ v +"  ");
        });

        System.out.println();
        System.out.println("size="+linkedHashMap.size());
    }

1
2
3
4
size=6
8
4:4  5:5  6:6  7:7  9:9  8:8  
size=6