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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.