LeetCode - LRU缓存

Question

我解决了这个LeetCode问题问题。根据(可能)服务器负载，我曾经获得以下性能数字：

我的代码如下：

class LRUCache {

    private static final class LinkedListNode {
        final int key;
        int value;
        LinkedListNode next;
        LinkedListNode prev;

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

    private static final class LinkedList {
        private LinkedListNode head;
        private LinkedListNode tail;

        // Unlinks the given node from its possible predecessor and 
        // successor:
        void unlink(LinkedListNode node) {
            if (head == null) {
                return;
            }

            LinkedListNode prev = node.prev;
            LinkedListNode next = node.next;

            if (prev == null) {
                head = next;
            } else {
                prev.next = next;
                node.prev = null;
            }

            if (next == null) {
                tail = prev;
            } else {
                next.prev = prev;
                node.next = null;
            }
        }

        // Adds the given node after the tail of this list:
        void append(LinkedListNode node) {
            if (tail == null) {
                tail = node;
                head = node;
            } else {
                tail.next = node;
                node.prev = tail;
                node.next = null;
                tail = node;
            }
        }
    }

    private static final class HashTableNode {
        LinkedListNode linkedListNode;
        HashTableNode next;
        HashTableNode prev;

        HashTableNode(LinkedListNode node) {
            this.linkedListNode = node;
        }
    }

    private static final class HashTable {
        private int size;
        private final LinkedList list;
        private final HashTableNode[] table;

        HashTable(int capacity) {
            table = new HashTableNode[capacity];
            list = new LinkedList();
        }

        int size() {
            return size;
        }

        // Adds the given node to this map. If it is already present in the
        // map, the node value is updated. Otherwise, a new mapping is 
        // created:
        void put(LinkedListNode linkedListNode) {
            HashTableNode hashTableNode = getNode(linkedListNode.key);

            if (hashTableNode != null) {
                // Just update the value:
                hashTableNode.linkedListNode.value = linkedListNode.value;
                return;
            }

            hashTableNode = new HashTableNode(linkedListNode);
            int index = linkedListNode.key % table.length;

            if (table[index] != null) {
                table[index].prev = hashTableNode;
                hashTableNode.next = table[index];
            }

            table[index] = hashTableNode;
            size++;
        }

        // Attempts to read a value associated with the given key. Returns
        // -1 if there is no given key in the map:
        int get(int key) {
            HashTableNode node = getNode(key);

            if (node == null) {
                return -1;
            }

            // Relink the node to the tail of the internal linked list:
            list.unlink(node.linkedListNode);
            list.append(node.linkedListNode);
            return node.linkedListNode.value;
        }

        // Removes the mapping wiith the given key:
        private void remove(int key) {
            HashTableNode node = getNode(key);

            if (node == null) {
                // Nothing to remove:
                return;
            }

            int hash = key % table.length;

            if (node.prev == null) {
                // The node to remove is the collision chain head. Advance
                // the collision chain head to the successor node:
                table[hash] = node.next;
            } else {
                // Unlink from the collision chain:
                node.prev.next = node.next;
            }

            // Deal with the removed node successor:
            if (node.next != null) {
                node.next.prev = node.prev;
            }

            --size;
        }

        // Fetches the map node with the given key, or 'null' if there is no
        // such:
        private HashTableNode getNode(int key) {
            int hash = key % table.length;

            for (HashTableNode node = table[hash];
                    node != null;
                    node = node.next) {
                if (node.linkedListNode.key == key) {
                    return node;
                }
            }

            return null;
        }
    }

    private final int capacity;
    private final HashTable table;

    /**
     * Constructs a new cache object.
     * 
     * @param capacity the maximum number of key/value -pairs accepted.
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        table = new HashTable(capacity);
    }

    /**
     * Reads the value associated with the given key.
     * 
     * @param key the key whose value to read.
     * @return the value associated with {@code key}.
     */
    public int get(int key) {
        return table.get(key);
    }

    /**
     * Creates or updates a key/value -mapping.
     * 
     * @param key   the key.
     * @param value the value.
     */
    public void put(int key, int value) {
        HashTableNode hashTableNode = table.getNode(key);

        if (hashTableNode == null) {
            // No 'key' in this cache, create one:
            LinkedListNode linkedListNode = new LinkedListNode(key, value);
            table.list.append(linkedListNode);
            table.put(linkedListNode);
        } else {
            // Update existing mapping with the new value:
            hashTableNode.linkedListNode.value = value;
            table.list.unlink(hashTableNode.linkedListNode);
            table.list.append(hashTableNode.linkedListNode);
            return;
        }

        if (table.size() > capacity) {
            // Here, the cache is too big (by one mapping), remove LRU:
            removeLRU();
        }
    }

    // Removes the head element (that is least recently used) from the 
    // cache:
    private void removeLRU() {
        table.remove(table.list.head.key);
        table.list.unlink(table.list.head);
    }
}

评论请求

请告诉我想到的任何事情。

Answer 1

• get在失败时返回-1总是令人怀疑的。它本质上禁止客户端put值为-1。我建议返回一对bool, value，STL样式。
• HashTable.remove和HashTable.getNode直接在列表上操作也是不对的。考虑创建适当的LinkedList方法。毕竟，LinkedList已经知道其节点的kay字段。
• 为了扩展上面的项目，HashTable.table的元素是链接列表。值得努力提供一个统一的实现一个链接的清单，一个和永远。
• LinkedList.append的两个分支都是tail = node;。如果脱离条件，请将其解除。
• 内联注释(如// No 'key' in this cache, create one或// Update existing mapping with the new value )表明您未能在代码中清楚地表达自己。考虑将注释块作为一个具有正确名称的方法。