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

# Hash

## Operation

* Insert: `O(1)`
* Delete: `O(1)`
* Find: `O(1)`

## Hash Function

* Magic Number 33

  ```java
  int hash(String key) {
    int sum = 0;
    for (int i = 0; i < key.length(); i++) {
        sum = sum * 33 + (int) (key.charAt(i));
        sum = sum % Hash_TableSize;
    }
    return sum;
  }
  ```

## Hash Collision

### 1. Open Hashing

Use **Linked List** to chain different elements on the same position.\
这个 Visualization 挺好的。

> <https://www.cs.usfca.edu/~galles/visualization/OpenHash.html>

![](https://1241747088-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lpv9LvBSlFaukf_ALqh%2F-Lpv9NPw3Ji1X5Vk8CES%2F-Lpv9xc8cX_yjOlqoP1c%2FopenHashing.png?generation=1569729541616486\&alt=media)

### 2. Closed Hashing

Use **Array** to allocate different elements. If the position is occupied, move to the next available position.\
这个 Visualization 挺好的。

> <https://www.cs.usfca.edu/~galles/visualization/ClosedHash.html>

![](https://1241747088-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lpv9LvBSlFaukf_ALqh%2F-Lpv9NPw3Ji1X5Vk8CES%2F-Lpv9xcAS4_p9wrDP-ZB%2FclosedHashing.png?generation=1569729548375472\&alt=media)

### 3. Rehashing

![](https://1241747088-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lpv9LvBSlFaukf_ALqh%2F-Lpv9NPw3Ji1X5Vk8CES%2F-Lpv9xcCUo0-KbaK-VV3%2FreHashing.png?generation=1569729541840010\&alt=media)

## Thread Safe

> In Java, which one is thread safe? HashMap, HashSet and HashTable.

**HashTable**.