Java中多FIFO队列高效插入删除与查找的最优实现方案

核心思路 #

针对你需要的N个FIFO队列（尾部插入、头部删除高效）+ 全局高效查找的场景，最优方案是采用「全局索引Map + 队列容器（双向链表/LinkedHashMap）」的组合，本质是把你提到的“存储分类信息的Map”落地——这是空间换时间的经典思路，也是LFU缓存的标准实现逻辑之一。

具体实现细节 #

1. 自定义数据节点类 #

先定义一个节点类，用来存储数据本身、所属队列的标识（比如频次等级），以及双向链表的前后指针（如果自己实现链表）：

class Node<K, V> {
    K key;
    V value;
    int frequency; // 对应所属队列的编号，比如1对应队列1
    Node<K, V> prev;
    Node<K, V> next;

    public Node(K key, V value, int frequency) {
        this.key = key;
        this.value = value;
        this.frequency = frequency;
    }
}

2. 实现FIFO队列容器（双向链表） #

每个队列用双向链表实现，保证头部删除、尾部插入都是O(1)时间：

class FrequencyQueue<K, V> {
    Node<K, V> head;
    Node<K, V> tail;
    int size;

    // 尾部插入节点
    public void addToTail(Node<K, V> node) {
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
    }

    // 头部删除节点
    public Node<K, V> removeFromHead() {
        if (head == null) return null;
        Node<K, V> removed = head;
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        removed.next = null; // 断开引用，避免内存泄漏
        size--;
        return removed;
    }

    // 移除指定节点（用于数据在队列间移动）
    public void removeNode(Node<K, V> node) {
        if (node == head) {
            removeFromHead();
            return;
        }
        if (node == tail) {
            tail = tail.prev;
            tail.next = null;
            size--;
            return;
        }
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = node.next = null;
        size--;
    }
}

3. 全局管理类 #

用两个Map做全局管理：一个记录每个key对应的节点（实现O(1)查找），另一个管理不同频次对应的队列：

public class LFUQueueManager<K, V> {
    // 全局索引：key -> 对应的节点，实现O(1)查找
    private Map<K, Node<K, V>> keyNodeMap;
    // 频次 -> 对应的队列，管理所有FIFO队列
    private Map<Integer, FrequencyQueue<K, V>> freqQueueMap;
    private int maxQueueCount; // 最大队列数，比如你的N=4

    public LFUQueueManager(int maxQueueCount) {
        this.maxQueueCount = maxQueueCount;
        keyNodeMap = new HashMap<>();
        freqQueueMap = new HashMap<>();
        // 提前初始化所有队列
        for (int i = 1; i <= maxQueueCount; i++) {
            freqQueueMap.put(i, new FrequencyQueue<>());
        }
    }

    // 查找数据：O(1)时间复杂度
    public V get(K key) {
        Node<K, V> node = keyNodeMap.get(key);
        if (node == null) return null;
        // 如果不是最高频次队列，将节点移到下一级队列
        if (node.frequency < maxQueueCount) {
            moveToNextFrequency(node);
        }
        return node.value;
    }

    // 插入/更新数据：默认加入频次1的队列
    public void put(K key, V value) {
        Node<K, V> node = keyNodeMap.get(key);
        if (node != null) {
            node.value = value;
            // 访问后移到下一级队列
            if (node.frequency < maxQueueCount) {
                moveToNextFrequency(node);
            }
            return;
        }
        // 新节点加入频次1队列
        Node<K, V> newNode = new Node<>(key, value, 1);
        keyNodeMap.put(key, newNode);
        freqQueueMap.get(1).addToTail(newNode);
    }

    // 将节点从当前队列移到下一级队列
    private void moveToNextFrequency(Node<K, V> node) {
        int oldFreq = node.frequency;
        FrequencyQueue<K, V> oldQueue = freqQueueMap.get(oldFreq);
        oldQueue.removeNode(node);

        int newFreq = oldFreq + 1;
        node.frequency = newFreq;
        FrequencyQueue<K, V> newQueue = freqQueueMap.get(newFreq);
        newQueue.addToTail(node);
    }

    // 从指定队列头部删除数据
    public V removeFromQueueHead(int freq) {
        FrequencyQueue<K, V> queue = freqQueueMap.get(freq);
        if (queue == null) return null;
        Node<K, V> removedNode = queue.removeFromHead();
        if (removedNode != null) {
            keyNodeMap.remove(removedNode.key);
            return removedNode.value;
        }
        return null;
    }
}

方案优势对比 #

• 对比你最初的LinkedHashMap逐个查找方案：查找操作从O(N)降到了O(1)，插入、删除、队列间移动都是O(1)时间复杂度，完全满足高效要求。
• 关于内存开销：额外的全局Map只存储每个key的节点引用，内存占用远低于重复存储数据的成本，属于合理的空间换时间，在大多数场景下都是最优选择。

替代方案说明 #

如果不想自定义链表，也可以用LinkedHashMap代替自定义的FrequencyQueue——因为LinkedHashMap本身基于双向链表实现，默认维护插入顺序，天然支持尾部插入、头部删除（可通过removeEldestEntry或直接操作头部节点）。但自定义链表的灵活性更高，比如能更方便地实现节点在队列间的移动。

内容的提问来源于stack exchange，提问作者1a1a11a