📌 오늘의 질문: 해시 테이블(Hash Table)은 무엇이고, 왜 그렇게 빠른가요? 많은 언어에서 딕셔너리, 맵 등으로 쓰이는 핵심 자료구조죠! '해시 충돌(Collision)'에 대해서도 들어보셨다면 함께 이야기 나눠봐요.
해시 테이블은 '키(Key)'와 '값(Value)'을 짝지어 저장하는 자료구조로, 빠르게 조회하기 위함이다.
일반적인 배열에서, 특정 데이터를 찾으려면 처음부터 끝까지 모두 찾아봐야한다.
그렇기 때문에 데이터가 많아질수록 탐색 시간이 늘어난다()
반면, 해시 테이블은 Key 값을 넣자마자 Value가 저장된 위치(인덱스)를 곧바로 계산해 낸다.
평균 시간 복잡도:
키 -> 해시함수 -> 배열 인덱스
Hash(key) -> index
키값을 해시함수에 넣은 결과물이 곧 위치값(인덱스값)이다.
"김민수"를 찾고 싶음
↓
hash("김민수")
↓
28
↓
해시테이블의 table[28] 이동
↓
("김민수", "010-1234-5678")
↓
전화번호 반환💥 피할 수 없는 숙명: 해시 충돌 (Hash Collision)
해시 테이블은 무한한 종류의 Key들을 유한한 크기의 메모리 공간(버킷)에 매핑해야 합니다. 그러다 보니 "서로 다른 두 개 이상의 Key가 해시 함수를 거쳤는데 똑같은 인덱스를 배정받는 상황"이 발생하는데, 이를 해시 충돌이라고 합니다.
이를 해결하기 위해 대표적으로 두 가지 영리한 알고리즘을 사용합니다.
1. 분리 연결법 (Chaining)
충돌이 발생하면, 같은 인덱스 자리에 데이터를 덮어쓰는 것이 아니라 링크드 리스트(Linked List) 형태로 뒤에 줄을 세우는 방식입니다.
- 장점: 테이블 공간을 효율적으로 쓸 수 있고, 충돌이 발생해도 연결리스트에 슥 추가하면 되니 구현이 비교적 간단합니다. (Java의 HashMap 등이 이 방식을 채택하고 있습니다.)
- 주의점: 한 인덱스에만 데이터가 너무 많이 몰리면(최악의 경우), 데이터를 찾을 때 링크드 리스트를 쭉 타고 들어가야 하므로 속도가 에 수렴할 수 있습니다.
2. 개방 주소법 (Open Addressing)
충돌이 발생하면, "빈 방이 있을 테니 다른 주소를 찾아 떠나자!" 하고 테이블의 다른 빈 버킷을 찾아 데이터를 저장하는 방식입니다. 비어있는 공간을 찾는 방법(Probing)에는 여러 가지가 있습니다.
- 선형 탐사(Linear Probing): 충돌이 나면 바로 다음 칸, 또 충돌이 나면 그다음 칸(+1, +2, +3...)을 순차적으로 확인하며 빈 곳을 찾습니다. (공간 밀집도가 높아져 특정 구역에 데이터가 몰리는 '클러스터링' 문제가 생길 수 있습니다.)
- 이차 탐사(Quadratic Probing): 제곱수만큼 건너뛰며() 빈 공간을 찾습니다.
- 이중 해시(Double Hashing): 충돌 발생 시 이동할 간격을 또 다른 해시 함수로 계산하여 무작위성을 높입니다.
