해시 Hash

💡 해시함수란?

해시함수는 key를 고정된 길이의 hash로 변경해주는 역할을 하며, 이 과정을 Hashing이라고 한다.
이 해시함수에 key값을 input으로 넣으면 output으로 나오는 것이 바로 Hash이며, 이 해시가 저장 위치가 된다.
즉, 해시 함수는 key로 해시를 만들어내는 함수이다.

💡 해시테이블 구성

1. Key

고유한 값, hash function의 Input이다.
key값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼 정보를 저장할 공간도 따로 마련해야하기 때문에 key의 길이가 제각각일 수 있다. 때문에 고정된 길이의 해시로 변경해준다.

2. Hash Function

Key를 고정된 길이의 Hash로 변경해주는 역할
서로 다른 key가 hashing 후 같은 hash값이 나오는 경우를 해시 충돌이라고 한다. 이런 해시 충돌의 발생 확률이 적을 수록 좋다.
또한 해시 충돌이 균등하게 발생하는 것도 중요하다. 모든 키가 같은 해시값이 나오게 되면, 데이터 저장 시 비효율성이 커지고 보안이 취약해져서 좋지 않다.

3. Value

저장소(버킷, 슬롯)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장된다.

4. Hash Table

해시 함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 주소 또는 색인 삼아 데이터(Value)를 Key와 함께 저장하는 자료구조

💡 해시 테이블의 기능

• 데이터 삽입(저장)

먼저 데이터를 Hash Function을 이용하여 key 값을 hash로 변경한다.
이후 미리 준비해둔 저장소(bucket, slot) 중에 알맞은 hash 값을 찾아 value를 저장한다.
따라서 해시 테이블의 데이터 삽입(저장)과정의 시간 복잡도는 O(1)이다.

• 데이터 삭제

저장된 값을 삭제하기 위해서는 bucket에 삭제할 key와 매칭되는 value 값을 찾아서 삭제한다.
따라서 해시 테이블의 데이터 삭제 과정의 시간 복잡도는 O(1)이다.

• 데이터 검색

key를 이용해 value를 찾아내는 과정이다. key값과 HashFunction을 이용해 hash를 찾고, 이 hash로 value를 찾을 수 있다.
해시 충돌이 일어나지 않는다는 가정 하에 데이터 검색의 시간 복잡도는 O(1)이다.

💡 장점

해시 테이블은 key - value가 1:1로 매핑되어있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있다.

💡 단점

1. 해시 충돌 발생

해시 충돌이 발생할 수 있기 때문에 개방 주소법, 체이닝과 같은 기법으로 해결해야 한다.

2. 순서/관계가 있는 배열에는 어울리지 않는다.

3. 공간 효율성이 떨어진다.

데이터가 저장되기 전에 미리 저장 공간을 만들어놔야해서 만들어둔 공간이 다 차지 않았을 때는 효율성이 떨어진다.

4. Hash Function의 의존도가 높다.

해시 함수가 복잡하면 hash를 만드는 데에 긴 시간이 걸린다.

---

💡 해시 충돌(Hash Collision)

A와 B를 Hash Function으로 해시 값을 얻었는데, 값이 똑같을 경우

💡 해시 충돌 해결 방법

1. Chaining

저장소(Bucket)에서 충돌이 일어나면 기존 값과 새로운 값을 연결 리스트로 연결하는 방법

장점

충돌을 대비하여 미리 공간을 많이 만들 필요가 없다. 충돌이 생기면 그 때 공간을 만들어서 연결해주는 형식.

단점

연결 리스트이기 때문에, 같은 hash에 자료들이 많이 연결되면 검색 시 효율이 낮아진다.

2. Open Addressing(개방 주소법)

충돌이 일어나면 비어있는 hash에 데이터를 저장하는 방법
개방 주소법의 해시테이블은 hash와 value가 1:1 관계를 유지한다.

위와 같은 예시에서 John과 Sandra의 해시 충돌이 발생하고, 산드라가 비어있는 153 hash에 값을 저장한다. 이후 Ted가 153번 hash에 저장을 하려고 봤더니 이미 산드라가 저장되었기 때문에 다음 번호인 154번에 저장한다.

💡 비어있는 Hash를 찾아가는 방법

1. 선형 탐색

해시 값에서 고정값 만큼 건너뛰면서 비어있는 해시가 나오면 저장한다.
이 방법은 특정 해시 값 주변 버킷이 모두 채워져있는 primary clustring 문제에 취약하다는 단점이 있다.

2. 제곱 탐색

고정값이 아닌 1칸 -> 4칸 -> 9칸 -> 16칸 ... 처럼 제곱수만큼 건너 뛰면서 빈 칸을 찾는다.
이 방법은 공간을 많이 확보해야한다는 단점이 있다.