2020
10-08
10-08
浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存
LRU:LeastRecentlyUsed最近最少使用,当缓存容量不足时,先淘汰最近最少使用的数据。就像JVM垃圾回收一样,希望将存活的对象移动到内存的一端,然后清除其余空间。缓存基本操作就是读、写、淘汰删除。读操作时间复杂度为O(1)的那就是hash操作了,可以使用HashMap索引key。写操作时间复杂度为O(1),使用链表结构,在链表的一端插入节点,是可以完成O(1)操作,但是为了配合读,还要再次将节点放入HashMap中,put操作最优是O(1),...
继续阅读 >