Data Structure

• hash table / hash map / hash set

• heap / priority heap / min heap / max heap

• Union Find

• queue interface: LinkedList, PriorityQueue, Deque(doulbe queue)

• Trie (inset/find/startswith)

• Binary Indexed Tree / Fenwick Tree

Hash table / map

• time complexity O(keyLength), not O(1), because need to calculate hash value

• Hash function Magic Number: 31, prime number

• Rehash size / capacity > 10%, need to rehash

collision

Open Hashing vs Closed Hashing

• Open Hashing, LinkedList

deficiency: LinkedList slower than Array https://www.cs.usfca.edu/~galles/visualization/OpenHash.html

• Closed Hashing, Array

deficiency: when item deleted, occupy position, affect find time. https://www.cs.usfca.edu/~galles/visualization/ClosedHash.html

LRU: HashMap + DoublyLinkedList

http://www.jiuzhang.com/solutions/lru-cache/

public class LRUCache {
    private class Node{
        Node prev;
        Node next;
        int key;
        int value;

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

    private int capacity;
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);

        return hs.get(key).value;
    }

    public void set(int key, int value) {
        // get 这个方法会把key挪到最末端，因此，不需要再调用 move_to_tail
        if (get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {
            hs.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        hs.put(key, insert);
        move_to_tail(insert);
    }

    private void move_to_tail(Node current) {
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }
}