详解Java实现缓存(LRU,FIFO)
现在软件或者网页的并发量越来越大了,大量请求直接操作数据库会对数据库造成很大的压力,处理大量连接和请求就会需要很长时间,但是实际中百分之80的数据是很少更改的,这样就可以引入缓存来进行读取,减少数据库的压力。
常用的缓存有redis和memcached,但是有时候一些小场景就可以直接使用java实现缓存,就可以满足这部分服务的需求。
缓存主要有lru和fifo,lru是least recently used的缩写,即最近最久未使用,fifo就是先进先出,下面就使用java来实现这两种缓存。
lru
lru缓存的思想
- 固定缓存大小,需要给缓存分配一个固定的大小。
- 每次读取缓存都会改变缓存的使用时间,将缓存的存在时间重新刷新。
- 需要在缓存满了后,将最近最久未使用的缓存删除,再添加最新的缓存。
按照如上思想,可以使用linkedhashmap来实现lru缓存。
这是linkedhashmap的一个构造函数,传入的第三个参数accessorder为true的时候,就按访问顺序对linkedhashmap排序,为false的时候就按插入顺序,默认是为false的。
当把accessorder设置为true后,就可以将最近访问的元素置于最前面,这样就可以满足上述的第二点。
/** * 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的要求。这样就可以满足上述第三点要求。
protected boolean removeeldestentry(map.entry<k,v> eldest) { return false; }
由于linkedhashmap是为自动扩容的,当table数组中元素大于capacity * loadfactor的时候,就会自动进行两倍扩容。但是为了使缓存大小固定,就需要在初始化的时候传入容量大小和负载因子。
为了使得到达设置缓存大小不会进行自动扩容,需要将初始化的大小进行计算再传入,可以将初始化大小设置为(缓存大小 / loadfactor) + 1,这样就可以在元素数目达到缓存大小时,也不会进行扩容了。这样就解决了上述第一点问题。
通过上面分析,实现下面的代码
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); } }
运行结果:
从运行结果中可以看出,实现了lru缓存的思想。
接着使用hashmap和链表来实现lru缓存。
主要的思想和上述基本一致,每次添加元素或者读取元素就将元素放置在链表的头,当缓存满了之后,就可以将尾结点元素删除,这样就实现了lru缓存。
这种方法中是通过自己编写代码移动结点和删除结点,为了防止缓存大小超过限制,每次进行put的时候都会进行检查,若缓存满了则删除尾部元素。
import java.util.hashmap; /** * 使用cache和链表实现缓存 */ public class lru2<k, v> { private final int max_cache_size; private entry<k, v> head; private entry<k, v> tail; private hashmap<k, entry<k, v>> cache; public lru2(int cachesize) { max_cache_size = cachesize; cache = new hashmap<>(); } public void put(k key, v value) { entry<k, v> entry = getentry(key); if (entry == null) { if (cache.size() >= max_cache_size) { cache.remove(tail.key); removetail(); } } entry = new entry<>(); entry.key = key; entry.value = value; movetohead(entry); cache.put(key, entry); } public v get(k key) { entry<k, v> entry = getentry(key); if (entry == null) { return null; } movetohead(entry); return entry.value; } public void remove(k key) { entry<k, v> entry = getentry(key); if (entry != null) { if (entry == head) { entry<k, v> next = head.next; head.next = null; head = next; head.pre = null; } else if (entry == tail) { entry<k, v> prev = tail.pre; tail.pre = null; tail = prev; tail.next = null; } else { entry.pre.next = entry.next; entry.next.pre = entry.pre; } cache.remove(key); } } private void removetail() { if (tail != null) { entry<k, v> prev = tail.pre; if (prev == null) { head = null; tail = null; } else { tail.pre = null; tail = prev; tail.next = null; } } } private void movetohead(entry<k, v> entry) { if (entry == head) { return; } if (entry.pre != null) { entry.pre.next = entry.next; } if (entry.next != null) { entry.next.pre = entry.pre; } if (entry == tail) { entry<k, v> prev = entry.pre; if (prev != null) { tail.pre = null; tail = prev; tail.next = null; } } if (head == null || tail == null) { head = tail = entry; return; } entry.next = head; head.pre = entry; entry.pre = null; head = entry; } private entry<k, v> getentry(k key) { return cache.get(key); } private static class entry<k, v> { entry<k, v> pre; entry<k, v> next; k key; v value; } @override public string tostring() { stringbuilder stringbuilder = new stringbuilder(); entry<k, v> entry = head; while (entry != null) { stringbuilder.append(string.format("%s:%s ", entry.key, entry.value)); entry = entry.next; } return stringbuilder.tostring(); } public static void main(string[] args) { lru2<integer, integer> lru2 = new lru2<>(5); lru2.put(1, 1); system.out.println(lru2); lru2.put(2, 2); system.out.println(lru2); lru2.put(3, 3); system.out.println(lru2); lru2.get(1); system.out.println(lru2); lru2.put(4, 4); lru2.put(5, 5); lru2.put(6, 6); system.out.println(lru2); } }
运行结果:
fifo
fifo就是先进先出,可以使用linkedhashmap进行实现。
当第三个参数传入为false或者是默认的时候,就可以实现按插入顺序排序,就可以实现fifo缓存了。
/** * 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实现lru的代码基本一致,主要就是构造函数的传值有些不同。
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); } }
运行结果:
以上就是使用java实现这两种缓存的方式,从中可以看出,linkedhashmap实现缓存较为容易,因为底层函数对此已经有了支持,自己编写链表实现lru缓存也是借鉴了linkedhashmap中实现的思想。在java中不只是这两种数据结构可以实现缓存,比如concurrenthashmap、weakhashmap在某些场景下也是可以作为缓存的,到底用哪一种数据结构主要是看场景再进行选择,但是很多思想都是可以通用的。
下一篇: Python中扩展包的安装方法详解