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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/topics/data-structure.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.