Java中如何实现LRU缓存且时间复杂度为O(1)的算法原理？

本文共计889个文字，预计阅读时间需要4分钟。

LRU缓存：最近最少使用，当缓存容量不足时，先淘汰最近最少使用的元素。类似JVM垃圾回收，希望将活跃的对象移动到内存的一端，然后清除其余空间。缓存基本操作：添加、查询、删除。

LRU：Least Recently Used最近最少使用，当缓存容量不足时，先淘汰最近最少使用的数据。就像JVM垃圾回收一样，希望将存活的对象移动到内存的一端，然后清除其余空间。

缓存基本操作就是读、写、淘汰删除。

读操作时间复杂度为O(1)的那就是hash操作了，可以使用HashMap索引 key。

写操作时间复杂度为O(1)，使用链表结构，在链表的一端插入节点，是可以完成O(1)操作，但是为了配合读，还要再次将节点放入HashMap中，put操作最优是O(1)，最差是O(n)。

不少童鞋就有疑问了，写入时又使用map进行了put操作，为何缓存不直接使用map？没错，首先使用map存储了节点数据就是采用空间换时间，但是淘汰删除不好处理，使用map如何去记录最近最少使用(涉及到时间、频次问题)。so，使用链表可以将活跃节点移动到链表的一端，淘汰时直接从另一端进行删除。