해시 테이블(Hash Table)은 도서관.

해시 테이블(Hash Table)은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조입니다. 

이를 위해 해시 함수(Hash Function)를 사용하여 각 데이터의 키(Key)를 해시 값(인덱스)으로 변환합니다.

해시 함수는 임의의 길이를 가진 데이터를 고정된 길이의 해시 값으로 매핑합니다. 

이 과정을 통해 데이터는 테이블 내의 주소(인덱스)로 변환됩니다.

 

 이렇게 변환된 주소를 사용하여 데이터를 테이블(Slot, Bucket)에 저장하거나 검색합니다.

이미지 출처: https://dbehdrhs.tistory.com/70

 

예를 들어, 키가 123817인 데이터를 해시 함수에 넣으면 3819와 같은 해시 값이 나옵니다. 

이 해시 값은 해당 데이터를 저장할 테이블 내의 위치를 결정하는 데 사용됩니다. 

 

 

무슨 말인지 잘 모르겠다면..

 

이 글의 제목처럼 해시 테이블은 도서관.을 생각하면 쉽습니다!

이미지 출처: https://www.pinterest.co.kr/pin/601371356490852311/

도서관은 여러 개의 책을 보관하고 책을 찾을 수 있는 장소입니다. 

 

그러나 도서관마다 책을 보관하는 방식이 다릅니다.

어떤 도서관은 책을 장르별로 보관하고, 또 다른 도서관은 책의 이름이나 저자를 기준으로 책을 보관합니다.

 

예를 들어, 가나다 순으로 책을 보관하는 도서관에서는

해당 방식을 고려하여 책을 찾아야 더 쉽고 빠르게 책을 찾을 수 있을 것입니다.

이제 이 도서관의 예시를 해시 테이블에 접목시켜보겠습니다.

해당 도서관이 책을 보관하는 방식을 해시 함수(Hash Function)라고 하고,

각 도서관은 자신만의 해시 함수(책 보관법)을 갖고 있습니다.

해시 함수를 통해 원하는 책의 위치를 찾아내면 그 위치가 해시 값이 되고,

해당 위치에 책이 보관되어 있는 곳을 버킷 또는, 슬롯이라고 합니다.

 

다시 한 번, 도서관을 머리 속에서 떠올리며 해시 테이블에 대해 생각해보시죠.

(책을 가나다 순으로 나열하는 도서관이라고 생각해봅시다.)

 

해시 테이블은 Key와 Value를 1:1 매핑하여 저장하는 구조이고, Key(책 이름)를 해시 함수에 넣어서 나온 해시 값(책의 이름으로 정해진 보관 위치)에 해당 Value(책)을 저장하는 방식인 것입니다.

따라서 해시 테이블은 데이터를 효율적으로 관리하고 검색할 수 있는 도서관과 같다고 생각하시면 좋을 것 같습니다.

 

이제 조금은 해시 테이블이 머리 속에서 그려지시나요 ?! 🤓

---

해시 충돌 (Hash Collision )

해시 함수는 해시 값의 개수보다 더 많은 키 값을 해시 값으로 변환하기 때문에 

서로 다른 키에 대해 동일한 해시 값을 내는 해시 충돌(Collision)이 발생하게 됩니다.

 

예를 들어, 도서관의 해시 함수가 저자의 이름을 기준으로 한다면 

한 저자가 쓴 다른 책들도 같은 해시 값을 갖게 됩니다. (Collision 발생)

 

해시 테이블에서도 이와 유사한 문제가 발생합니다. 

해시 함수가 정해진 상태로 해시 테이블에 데이터를 저장하기 때문에 언젠가는 똑같은 해시 값을 내는 키가 발생할 것입니다. 

이러한 상황을 우리는 해시 충돌(Collision)이라고 합니다.

 

그렇기 때문에 우리는 해시 함수를 선택할 때 골고루 분산되도록 설계하는 것이 좋습니다. 

좋은 해시 함수의 조건으로는 두 가지를 나타낼 수 있습니다.

첫 번째는 충돌이 적게 발생하는 Less Collision입니다. 

완벽한 해시 함수는 존재하지 않지만, 충돌이 적게 발생하는 함수를 선택하는 것이 중요합니다.

두 번째로는 계산이 빠른 Fast Computation입니다. 

해시 함수의 계산이 빠를수록 더 좋습니다. 해시 테이블에서는 해시 함수 값을 자주 계산해야 하기 때문에 빠른 계산이 필수적입니다. 

 

그러나 이 둘은 상충 관계(Trade-off)에 있습니다.

 

사진 출처: https://www.pinterest.co.kr/pin/597501075536675448/

해시 충돌을 줄이려면 해시 함수를 복잡하게 만들어야 하지만, 이렇게 되면 계산 속도가 느려집니다. 

따라서 두 가지 조건을 모두 고려하여 현재 상황에 맞는 해시 함수를 선택하는 것이 필요합니다.

---

마무리

사람이 뛰어난 해시 함수를 만들어도 완벽하게 충돌을 막을 수는 없습니다.

그래서 우리는

충돌이 발생했을 때를 대처하기 위해 Open addressing과 Chaining 두 가지 방법이 주로 사용합니다.

한 포스팅에 모든 내용을 다루기에는 시간이 부족하여

이번 포스팅에서는 해시 테이블의 개념에 대해서만 다루고 마치겠습니다..!

다음 포스팅에서는 충돌 회피 방법에 대해 더 자세히 다루고,
코드로 구현과 시간 복잡도에 대한 내용을 다룰 예정입니다.

 

잘못된 내용이나 궁금하신 점이 있다면 댓글 남겨주세요. 🤓

읽어주셔서 감사합니다.

---

📝 참고 자료

한국외대 신찬수 교수님의 Data Structures with Python 강의

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/