我想实现一个简单的MRU缓存:我将使用队列:
get(Object):
- 检查队列是否包含对象
- YES:将它从队列中移除并插入到队列的开始位置
- No:向系统转发请求，获取元素并在开头插入
这个方法可以吗?我见过许多使用Maps的实现，但我不明白为什么。为什么我需要一个键值对缓存?
因为使用map检查集合是否包含元素要快得多(理论上为O(1))，而使用队列则必须遍历所有现有元素并进行比较，即O(sizeOfQueue)