# Hash

- Hash의 가장 큰 장점은 random access ($O(1)$) 가 가능하다는 것이다. 실제 데이터가 긴 문자열이나 숫자라고 하더라도 이것을 hash function을 통해서 key 를 만들면, $O(1)$의 access time이 소요되기 떄문에 매우 효율적이라고 볼 수 있다.
- 하지만, Hash 가 적합하지 않은 경우는 다음과 같은 경우가 있다.
- 정렬이 필요한 경우
- 키의 길이가 길고 가변적이어서 키에 대한 검색이 필요할 때
- 키가 유일하지 않을때
- 멀티미디어 데이터 저장할 때
- Hash 를 구현하기 위해서는 hash table과 hash function 이 있어야 한다. hash table은 보통 Array로 많이 사용하고, Array의 인덱스를 hask key로
- Hash 에서 가장 중요한 것은 동일한 key가 발생했을 때, 어떻게 해결을 할 것인가 이다. 이것을 `collsion resolution`이라고 부르는데, 해결 방법에는 2가지가 있다.
- 첫번째는 `open addressing`이다. Open addressing 방법은 다른 key의 공간을 사용하는 것을 허용하는 방법이다. 예를 들어, hash table의 1번 공간이 다른 데이터에 의해서 사용되고 있다면, 그 다음 2번 공간에 데이터를 넣는다. 만약에 그 공간마저 사용되고 있다면, 3번 공간에 데이터를 넣는다. 이 방법을 `linear probing`이라고 부른다. `quadratic probing`이라는 방법도 있는데, 1번 공간이 사용되고 있으면 2번 공간을, 2번 공간이 사용되고 있으면 4번 공간을, 4번 공간이 사용되고 있으면 9번 공간을 사용하는 방법이다.

[Open addressing: linear probing](https://baeharam.netlify.app/posts/data%20structure/hash-table/)
- 두번째는 `closed addressing`이다. Closed addressing 방법은 다른 key의 공간을 사용하지 못하도록 한다. 위의 예시에서 1번 공간이 사용되고 있으면 1번 공간에 추가 공간을 덧붙여서 데이터를 저장한다. 그 방법 중 하나가 `separate chaining`이다. Seperate chaining은 추가 공간을 chain 형태로 만드는 방법이다. 대표적인 chain 형태의 자료구조는 Linked List이다. 따라서, 1번 공간이 다른 데이터에 의해서 사용되고 있으면, 그 뒤에 Linked List 형태로 데이터를 추가한다. 또는 데이터의 탐색을 용이하게 하기 위해서 Tree 를 사용하기도 한다.

[Closed addressing: separate chaining](https://intrepidgeeks.com/tutorial/data-structure-table-and-hash5)
- Open addressing이나 Closed addressing 모두 key가 충돌했을 때 사용하는 방법으로 최악의 경우에는 $O(N)$의 탐색 시간이 소요된다. 따라서, hash에서 가장 중요한 것은 '어떻게 하면 key 충돌이 발생하지 않도록 하는 것'이다. 그러기 위해서는 key가 고르게 분산되도록 하는 hash function을 사용하는 것이 중요하다.