자료구조 - 해시 테이블(HashTable)

Q. 해시 테이블(HashTable)이란 무엇인가요?

해시 테이블은 (Key, Value) 형태로 데이터를 저장하는 자료구조 중 하나로, 빠른 데이터 검색을 지원합니다. 빠른 검색 속도가 가능한 이유는 내부적으로 배열을 사용하고, 해시 함수를 통해 각 Key를 고유한 index로 변환하여 데이터에 접근하기 때문입니다. 이때 실제 값이 저장되는 공간을 버킷(Bucket) 또는 슬롯(Slot)이라고 합니다. 해시 테이블의 가장 큰 특징은 평균적으로 O(1)의 시간복잡도로 데이터를 저장/검색/삭제할 수 있다는 점입니다. 하지만 해시 충돌이 발생하는 최악의 경우, 시간복잡도가 O(N)까지 증가할 수 있습니다.

Q. 해시 충돌에 대해 조금 더 자세히 설명해주세요.

해시 충돌은 서로 다른 Key가 해시 함수를 통해 동일한 index를 가리키게 되는 현상을 말합니다. 이러한 충돌을 해결하기 위한 대표적인 방법으로는 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing)이 있습니다. 분리 연결법은 동일한 버킷에 데이터가 충돌하면 연결 리스트나 트리와 같은 자료구조를 활용해 데이터를 연결하는 방식입니다. Java8의 HashMap은 이 방식을 사용하며, 특히 하나의 버킷에 데이터가 8개 이상 모이면 링크드 리스트에서 레드-블랙 트리로 자동 전환되어 성능을 개선합니다. 개방 주소법은 추가 메모리를 사용하지 않고 해시 테이블 내의 빈 공간을 활용하는 방식입니다. 충돌이 발생하면 특정 규칙에 따라 다음 버킷을 탐색하여 데이터를 저장합니다. 이 방식은 데이터 삭제 시 해당 공간을 단순히 비우면 검색에 문제가 생길 수 있어, Dummy Space로 표시하고 주기적으로 재정리가 필요합니다.

Q. Open Addressing의 세 가지 방식을 설명해주세요.

Open Addressing은 Linear Probing, Quadratic Probing, Double Hashing 세 가지 방식으로 구현할 수 있습니다. Linear Probing은 충돌 발생 시 순차적으로 다음 버킷을 탐색하는 가장 단순한 방식입니다. 구현이 쉽고 캐시 지역성이 좋아 실제로 자주 사용되지만, 특정 영역에 데이터가 몰리는 일차 군집화(Primary Clustering) 문제가 있습니다. Quadratic Probing은 충돌 발생 시 1², 2², 3²... 순으로 건너뛰며 탐색하는 방식입니다. Linear Probing의 군집화 문제는 완화되지만, 여전히 이차 군집화(Secondary Clustering)가 발생할 수 있고, 최악의 경우 모든 버킷을 탐색하지 못할 수 있습니다. Double Hashing은 두 개의 해시 함수를 사용합니다. 첫 번째 해시 함수로 기본 위치를 정하고, 충돌 시 두 번째 해시 함수로 건너뛸 간격을 결정합니다. 군집화 문제를 효과적으로 해결할 수 있지만, 추가적인 해시 함수 연산으로 인한 성능 부하가 있습니다. 모든 Open Addressing 방식은 해시 테이블의 부하율(Load Factor)이 높아지면 성능이 급격히 저하되므로, 적절한 임계점에서 rehashing을 통한 크기 조정이 필수적입니다.