Java LRU Cache implementation without using util.HashMap


  • -1
    3

    I basically implemented a HashMap with its entry table being doubly-linked list.

    public class LRUCache {
        Entry[] table;
        int size;
        int capacity;
        Entry head;
        Entry tail;
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            table = new Entry[capacity];
            head = new Entry();
            tail = new Entry();
            head.post = tail;
            tail.pre = head;
            size = 0;
        }
    
        public int get(int key) {
            int hash = hash(key);
            int index = indexFor(hash, capacity);
            for (Entry e = table[index]; e != null; e = e.next) {
                if (e.hash == hash && e.key == key) {
                    moveToHead(e);
                    return e.value;
                }
            }
            return -1;
        }
    
        public void set(int key, int value) {
            int hash = hash(key);
            int index = indexFor(hash, capacity);
            for (Entry e = table[index]; e != null; e = e.next) {
                if (e.hash == hash && e.key == key) {
                    e.value = value;
                    moveToHead(e);
                    return;
                }
            }
            Entry curEntry = table[index];
            Entry newEntry = new Entry(key, value, hash, curEntry, null, null);
            table[index] = newEntry;
            moveToHead(newEntry);
            size++;
            if (size > capacity) {
                popTail();
            }
    
        }
        
        void popTail() {
            Entry toRemove = tail.pre;
            removeEntry(toRemove);
            toRemove.pre.post = tail;
            tail.pre = toRemove.pre;
        }
    
        void moveToHead(Entry entry) {
            if (entry.pre != null) {
                entry.pre.post = entry.post;
            }
            if (entry.post != null) {
                entry.post.pre = entry.pre;
            }
            entry.post = head.post;
            entry.pre = head;
            head.post.pre = entry;
            head.post = entry;
        }
        
        void removeEntry(Entry entry) {
            int hash = entry.hash;
            int index = indexFor(hash, capacity);
            if (table[index] == entry) {
                table[index] = entry.next;
            } else {
                for (Entry e = table[index]; e.next != null; e = e.next) {
                    if (e.next == entry) {
                        e.next = entry.next;
                        return;
                    }
                }
            }
            size--;
        }
    
        int indexFor(int hash, int length) {
            return hash % length;
        }
    
        int hash(int key) {
            key ^= (key>>>20) ^ (key >>>12);
            return key ^ (key>>>7) ^ (key>>>4);
        }
    
        static class Entry {
            final int key;
            int value;
            final int hash;
            Entry next;
            Entry pre;
            Entry post;
    
            Entry(int key, int value, int hash, Entry next, Entry pre, Entry post) {
                this.key = key;
                this.value = value;
                this.hash = hash;
                this.next = next;
                this.pre = pre;
                this.post = post;
            }
    
            Entry() {
                this.key = 0;
                this.hash = 0;
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.