如何不使用HashMap实现O(1)时间复杂度的Java LRU缓存？

嘿，我来给你掰扯清楚怎么用队列、栈、列表、数组这些基础结构实现O(1)时间复杂度的LRU缓存。其实核心逻辑和经典的HashMap+双向链表方案是通的，只是我们得自己用基础结构模拟出HashMap的快速查找能力而已。

1. LRU的核心需求先明确 #

不管用什么结构，LRU要做到两个操作都是O(1)：

• get(key)：存在就返回值，同时把这个节点标记为「最近使用」；不存在返回-1。
• put(key, value)：存在就更新值并标记为最近使用；不存在就新增，缓存满了就删掉「最少使用」的节点再新增。

要满足O(1)，必须解决两个问题：快速找到节点、快速调整节点的使用顺序（移动/删除）。

2. 替代HashMap的方案：自定义哈希桶 #

经典方案用HashMap做O(1)查找，现在我们用「数组+双向链表」来模拟这个功能——也就是哈希桶的思路：

• 用一个数组作为哈希桶的容器，数组的每个索引对应一个「桶」，每个桶是一个双向链表（用来处理哈希冲突）。
• 当要查找key时，先通过哈希函数（比如key.hashCode() % 桶数组长度）算出该key对应的桶索引，然后在桶的双向链表中找节点。只要哈希函数选得合理，冲突会很少，平均查找时间就是O(1)。

3. 核心组件详解 #

我们需要三个核心部分：

（1）自定义双向链表节点 #

每个节点要同时属于两个双向链表：

• 一个是全局LRU链表：维护所有节点的使用顺序，头部是最近使用的节点，尾部是最少使用的节点。
• 一个是哈希桶链表：用来在对应桶中快速定位、删除节点。
  所以节点类要包含这些字段：

class Node {
    int key;
    int value;
    // LRU链表的前后指针
    Node lruPrev;
    Node lruNext;
    // 哈希桶链表的前后指针
    Node bucketPrev;
    Node bucketNext;

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

（2）全局LRU双向链表 #

我们给LRU链表加头尾哨兵节点（避免空指针、简化边界处理），支持三个O(1)操作：

• 把节点移到头部（标记为最近使用）
• 删除任意指定节点
• 删除尾部节点（淘汰最少使用的）

（3）哈希桶数组 #

数组的每个元素是对应桶的头节点，支持两个O(1)操作：

• 把节点加入对应桶的头部
• 从对应桶中删除指定节点

4. 关键操作的O(1)实现 #

（1）get(key)操作 #

1. 用哈希函数算出key对应的桶索引，遍历该桶的链表找到节点（平均O(1)，冲突少的话几乎是直接命中）。
2. 如果找到节点：
   • 从LRU链表的当前位置删除它（O(1)，双向链表直接调整指针）
   • 把它移到LRU链表的头部（O(1)）
   • 返回节点的value
3. 没找到就返回-1。

（2）put(key, value)操作 #

1. 先执行类似get的步骤查找节点：
   • 如果找到：更新节点的value，然后移到LRU头部（O(1)）
   • 如果没找到：
     • 若缓存已满：删除LRU链表的尾部节点（O(1)），同时把该节点从对应的哈希桶中移除（O(1)）
     • 创建新节点，把它加入LRU链表头部（O(1)）和对应哈希桶的头部（O(1)）

5. 注意细节 #

• 哈希桶的大小要选合理：比如设置为缓存容量的1.5~2倍，或者选质数，尽量减少哈希冲突，保证查找的平均时间是O(1)。
• 哨兵节点很重要：给LRU链表加头尾哨兵后，不用处理「链表为空」「只有一个节点」这些边界情况，代码会简洁很多。
• 两个链表的指针要同步维护：删除或移动节点时，必须同时更新LRU链表和哈希桶链表的指针，不然会出现内存泄漏或查找错误。

完整代码示例 #

下面是一个简化的Java实现：

public class LRUCache {
    private int capacity;
    private int size;
    // LRU链表的头尾哨兵
    private Node lruHead;
    private Node lruTail;
    // 哈希桶数组
    private Node[] bucketArray;
    private int bucketSize;

    public LRUCache(int capacity, int bucketSize) {
        this.capacity = capacity;
        this.size = 0;
        this.bucketSize = bucketSize;
        this.bucketArray = new Node[bucketSize];
        // 初始化LRU哨兵
        lruHead = new Node(-1, -1);
        lruTail = new Node(-1, -1);
        lruHead.lruNext = lruTail;
        lruTail.lruPrev = lruHead;
    }

    // 计算哈希桶索引
    private int getBucketIndex(int key) {
        return Math.abs(key.hashCode()) % bucketSize;
    }

    // 在哈希桶中查找节点
    private Node findNodeInBucket(int key) {
        int index = getBucketIndex(key);
        Node current = bucketArray[index];
        while (current != null) {
            if (current.key == key) {
                return current;
            }
            current = current.bucketNext;
        }
        return null;
    }

    // 把节点加入哈希桶头部
    private void addToBucket(Node node) {
        int index = getBucketIndex(node.key);
        Node bucketHead = bucketArray[index];
        if (bucketHead != null) {
            bucketHead.bucketPrev = node;
        }
        node.bucketNext = bucketHead;
        node.bucketPrev = null;
        bucketArray[index] = node;
    }

    // 从哈希桶中移除节点
    private void removeFromBucket(Node node) {
        int index = getBucketIndex(node.key);
        if (node.bucketPrev != null) {
            node.bucketPrev.bucketNext = node.bucketNext;
        } else {
            // 是桶的头节点，更新桶的头指针
            bucketArray[index] = node.bucketNext;
        }
        if (node.bucketNext != null) {
            node.bucketNext.bucketPrev = node.bucketPrev;
        }
        // 清空指针，避免引用残留
        node.bucketPrev = null;
        node.bucketNext = null;
    }

    // 把节点移到LRU头部
    private void moveToLruHead(Node node) {
        removeFromLru(node);
        addToLruHead(node);
    }

    // 从LRU链表移除节点
    private void removeFromLru(Node node) {
        node.lruPrev.lruNext = node.lruNext;
        node.lruNext.lruPrev = node.lruPrev;
    }

    // 把节点加入LRU头部
    private void addToLruHead(Node node) {
        node.lruNext = lruHead.lruNext;
        node.lruPrev = lruHead;
        lruHead.lruNext.lruPrev = node;
        lruHead.lruNext = node;
    }

    // 删除LRU尾部节点（最少使用的）
    private Node removeLruTail() {
        Node tailNode = lruTail.lruPrev;
        removeFromLru(tailNode);
        return tailNode;
    }

    public int get(int key) {
        Node node = findNodeInBucket(key);
        if (node == null) {
            return -1;
        }
        moveToLruHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = findNodeInBucket(key);
        if (node != null) {
            node.value = value;
            moveToLruHead(node);
            return;
        }
        Node newNode = new Node(key, value);
        if (size >= capacity) {
            Node removedNode = removeLruTail();
            removeFromBucket(removedNode);
            size--;
        }
        addToLruHead(newNode);
        addToBucket(newNode);
        size++;
    }

    // 自定义节点类
    static class Node {
        int key;
        int value;
        Node lruPrev;
        Node lruNext;
        Node bucketPrev;
        Node bucketNext;

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

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