[자료 구조] Hash의 개념 설명

• 매핑 : 하나의 값을 다른 값으로 대응시키는 것
• 해시 함수란 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터(Key)를 고정된 길이의 데이터(Hash)로 매핑

⬛ Hash Table

• 해시 테이블은 내부적으로 배열을 사용하여 저장하기 때문에 빠른 검색 속도를 가진다. 이때의 배열을 bucket이라고 한다.
• (key, value)를 저장하는 자료구조로 해시함수를 이용하여 key를 해시값으로 매핑하고, 이 해시값을 value를 저장하기 위한 인덱스로 사용
• 해시 테이블을 이용하여 데이터를 저장하면 key로 value를 찾을 때 해시 함수를 수행하여 value가 있는 위치를 찾을 수 있기 때문에 저장/삭제/조회 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가진다

---

• 전체 데이터의 양이 16이라고 하면 buckets의 사이즈는 16
• hashFunction(key) % 16으로 인덱스의 값을 구한 후 bucket의 해당 인덱스 값에 value를 저장
• 해시함수를 통해 임의의 길이의 데이터를 길이가 2인 데이터로 변환
• 예를 들어, hashFunction(”park123”)%16 = 00이면 bucket의 인덱스가 00인 곳에 value인 “qkr456!” 저장

---

⬛ 충돌(Collision)

• 어설픈 해시 함수를 이용하여 데이터를 계속해서 저장하다보면 계산된 인덱스의 값이 중복될 수 있다. 즉, 서로 다른 key에 대해 동일한 해시값(index)을 가지는 경우이다.
• Collision이 많아질수록 탐색에 필요한 시간 복잡도가 O(N)에 가까워지기 때문에 Collision을 최소화할 수 있는 해시 함수를 정의하는 것이 중요하다. 하지만 입력 값이 무한하기 때문에 충돌은 반드시 발생한다. (비둘기집의 원리)
• 충돌을 최소화할 수 있는 방법
  1. Separating Chaining
  2. Open Addressing

⬛ Separating Chaining

• 해당 주소에 이미 다른 데이터가 있다면 기존의 데이터와 새로운 데이터를 연결리스트를 이용하여 연결하는 방식
• 해시 테이블의 확장이 필요없기 때문에 구현이 간단하고 쉽게 삽입과 삭제가 가능하지만 추가적인 메모리가 필요

⬛ Open Addressing

• 해당 주소에 이미 다른 데이터가 있다면 비어있는 다른 주소를 탐색하여 찾은 주소에 새로운 데이터를 저장하는 방식
• 추가적인 메모리를 사용하지 않지만 데이터를 저장할 수 있는 버킷이 한정되어 있다.
• 주소를 탐색하는 방식

1. 선형 탐색(Linear Probing) : 충돌이 일어났던 인덱스(해시값)에서 고정 폭만큼을 옮겨가며 빈 버킷을 찾아 데이터 저장
   • 만약 인덱스가 2였고 고정폭이 3이었다면, 5가 비어있는 지 확인 → 5가 비어있지 않으면 8 확인 → 8이 비어있으면 해당 버킷에 데이터 저장
2. 제곱 탐색(Quadratic Probing) : 충돌이 일어났던 인덱스(해시값)에서 폭을 제곱씩 늘려 옮겨가며 빈 버킷을 찾아 데이터 저장
   • 만약 인덱스 2였다면, 2 + 11 = 3이 비어있는 지 확인 → 3이 비어있지 않으면 3 + 22 = 7이 비어있는 지 확인 → 7이 비어있으면 해당 버킷에 데이터 저장
3. 이중 해시(Double Hashing Probing) : 충돌이 발생하면 또 다른 해시 함수를 통해 새로운 주소 값을 할당 받고, 새로 할당받은 주소의 버킷이 비어있을 때까지 반복한 후 비어있다면 데이터 저장

•  

⬛ Resizing

• 버킷이 일정 이상 차면 Separating Chaining에서는 연결리스트의 길이가 너무 길어져서 성능이 떨어지고, Open Addressing에서는 많은 데이터를 저장할 수 없기 때문에 버킷의 개수를 늘려줘야 하는데 이러한 과정을 Resizing이라고 한다.
• 보통 두배로 확장하며, 확장하기 위한 임계점인 일정 이상이라는 것은 현재 데이터 개수가 해시 버킷의 개수의 75%가 되었을 때를 의미한다. 이때 0.75라는 숫자는 load factor라고 불린다.

HashTable vs HashMap

해시 테이블은 동기화를 지원하지만 해시 맵은 동기화를 지원하지 않는다.

병렬 처리를 하기 위해 동기화를 고려해야 한다면 해시 테이블을, 병렬 처리를 하지 않아 동기화를 고려하지 않아도 된다면 해시 맵을 사용한다.