为何实现LRU缓存优先选择双向链表而非队列+哈希表？

问题要求 #

设计满足最近最少使用（LRU）约束的数据结构，实现LRUCache类：

• LRUCache(int capacity)：初始化容量为正整数的LRU缓存。
• int get(int key)：若key存在则返回对应值，否则返回-1。
• void put(int key, int value)：若key存在则更新值；否则添加键值对，若超过容量则淘汰最近最少使用的键。
  要求get和put方法均满足**平均O(1)**时间复杂度。

我的实现与问题 #

我使用Queue+HashMap实现了LRU缓存，代码如下：

class LRUCache {
    int capacity=0;
    BlockingQueue<Integer> queue;
    Map<Integer, Integer> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        queue = new ArrayBlockingQueue<Integer>(capacity);
    }
    
    public int get(int key) {
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            return map.get(key);
        }
        else
            return -1;
    }
    
    public void put(int key, int value) {
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            map.put(key, value);
        }
        else if(queue.size()<capacity){
            queue.add(key);
            map.put(key,value);
            
        }
        else{
            int oldKey = queue.remove();
            map.remove(oldKey);
            queue.add(key);
            map.put(key,value);
        }
    }
}

该实现通过了22个测试用例中的20个，但剩余用例超时。查阅资料后得知双向链表是最优实现方案，希望了解：

1. 为什么Queue+HashMap的实现会超时？
2. 双向链表为何是LRU缓存的最佳实现方案？

测试结果 #

内容的提问来源于stack exchange，提问作者Karthik G Sarode