[Java] Map Implementations

Documents: https://docs.oracle.com/javase/tutorial/collections/implementations/map.html


General-Purpose Map Implementations:

• HashMap
• TreeMap
• LinkedHashMap

Special-Purpose Map Implementations:

• EnumMap
• WeakHashMap
• IdentityHashMap

Concurrent Map Implementations:

• The java.util.concurrent package contains the ConcurrentMap interface, which extends Map with atomic putIfAbsent, remove, and replace methods, and the ConcurrentHashMap implementation of that interface.

---

Example: [LeetCode] 146. LRU Cache

• Link: https://leetcode.com/problems/lru-cache/description/
• HashMap + Doubly Linked List
• Illustration is here: http://androidsrc.net/lru-cache-java-implementation/

public class LRUCache {
    private int capacity;
    private Map<Integer, Node> cache;
    private DoublyLinkedList doublyLinkedList;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.doublyLinkedList = new DoublyLinkedList();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        doublyLinkedList.moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            doublyLinkedList.moveToTail(node);
            node.value = value;
            return;
        }

        if (cache.size() == capacity) {
            cache.remove(doublyLinkedList.first().key);
            doublyLinkedList.remove(doublyLinkedList.first());
        }

        Node insert = new Node(key, value);
        cache.put(key, insert);
        doublyLinkedList.addToTail(insert);
    }
    
    public static class DoublyLinkedList {
        private Node head;
        private Node tail;

        public DoublyLinkedList() {
            this.head = new Node();
            this.tail = new Node();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
        
        public Node first() {
            return head.next;
        }
        
        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        public void addToTail(Node node) {
            node.prev = tail.prev;
            tail.prev = node;
            node.prev.next = node;
            node.next = tail;
        }
        
        public void moveToTail(Node node) {
            remove(node);
            addToTail(node);
        }
    }
    
    public static class Node {
        public int key;
        public int value;
        public Node prev;
        public Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        
        public Node() {
            this.key = -1;
            this.value = -1;
        }
    }
}

---

Example: [LeetCode] 460. LFU Cache

• Link: https://leetcode.com/problems/lfu-cache/description/
• Reference: http://dhruvbird.com/lfu.pdf

class LFUCache {
    private int capacity;
    private HashMap<Integer, Integer> valueHash;
    private Node head;
    private HashMap<Integer, Node> nodeHash;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.valueHash = new HashMap<>();
        this.nodeHash = new HashMap<>();
    }
    
    public int get(int key) {
        if (valueHash.containsKey(key)) {
            increaseFrequency(key);
            return valueHash.get(key);
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (!valueHash.containsKey(key)) {
            if (valueHash.size() == capacity) {
                removeOldestKey();
            }
            addToHead(key);
        }
        valueHash.put(key, value);    
        increaseFrequency(key);
    }
    
    private void addToHead(int key) {
        if (head == null) {
            head = new Node(0);
        } else if (head.frequency > 0) {
            Node node = new Node(0);
            node.next = head;
            head.prev = node;
            head = node;
        }
        head.bucket.add(key);
        nodeHash.put(key, head);      
    }
    
    private void increaseFrequency(int key) {
        Node node = nodeHash.get(key);
        node.bucket.remove(key);
        
        if (node.next == null) {
            node.next = new Node(node.frequency + 1);
            node.next.prev = node;
        } else if (node.next.frequency > node.frequency + 1) {
            Node middle = new Node(node.frequency + 1);
            middle.prev = node;
            middle.next = node.next;
            node.next.prev = middle;
            node.next = middle;
        }
        node.next.bucket.add(key);
        nodeHash.put(key, node.next);
        if (node.bucket.isEmpty()) {
            removeNode(node);
        }
    }
    
    private void removeOldestKey() {
        if (head == null) { 
            return;
        }
        int oldestKey = getOldestKey();
        head.bucket.remove(oldestKey);
        if (head.bucket.isEmpty()) {
            removeNode(head);   
        }
        nodeHash.remove(oldestKey);
        valueHash.remove(oldestKey);
    }
    
    private int getOldestKey() {
        for (int n : head.bucket) {
            return n;
        }
        return 0;
    }
    
    private void removeNode(Node node) {
        if (node.prev == null) {
            head = node.next;
        } else {
            node.prev.next = node.next;
        } 
        if (node.next != null) {
            node.next.prev = node.prev;
        }        
    }
    
    public static class Node {
        public int frequency;
        public LinkedHashSet<Integer> bucket;
        public Node prev;
        public Node next;
        
        public Node(int frequency) {
            this.frequency = frequency;
            this.bucket = new LinkedHashSet<>();
        }
    }
}