JAVA实现缓存（LRU、FIFO、weakhashMap）

发表于

前阵子在公司给某客户做的邮箱系统登录页背景图的定制化开发。无意中想到一个问题：若系统支持给不同集团做定制化的登录页背景图开发，那就是图片不能直接存项目的资源文件了。只能通过文件形式或者图片Base64存数据库。那么问题来了，若是每一次浏览系统登录页时，都需要读一次文件目录或数据库，岂不是对数据库产生压力？能不能有一种方式，不需要大费周章的引入缓存的框架，仅JAVA来实现简单的缓存？于是便发现了我接下来要讲述的几种：LRU、FIFO（linkedHashMap,hashMap）、以及用 weakHashMap 来实现缓存

当然，也是可以直接引入缓存框架的，目前比较常用的缓存有 Readis 、 memcached。

缓存的主要思想有 LRU 和 FIFO。其中 LRU 英文为 Least Recently Used(最近最久未使用)。 FIFO 英文为 first in fisrst out(先进先出)。而实现则主要用 linkedHashMap、hashMap、weakHashMap。

LRU

LRU 缓存思想

  1. 固定缓存大小，需要给缓存分配一个固定的大小。
  2. 每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新（在链式中，则是把这次试用的节点，抽出来放到最后一个）。
  3. 需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存。

这是LinkedHashMap的一个构造函数，传入的第三个参数accessOrder为true的时候，就按访问顺序对LinkedHashMap排序，为false的时候就按插入顺序，默认是为false的。
当把accessOrder设置为true后，就可以将最近访问的元素置于最前面，这样就可以满足上述的第二点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
复制代码/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

这是LinkedHashMap中另外一个方法，当返回true的时候，就会remove其中最久的元素，可以通过重写这个方法来控制缓存元素的删除，当缓存满了后，就可以通过返回true删除最久未被使用的元素，达到LRU的要求。这样就可以满足上述第三点要求。

1
2
3
复制代码protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

由于LinkedHashMap是为自动扩容的，当table数组中元素大于Capacity * loadFactor的时候，就会自动进行两倍扩容。但是为了使缓存大小固定，就需要在初始化的时候传入容量大小和负载因子。
为了使得到达设置缓存大小不会进行自动扩容，需要将初始化的大小进行计算再传入，可以将初始化大小设置为(缓存大小 / loadFactor) + 1，这样就可以在元素数目达到缓存大小时，也不会进行扩容了。这样就解决了上述第一点问题。

通过上面分析，实现下面的代码

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
复制代码import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class LRU1<K, V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;

    LinkedHashMap<K, V> map;

    public LRU1(int cacheSize) {
        MAX_CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
        /*
         * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存
         * 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存
         */
        map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void remove(K key) {
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (Map.Entry<K, V> entry : map.entrySet()) {
            stringBuilder.append(String.format("%s: %s  ", entry.getKey(), entry.getValue()));
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        LRU1<Integer, Integer> lru1 = new LRU1<>(5);
        lru1.put(1, 1);
        lru1.put(2, 2);
        lru1.put(3, 3);
        System.out.println(lru1);
        lru1.get(1);
        System.out.println(lru1);
        lru1.put(4, 4);
        lru1.put(5, 5);
        lru1.put(6, 6);
        System.out.println(lru1);
    }
}

运行结果为：

1
2
3
复制代码1:1 2:2: 3:3
2:2 3:3 1:1
3:3 1:1 4:4 5:5 6:6

FIFO

LRU 缓存思想

  1. 固定缓存大小，需要给缓存分配一个固定的大小。
  2. 每次读取都不改变缓存节点的位置。
  3. 当需要是，缓存满了，就将最先插入的缓存删除，在往里面加。

FIFO 跟 LRU 的代码差不多一直，只是new linkedHashMap时的构造函数传入参数不同。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
复制代码import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class LRU1<K, V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;

    LinkedHashMap<K, V> map;

    public LRU1(int cacheSize) {
        MAX_CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
        /*
         * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存
         * 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存
         */
        map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, false) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void remove(K key) {
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (Map.Entry<K, V> entry : map.entrySet()) {
            stringBuilder.append(String.format("%s: %s  ", entry.getKey(), entry.getValue()));
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        LRU1<Integer, Integer> lru1 = new LRU1<>(5);
        lru1.put(1, 1);
        lru1.put(2, 2);
        lru1.put(3, 3);
        System.out.println(lru1);
        lru1.get(1);
        System.out.println(lru1);
        lru1.put(4, 4);
        lru1.put(5, 5);
        lru1.put(6, 6);
        System.out.println(lru1);
    }
}

看到这里你可能会问：

为什么 LRU 和 FIFO 都用 linkedHashMap 来实现？而不用 hashMap？

其实是因为 linkedHashMap 继承了 hashMap，从它的构造函数可以看出， linkedHashMap 专门对这两种思想进行了实现。而用 hashMap 实现起来比较繁琐。当然也可以实现，网上很多实现方式。这里就不详细讲解了。

weakHashMap

WeakHashMap 和 HashMap 一样是个散列表。但是 weakHashMap 是 WeakReference(弱引用)。也就是，在GC时，没有被引用的会被清除。

hashMap 有一个 Extry 数组，weakHashMap 也有 Entry 数组，不过是继承了 weakReference 的，这也是弱类型的体现所在。

因为 weakHashMap 是弱类型，不需要手动去移除，一切交给GC，所以实现缓存的方式直接 new 即可。

但需要注意的是：

  1. 强引用的key是不会被回收的。
  2. weakHashMap 不是现成安全，若要实现则需要 Collections.synchronizedMap(weakHashMapintsmaze);

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%