Hash

---

Hash?

해시는 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 것을 말한다.

이 과정에서 원본 데이터를 키(Key), 매핑하는 과정을 해싱(Hashing), 결과 데이터를 해시값(Hash Value)이라한다.

그리고 이렇게 데이터를 해싱하는 함수를 해시 함수(Hash Function)라 한다.

• 키 : 매핑 전 원래 데이터의 값
• 해시값 : 매핑 후 데이터의 값
• 해시 함수 : 데이터를 해싱하는 함수

Hash의 특징

• 임의의 길이 데이터로부터 고정된 길이 해시값을 얻는다.
• 단방향성이므로 해시값으로부터 키를 역산할 수 없다.
• 하나의 키 값에 하나의 해시값을 가져야 한다.

---

Hash collision

해시 함수는 해시값의 보통 입력의 범위보다 출력 값의 범위가 좁은 경우가 많기 때문에 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시 충돌이 발생할 수 있다.

이를 해결하기 위한 방법에는 분리 연결법과 개방 주소법이 존재한다.

분리 연결법(Separate Chaining)

분리 연결법은 충돌이 발생하면 Linked List를 사용해 연결된 새로운 공간을 사용하는 방법이다.

장점

• 연결 리스트를 사용하기 때문에 보다 유연하게 사용가능하고, 해시값을 그대로 사용할 수 있다.

단점

• 하지만 연결 리스트를 사용하기 때문에 추가적인 공간이 필요하고 메모리 문제가 발생할 수 있다.

• 연결 리스트는 검색 시 O(n) 걸리므로 같은 해시값을 갖는 데이터가 많아진다면 해시를 사용하는 이유가 사라진다.

개방 주소법(Open Addressing)

개방 주소법은 충돌이 발생하면 다른 버킷을 사용하는 방법이다.

다른 버킷을 찾는 방법에는 대표적으로 3가지가 존재한다.

1. 선형 탐색(Linear Probing) : 충돌 시 다음 버킷, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
2. 제곱 탐색(Quadratic Probing) : 충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입한다.(1,4,9,16..)
3. 이중 해시(Double Hashing) : 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용한다.

장점

• 고정된 크기의 배열을 사용하므로 추가적인 공간을 필요로 하지 않는다.

• 데이터가 적을 때는 연속된 공간에서 빠르게 찾을 수 있기 때문에 분리 연결법보다 좋은 성능을 보인다.

단점

• 데이터가 많아지면 충돌이 발생했을 때 다음 빈 버킷을 찾기 어려워지고, 값이 자주 추가되고 삭제되면 성능이 떨어진다.