해시맵에서 충돌이 많이 발생하면 성능에 어떤 영향이 있나요?

면접 답변

해시맵에서 충돌이 많이 발생하면, 해시 버킷 하나에 여러 개의 엔트리가 모이게 되어 탐색 시간이 길어집니다. 이로 인해 해시맵의 평균 시간 복잡도가 O(1)에서 O(n)까지 나빠질 수 있어 성능 저하가 발생합니다.

개념 정리

해시맵(HashMap)

• 키-값(key-value) 쌍을 저장하는 자료구조로, 내부적으로는 배열과 해시 함수를 활용한다.

• 키를 해시 함수에 입력하여 나온 해시값을 배열의 인덱스로 사용한다.

• 평균적으로 O(1)에 가까운 시간복잡도로 탐색, 삽입, 삭제가 가능하다.

해시 충돌(Hash Collision)

• 서로 다른 두 개 이상의 키가 동일한 해시 버킷 인덱스로 매핑되는 현상

  • 해시 함수는 유한한 범위(배열 크기)의 인덱스를 출력하므로, 서로 다른 키가 같은 인덱스를 가질 가능성이 존재한다.

  • ex. "abc"와 "acb"가 우연히 같은 인덱스로 해시될 수 있다.

• 원인

  1. 해시 함수의 분산 품질이 낮은 경우

     • 해시 함수가 입력값을 고르게 분산시키지 못하면, 특정 해시 버킷에 키가 몰리는 현상이 발생한다.

     • ex. 단순히 문자열의 첫 글자만으로 인덱스를 계산하면, 비슷한 키들(예: "apple", "apricot")이 같은 인덱스로 해시될 가능성이 증가한다.

     • 분산 품질이 좋지 않으면 충돌이 자주 발생하여 O(1)의 성능을 기대하기 어렵다.

  2. 해시맵의 크기(배열 크기)가 작은 경우

     • 해시 함수의 출력값은 보통 배열 크기로 mod 연산되므로, 버킷 수가 적으면 충돌 확률이 자연스럽게 높아진다.

     • ex. 5개의 버킷만 있는 해시맵에 10개의 키를 저장하면 최소한 5개는 충돌이 발생한다.(비둘기집 원리)

  3. 저장된 데이터 수가 많아지는 경우 (= Load Factor 증가)

     • Load Factor = 저장된 요소 수 / 배열 크기

     • Load Factor 비율이 높아지면 해시 버킷 당 평균 엔트리 수가 많아져 충돌 가능성이 상승한다.

     • 참고로 Java의 HashMap은 기본적으로 Load Factor가 0.75를 넘으면 자동으로 resizing(버킷 수 2배 증가)을 수행하여 충돌을 완화한다.

     • ex. 16개 버킷에 16개 이상의 키가 들어가면 평균적으로 버킷당 1개 이상 저장되므로, 충돌 가능성이 증가한다.

충돌 해결 방식

해시 충돌이 발생했을 때 데이터를 어떻게 저장하고 검색할지를 결정하는 방식으로, 대표적으로 체이닝(Chaining) 과 오픈 어드레싱(Open Addressing) 방식이 있다.

방식	설명	시간 복잡도 영향
체이닝 (Chaining)	동일 해시 인덱스에 여러 값을 저장할 수 있도록, 각 버킷을 연결 리스트나 트리 구조로 구현	평균 O(1), 최악 O(n)
오픈 어드레싱 (Open Addressing)	충돌 시 해당 버킷이 아닌 다른 빈 버킷을 찾아 데이터를 저장 (선형 탐사, 이차 탐사, 이중 해싱 등)	충돌이 많을수록 탐색/삽입 시간 증가 (최악 O(n))

체이닝 (Chaining)

• 구조: 해시 버킷 배열의 각 요소가 연결 리스트(또는 트리)의 헤드 포인터 역할을 한다.

• 동작: 충돌이 발생하면 해당 인덱스의 리스트에 노드를 추가한다.

• Java의 HashMap은 기본적으로 체이닝을 사용하며, 동일 인덱스에 8개 이상의 노드가 존재할 경우 이진 트리로 전환한다.

장점

• 구현이 간단하고 삭제가 용이하다.

• 해시 테이블이 꽉 차더라도 삽입이 가능하다. (배열 크기와 무관하게 리스트에 추가)

단점

• 연결 리스트가 길어질수록 탐색 속도가 저하된다.

• 포인터를 위한 추가 메모리 사용이 필요하다.

시간 복잡도

• 평균: O(1) (충돌 적을 때)

• 최악: O(n) (모든 키가 한 버킷에 몰릴 경우)

오픈 어드레싱 (Open Addressing)

• 구조: 해시 테이블 자체만을 사용하고, 버킷 하나에 하나의 엔트리만 저장한다.

• 동작: 충돌이 발생하면 다음 버킷들을 차례로 확인하여 빈 공간을 찾아 저장한다.

• 대표적 방법

  • 선형 탐사 (Linear Probing): 한 칸씩 순차적으로 탐색

  • 이차 탐사 (Quadratic Probing): 거리 증가해가며 탐색

  • 이중 해싱 (Double Hashing): 다른 해시 함수를 사용해 거리 계산

장점

• 데이터가 테이블 내부에만 존재한다. → 캐시 친화적

• 포인터가 필요 없어 메모리 사용량이 적다.

단점

• 삭제가 어렵고, 삭제된 버킷에 대한 처리가 필요하다.

• 충돌이 많을수록 성능이 급격히 저하된다. (탐색 길어짐)

시간 복잡도

• 평균: O(1) (충돌 적을 때)

• 최악: O(n) (빈 버킷 찾기 어려운 경우)

성능에 미치는 영향

• 충돌이 많아질수록 각 연산(삽입, 검색, 삭제)의 성능이 저하될 수 있다.

• 평균 O(1)에서 최악의 경우 O(n)까지 느려질 수 있다.

• 해시맵의 **load factor(적재율)**를 적절히 관리하고, 필요 시 resize가 필요하다.

꼬리 질문

1. Java의 HashMap에서 해시 충돌이 심할 경우 어떤 방식으로 성능 저하를 완화하나요? Java 8 이상부터는 해시 충돌이 심할 경우, 체이닝 방식으로 연결된 LinkedList를 일정 기준 이상이 되면 자동으로 Red-Black Tree로 변환합니다. 이로 인해 최악 시간 복잡도가 O(n)에서 O(log n)으로 개선되어, 충돌이 심한 상황에서도 성능 저하를 줄일 수 있습니다.

2. 대량의 데이터를 다룰 때 HashMap보다 적합한 자료구조는 어떤 것이 있을까요? 대량의 데이터나 범위 기반 탐색이 필요한 경우에는 HashMap보다 TreeMap이 더 적합할 수 있습니다. TreeMap은 내부적으로 Red-Black Tree를 사용해 정렬된 순서로 데이터를 저장하며, 범위 검색이나 순차 탐색에 유리합니다. 또한 멀티스레드 환경에서는 ConcurrentHashMap을 사용하면 성능과 안정성을 모두 확보할 수 있습니다.

3. Java의 HashMap에서는 충돌이 많아질 때 어떻게 처리하면 좋을까요? 충돌이 많다면 초기 용량(capacity)과 로드 팩터(load factor)를 조정해 리사이징이 덜 일어나도록 하거나, HashMap 대신 TreeMap 또는 구간 분할이 쉬운 다른 자료구조로 바꾸는 방법이 있습니다.