해시함수 - 버킷사이즈 - 분리체이닝(Separate Chaining)

 

해시 함수

해시함수 mdn 도큐먼트 - Hash_function

해시 함수는 임의의 길이 Key를 고정된 길이의 값으로 매핑하는 함수입니다.

이때 매핑되어 나온 고정된 길이의 값이 해시 값 인거죠!

같은 Key값에 대해서는 언제나 같은 해시 값이 나와야 하고, 반대로 서로 다른 Key값에 대해서는 가능한 서로 다른 해시 값을 생성해야 하는 것이 핵심 포인트입니다.

그런데 해시 함수로 만들어 낸 해시 값은 보통 크고 예측하기 어려운 값으로 나오게 됩니다!

그래서 필요한게 버킷 사이즈죠

---

버킷 사이즈

hash(key) 값으로 2131245이 나왔다면? key-value 값을 2131245번 인덱스에 저장해야 할까요?

이건 좀 그렇죠? 그래서 필요한 것이, 버킷 사이즈를 이용한 아래 공식입니다!

실제 저장 위치(인덱스) = 해시 값 % 버킷 사이즈

버킷 사이즈를 16으로 한다면,

0~15 까지의 인덱스 안에만 값이 저장되게 되는것이죠

버킷 사이즈를 너무 크게 한다면 메모리 낭비가 심해지게 되고, 너무 작게 한다면 한 인덱스에 여러 값이 같이 들어갈 가능성이 높아지고 (이 부분을 해시 충돌 이라고 합니다),

 

---

해시 충돌

해시맵의 핵심은 Key를 통해 데이터가 저장된 위치를 한번에 계산하는 것이었습니다.

하지만 여기에 한 가지 문제가 있습니다.

서로 다른 Key를 해시 함수에 넣었는데 같은 해시 값이 나오는 해시충돌 상황입니다.

아무리 정교한 해시 함수를 사용하더라도, 무한에 가까운 Key의 종류에 비해 유한한 버킷 사이즈를 사용하기 때문에 언젠가는 반드시 일어나게 됩니다.

이를 해결하는 방법 중 하나가 separate chaining 입니다!

 

---

Separate Chaining

Scaler - What is Separate Chaning?

#https://scaler.com/topics/images/separate-chaining-hash-table

분리 체이닝(Separate Chaining)은 연결 리스트를 사용하여 구현된 충돌 해결 기법입니다. 두 개 이상의 요소가 같은 위치에 해시될 때, 이 요소들은 체인처럼 단일 연결 리스트로 표현됩니다. 이 방법은 충돌을 해결하기 위해 추가 메모리를 사용하므로, 개방 해싱(Open Hashing) 이라고도 합니다.

분리 체이닝 에서는 해시 테이블의 각 슬롯이 연결 리스트입니다. 해시 테이블에 저장하기 위해 특정 연결 리스트에 요소를 삽입합니다. 충돌이 발생하면, 즉 해시된 값을 계산한 후 두 개 이상의 요소가 동일한 키에 매핑되는 경우, 해당 요소들을 동일한 연결 리스트에 저장합니다.

쉽게 이야기해서, 값을 어느 인덱스에 넣으려고 했는데 그 곳에 이미 값이 있다면?

index [0] : [축구, 1] → [야구 , 2] → null

이런 식으로 각 노드가 다음 값의 주소를 포인터로 가리키고 있다면

찾는 값이 있을 때, 해당 인덱스의 값들을 모두 뒤져보면서 값을 잃어버리지 않고 찾을 수 있겠죠!

*마지막 노드는 null을 가리켜 마지막 노드임을 명시합니다.

이 방법이 바로 Separate Chaning 입니다!