안녕하세요, 이력서 기반 면접 준비를 도와드리는 QueryDaily 팀입니다.
"해시 테이블의 시간 복잡도는?" "O(1)입니다!"
여기까지는 자신 있게 대답하는 분들이 많습니다. 하지만 면접관이 미소를 지으며 이렇게 묻는다면 어떨까요?
"오, 그런가요? 항상 O(1)이라고 할 수 있을까요?"
이 꼬리 질문에 잠시 머리가 하얘지는 경험, 혹시 없으신가요? 괜찮습니다. 많은 개발자들이 이 '마법'의 함정에 빠지곤 합니다. 오늘은 해시 테이블의 O(1)이라는 놀라운 성능의 비밀과, 그 이면에 숨겨진 '해시 충돌'이라는 재앙에 대해 깊이 파헤쳐 보겠습니다.
O(1)이라는 마법의 비밀: 해시 함수
해시 테이블은 내부적으로 배열이라는 단순한 자료구조를 사용합니다. 배열은 인덱스를 알면 어떤 원소든 한 번에 접근할 수 있죠. 바로 이 특징이 O(1)의 핵심입니다.
그렇다면 해시 테이블은 어떻게 Key-Value 형태의 데이터를 배열의 인덱스와 연결시키는 걸까요? 바로 해시 함수(Hash Function)가 그 역할을 합니다.
- 해시 함수: 임의의 길이의 데이터를 고정된 길이의 데이터(해시 값)로 매핑하는 함수
- 해시 테이블의 적용: Key 값을 해시 함수에 넣어 나온 결과(해시 값)를 배열의 인덱스로 사용하는 것
// 간단한 해시 함수의 예시 (문자열의 길이를 인덱스로 사용)
int getHash(String key) {
return key.length();
}
int index = getHash("my_key"); // "my_key" -> 6
// 이제 배열의 6번 인덱스에 원하는 값을 저장하면 됩니다.이처럼 어떤 Key가 들어오든 해시 함수를 통해 곧바로 인덱스를 계산할 수 있기 때문에, 해시 테이블은 마치 마법처럼 O(1)의 속도로 데이터에 접근할 수 있는 것입니다.
피할 수 없는 재앙, 해시 충돌(Collision)
하지만 이 마법은 완벽하지 않습니다.
만약 서로 다른 Key를 해시 함수에 넣었는데 같은 결과(인덱스)가 나온다면 어떻게 될까요?
getHash("my_key") -> 6 getHash("ur_key") -> 6하나의 인덱스에 두 개의 값을 동시에 저장할 수는 없습니다. 이처럼 서로 다른 Key가 같은 해시 값을 가지는 상황을 바로 해시 충돌(Hash Collision)이라고 부릅니다.
해시 충돌은 '비둘기집 원리'처럼 필연적으로 발생할 수밖에 없습니다. 무한한 Key의 가짓수를 유한한 배열의 인덱스로 매핑하기 때문이죠. 따라서 좋은 해시 테이블이란, 충돌을 얼마나 적게 일으키는지, 그리고 발생한 충돌을 얼마나 효율적으로 해결하는지에 따라 결정됩니다.
재앙을 극복하는 방법들 (충돌 해결법)
해시 충돌이 발생했을 때, 데이터를 어떻게 저장해야 할까요? 가장 널리 쓰이는 두 가지 방법을 소개합니다.
1. Separate Chaining (분리 연결법)
가장 일반적인 해결책입니다. 이름 그대로, 충돌이 발생한 데이터를 별도의 공간에 연결해주는 방식입니다. 동일한 인덱스로 해싱된 데이터들을 링크드 리스트(Linked List) 로 줄줄이 연결하여 저장하는 것이죠.
- 장점: 구현이 비교적 간단하고, 데이터가 얼마나 늘어날지 예측하기 어려울 때 유용합니다.
- 단점: 링크드 리스트의 순회가 필요하므로, 최악의 경우(모든 데이터가 하나의 인덱스에 충돌) 시간 복잡도가 O(N) 까지 증가할 수 있습니다. O(1)의 마법이 깨지는 순간이죠.
2. Open Addressing (개방 주소법)
별도의 자료구조를 사용하지 않고, 비어있는 다른 인덱스를 찾아 데이터를 저장하는 방식입니다. 예를 들어, 6번 인덱스에 충돌이 나면 바로 옆인 7번, 8번, ... 인덱스가 비어있는지 확인하고 그곳에 저장하는 식이죠. (이를 Linear Probing 이라고 합니다.)
- 장점: 추가적인 자료구조가 필요 없어 메모리를 더 효율적으로 사용할 수 있습니다.
- 단점: 데이터가 특정 영역에 몰리는 '클러스터링(Clustering)' 현상이 발생할 수 있고, 데이터 삭제가 까다롭습니다.
면접관의 꼬리 질문
자, 이제 처음의 질문으로 돌아가 봅시다. 면접관은 여러분의 깊이를 확인하기 위해 이런 질문들을 던질 수 있습니다.
Q1. "해시 충돌이 최악의 경우, 시간 복잡도는 어떻게 되나요?"
A: "Separate Chaining 방식의 경우,
모든 데이터가 하나의 버킷에 충돌하면 링크드리스트를 처음부터 끝까지
순회해야 하므로, 탐색/삽입/삭제 모두 시간 복잡도가 O(N)이 됩니다."Q2. "Java의 HashMap은 충돌을 어떻게 해결하나요?"
A: "Java 8 이전에는 Separate Chaining만을 사용했습니다.
하지만 Java 8부터는 Chaining 방식을 사용하되, 하나의 버킷에
저장된 데이터 개수가 8개를 넘어가면 링크드리스트를
레드-블랙 트리(Red-Black Tree) 로 변환하여 성능을 개선했습니다.
트리를 사용하면 최악의 경우에도 시간 복잡도를 O(log N)으로
보장할 수 있기 때문입니다."결론
✅ 해시 테이블은 해시 함수를 통해 Key를 인덱스로 변환하여 평균 O(1) 의 빠른 속도를 자랑합니다.
✅ 하지만 해시 충돌은 피할 수 없으며, 충돌 발생 시 성능이 저하될 수 있습니다.
✅ 따라서 Chaining, Open Addressing 같은 충돌 해결 전략을 이해하는 것이 중요하며, 이것이 해시 테이블의 최악의 경우 시간 복잡도가 O(N) 또는 O(log N)이 되는 이유입니다.
오늘 알아본 것처럼, CS의 핵심 개념 하나를 깊게 파고들어 '왜?'라고 질문하는 연습은 합격의 핵심입니다.
QueryDaily는 여러분의 이력서와 경험을 바탕으로 바로 이런 깊이 있는 꼬리 질문들을 매일 제공하여, 면접을 완벽하게 대비할 수 있도록 돕습니다.
꾸준한 연습만이 합격의 문턱을 낮출 수 있습니다.
