LRU Cache

2016, May 10    

LRU Cache

@(算法)[算法, Linked List, Zenefits, Uber, Google]

这一题怎样用一句话描述？

手动实现LRU Cache算法（Least Recent Used），思路可以参照What is the best way to implement a LRU Cache，具体LRU Cache是什么请复习计算机体系结构。

用到什么算法？什么数据结构？

Cache算法。数组，HashMap

通过这题学到了什么？

What is the best way to implement a LRU Cache中的回答是使用双向链表加上HashMap，而我用的是数组。事实上殊途同归，我们都是要将最常用的放在最前面，最不常用的放在最后面，只是实现的方法不同而已。

相较而言，我更喜欢使用数组，因为数组的swap和取值都非常方便，思路如下（Java语言描述）：

新创建一个Cache，就会创建一个HashMap，其中存储了Key值，以及Key值对应的Value值在数组中的Index：

HashMap<Integer, Integer> hash = new HashMap<>();
// first Integer represents Key
// second Integer represent Index

同时，新建Cache时，还会创建一个对应其capacity大小的数组

Pair[] cache = new Pair[capacity]

你应该注意到，数组中存储的元素是一个Pair类型，因为每一个元素，我们不仅要用到value值，还需要用到key值：

private class Pair {
    int key;
    int val;
    Pair(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

有了这两个数据结构，我们就能实现自己的Cache算法了：

  1. get方法： 1.1. 查询HashMap中是否包含输入的Key值，找不到返回-1；找得到则进入1.2。 1.2. 通过输入的Key值找到该元素对应在数组中的Index，将该元素移动到数组首部，其他元素依次向后挪一格，最后返回该元素值对应的Value即可。
  2. set方法： 2.1. 查询HashMap中是否包含输入的Key值，如果找得到，则更新其Value值，并通过输入的Key值找到该元素对应在数组中的Index，将该元素移动到数组首部，其他元素依次向后挪一格；找不到则进入2.2。 2.2. 如果当前数组中元素的个数小于capacity，则往数组中增加一个元素，在HashMap中放入Key值对应的Index值，最后将该元素移动到数组首部，其他元素依次向后挪一格；如果元素的个数已经等于capacity，则进入2.3。 2.3. 将数组最后一个位置的元素的Key值对应的HashMap中的元素删除，然后将数组最后一个位置的元素的Key值和Value值都更新，将更新后的Key值以及元素位置的Index放进HashMap，最后将该元素移动到数组首部，其他元素依次向后挪一格。

这里的将该元素移动到数组首部，其他元素依次向后挪一格实现起来也很简单，就是将相邻的数组元素swap，然后更新元素Key值对应在HashMap中的Index（一个+1，一个-1）。

总结下来就是：HashMap是用来寻址的，而数组则充当了存储的角色。当计算机需要访问某个Value时，只要传入其对应的Key；Cache算法通过Key值查询HashMap，找到元素在数组中的Index；然后返回该Index下元素的Value值即可。

参考代码：

public class Solution {

    private int capacity;
    private HashMap<Integer, Integer> hash;
    private Pair[] cache;
    private int size;
    private class Pair {
        int key;
        int val;
        Pair(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // @param capacity, an integer
    public Solution(int capacity) {
        // write your code here
        this.capacity = capacity;
        hash = new HashMap<>();
        cache = new Pair[capacity];
        size = 0;
    }

    // @return an integer
    public int get(int key) {
        if (hash.containsKey(key)) {
            moveToFirst(cache, hash.get(key));
            return cache[hash.get(key)].val;
        } else {
            return -1;
        }
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        // write your code here
        if (hash.containsKey(key)) {
            cache[hash.get(key)].val = value;
            moveToFirst(cache, hash.get(key));
            return;
        }
        if (size < capacity) {
            cache[size] = new Pair(key, value);
            hash.put(key, size);
            moveToFirst(cache, size);
            size++;
        } else {
            hash.remove(cache[capacity - 1].key);
            cache[capacity - 1].key = key;
            cache[capacity - 1].val = value;
            hash.put(key, capacity - 1);
            moveToFirst(cache, capacity - 1);
        }
    }

    private void moveToFirst(Pair[] array, int index) {
        for (int i = index; i > 0 ; i--) {
            swap(array, i - 1, i);
        }
    }

    private void swap(Pair[] array, int i, int j) { // i must < j
        hash.put(array[i].key, hash.get(array[i].key) + 1);
        hash.put(array[j].key, hash.get(array[j].key) - 1);
        Pair pair = new Pair(array[j].key, array[j].val);
        array[j].key = array[i].key;
        array[j].val = array[i].val;
        array[i].key = pair.key;
        array[i].val = pair.val;
    }
}

可能(已经)遇到的BUG有？

set时，没有考虑到HashMap中已经存在Key的情况。

Twitter Facebook Google+