> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/topics/data-structure.md).

# 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 ![](https://stomachache007.files.wordpress.com/2017/04/9.png?w=531\&zoom=2)
* 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> ![](https://algs4.cs.princeton.edu/34hash/images/separate-chaining.png)

* Closed Hashing, Array

deficiency: when item deleted, occupy position, affect find time. <https://www.cs.usfca.edu/~galles/visualization/ClosedHash.html> ![](https://i.stack.imgur.com/dZI6E.gif)

### LRU: HashMap + DoublyLinkedList

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

```java
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;
    }
}
```