View
개요
대규모 데이터셋에서 원하는 정보를 효율적으로 저장하고 검색하는 것은 시스템 성능에 매우 중요하다.
가령, 웹사이트에 사용자가 로그인했을 때 서버는 해당 사용자의 로그인 상태나 장바구니 정보 같은 걸 기억해야 한다고 가정해보자.
사용자가 페이지를 이동할 때마다 이 정보를 빠르게 찾아야 하는데,
배열이나 연결 리스트를 이용한 순차 탐색은 데이터 크기에 비례하여 탐색 시간(O(n))이 증가하며, 이진 탐색 트리(O(log n))도 한계가 있다.
만약 로그인 시 발급된 고유한 세션ID(Key)에 해당하는 사용자의 정보(사용자 객체, 장바구니 정보 등)를 값(Value)로 저장한다면, 사용자의 요청에 세션ID로 바로 조회해서 사용자 정보를 순식간에 꺼내 쓸 수 있을 것이다.
이를 통해 데이터 양과 관계없이 거의 일정한 시간(평균 O(1)) 안에 원하는 데이터를 찾아낼 수 있는데,
이 놀라운 성능을 제공하는 핵심 자료구조가 해시맵(HashMap) 또는 해시 테이블(Hash Table)이다.
많은 개발자(본인 포함)가 편리함과 속도 때문에 사용하지만, 내부 메커니즘을 정확히 이해하는 것은 중요하다.
단순히 "빠르다"는 이해를 넘어, 해시맵의 심장부를 들여다보는 것은 자료구조에 대한 깊은 이해를 제공하고, 성능 최적화와 문제 해결 능력을 향상시킨다.
이 글에서는 해시맵이 키(Key)를 통해 값을 어떻게 빠르게 찾아내는지, 핵심 원리인 해시 함수(Hash Function)와 버킷 배열(Bucket Array)의 역할부터 분석해보려 한다.
필연적으로 발생하는 해시 충돌(Hash Collision) 문제와 이를 해결하기 위한 전략(Separate Chaining, Open Addressing), 그리고 최적 성능 유지를 위한 동적 리사이징(Resizing) 과정까지 심층적으로 다루려 한다.
키 객체의 불변성 요구 조건, 동시성 문제 등 실무 고려 사항까지 짚어보며, 해시맵이라는 강력한 도구를 효과적으로 활용하기 위한 기초를 다져보려 한다.
핵심 구성 요소
해시맵은 크게 세 가지 핵심 요소로 나눌 수 있다.
바로 키-값 쌍(Key-Value Pair), 해시 함수(Hash Function), 그리고 버킷 배열(Bucket Array)이다.
1. 데이터를 담는 단위: 키-값 쌍 (Key-Value Pair / Entry)
해시맵은 기본적으로 데이터를 키(Key) 와 값(Value) 이라는 하나의 쌍으로 묶어서 저장한다. 마치 사전에서 단어(키)를 찾으면 그 뜻(값)이 나오는 것과 같다.
- 키(Key): 저장된 값을 찾아내기 위한 고유한 식별자다. 해시맵에서 키는 중복될 수 없다. 어떤 값을 찾고 싶다면, 반드시 그 값에 해당하는 유일한 키를 사용해야 한다.
- 값(Value): 키를 통해 최종적으로 얻고 싶은 실제 데이터다. 값은 중복되어도 상관없다.
- 키의 역할: 이 키가 바로 해시 함수를 통해 데이터가 저장될 위치를 결정하는 재료가 된다. 따라서 해시맵에 저장된 이후에는 키로 사용된 객체의 상태가 변하지 않는 것이 매우 중요하다. 만약 키 객체의 상태가 변해서 `hashCode()` 결과나 `equals()` 비교 결과가 달라진다면, 나중에 해당 데이터를 찾지 못하는 심각한 문제가 발생할 수 있다.
보통 이 키-값 한 쌍을 엔트리(Entry) 라고 부르기도 한다. 해시맵 내부에 데이터가 저장될 때는 이 엔트리 단위로 관리된다고 생각하면 된다.
2. 해시 함수 (Hash Function)
해시 함수는 해시맵의 핵심 엔진이다. 임의의 길이와 형태를 가진 키(Key)를 입력받아서, 고정된 길이의 정수 값, 즉 '해시값(Hash Code)'으로 변환해주는 함수다.
- 목적: 키를 버킷 배열의 특정 위치(인덱스)와 연결시키는 다리 역할을 한다. 어떤 키든 해시 함수를 통과하면 숫자로 된 해시값이 나오므로, 이 숫자를 이용해 배열의 인덱스를 계산할 수 있다.
- 이상적인 해시 함수의 조건:
- 결정성(Deterministic): 동일한 키에 대해서는 항상 동일한 해시값을 반환해야 한다. 이게 보장되지 않으면 데이터를 저장하고 찾는 것 자체가 불가능하다.
- 균등 분포(Uniform Distribution): 키들을 가능한 한 버킷 배열의 모든 인덱스에 골고루 분산시켜야 한다. 특정 인덱스에 데이터가 쏠리면(충돌 증가) 해시맵의 성능이 급격히 저하된다.
- 효율성(Efficiency): 해시값을 계산하는 과정 자체가 빨라야 한다. 해시값 계산이 오래 걸리면 해시맵의 O(1) 성능 목표가 무의미해진다.
- `hashCode()` 와 `equals()` 규약: Java 같은 객체 지향 언어에서는 이 두 메서드가 해시맵 동작에 결정적인 역할을 한다.
- 규약 1: `a.equals(b)` 가 `true` 이면, `a.hashCode()`와 `b.hashCode()`는 반드시 같아야 한다. (같은 객체는 같은 버킷 인덱스를 가져야 찾을 수 있다)
- 규약 2: `a.equals(b)`가 `false`라고 해서 `a.hashCode()`와 `b.hashCode()`가 반드시 달라야 하는 것은 아니다. 하지만 다르면 충돌이 줄어 성능에 유리하다.
- 이 규약이 깨진 객체를 키로 사용하면 해시맵은 제대로 동작하지 않는다.
좋은 해시 함수를 만드는 것은 쉽지 않지만, 대부분의 프로그래밍 언어는 기본 타입(정수, 문자열 등)에 대해 잘 구현된 해시 함수를 기본 제공하므로 너무 걱정할 필요는 없다.
3. 데이터의 집: 버킷 배열 (Bucket Array / Table)
해시맵 내부에 실제로 데이터(엔트리)를 저장하는 공간이다.
그냥 평범한 배열(Array) 구조라고 생각하면 된다. 이 배열의 각 칸 하나하나를 버킷(Bucket) 또는 슬롯(Slot) 이라고 부른다.
중요한 것은, 인덱스(Index)는 해시코드를 통해 계산된 배열의 위치 번호(주소)이고, 버킷은 그 위치에 있는 실제 저장 공간 자체를 의미한다는 점이다.
즉, 인덱스는 버킷을 가리키는 주소값이다.이론적으로는 하나의 버킷에 하나의 엔트리가 저장되는 것이 이상적이지만, 서로 다른 키가 우연히 같은 인덱스를 가리키는 '해시 충돌'이 발생하면 하나의 버킷에 여러 개의 엔트리가 저장될 수도 있다.
- 역할: 해시 함수를 통해 계산된 해시값을 사용하여, 엔트리가 저장될 구체적인 위치(인덱스) 를 제공한다.
- 인덱스 계산: 기본적으로 `index = hashCode % 배열크기` 공식을 사용한다. 즉, 키의 해시값을 버킷 배열의 크기로 나눈 나머지가 해당 키-값 쌍이 저장될 버킷의 인덱스가 된다. 많은 구현체에서는 이 해시코드가 음수이거나 특정 범위에 쏠리는 것을 방지하기 위해 보조 해시 함수를 적용하거나, 비트 연산을 통해 해시값을 한번 더 가공하기도 한다.
- 배열 크기(Capacity)와 성능:
- 배열 크기가 너무 작으면 서로 다른 키가 같은 인덱스를 가리킬 확률(충돌)이 높아져 성능이 떨어진다.
- 배열 크기가 너무 크면 사용되지 않는 버킷이 많아져 메모리가 낭비된다.
- 그래서 해시맵은 데이터 양에 따라 동적으로 이 배열의 크기를 조절한다 (리사이징).
- (최적화 팁) 2의 거듭제곱 크기: 많은 해시맵 구현체(대표적으로 Java의 `HashMap`)는 성능 최적화를 위해 내부 배열의 크기를 항상 2의 거듭제곱(예: 16, 32, 64...) 으로 유지한다. 이렇게 하면 모듈로 연산(`%`) 대신 훨씬 빠른 비트 AND 연산(`&`)을 사용하여 인덱스를 계산할 수 있기 때문이다 (`index = hashCode & (배열크기 - 1)`).
결국 해시맵은 키를 해시 함수로 돌려 숫자로 바꾸고, 그 숫자를 이용해 버킷 배열의 특정 칸(인덱스)에 값을 저장하거나 찾아오는 방식으로 동작하는 것이다. 이 세 가지 요소가 어떻게 상호작용하는지 이해하는 것이 핵심이다.
핵심 동작
그럼 이제 위 3가지 핵심 요소로 HashMap이 어떻게 동작하는지를 알아보자.
핵심 동작은 크게 HashMap에 자료를 어떻게 저장하고(Put), 어떻게 검색하는지(Get), 어떻게 삭제하는지(Remove)를 정의할 수 있다.
저장(Put)
- HashMap은 버킷(Bucket)으로 이루어진 배열을 저장한다.
- Key-Value 쌍 저장 요청이 들어오면 Key 값을 해시 함수를 적용시켜 얻은 해시코드를 이용해 버킷 배열의 인덱스를 계산한다.
- 계산된 해당 인덱스에 해당하는 버킷이 비어있다면 새로운 엔트리(Key-Value 쌍)를 해당 버킷에 저장, 이미 버킷에 엔트리가 저장돼있다면 해시 충돌이 발생한다(해시 충돌 부분에서 다루겠다).
검색(Get) / 삭제(Remove)
저장(Put)과 핵심원리가 비슷하다.
- get(key) 혹은 remove(key) 요청이 오면, 해당 키의 해시코드를 계산한다.
- 해시코드를 이용해 버킷 배열의 인덱스를 계산한다.
- 해당 버킷에 엔트리가 있다면, 요청된 키와 `equals()`가 true인 엔트리의 값을 반환하거나 삭제한다(충돌 시에는 해시 충돌 부분에서 다루겠다).
이처럼 Key를 통해 바로 데이터가 저장될 위치(버킷 인덱스)를 계산할 수 있기 때문에, 해시맵은 평균적으로 O(1) 성능을 낼 수 있는 것이다.
해시 충돌
앞서 해시맵은 키를 해시 함수로 돌려 나온 해시코드를 이용해 버킷 인덱스를 계산한다고 했다.
모든 키가 서로 다른 인덱스에 딱딱 매핑되면 참 좋겠지만... 현실은 그렇지 않다.
해시 충돌이란, 서로 다른 키(Key)를 가졌음에도 불구하고, 해시 함수와 인덱스 계산을 거친 결과 우연히 동일한 버킷 인덱스를 할당받게 되는 현상을 말한다.
마치 여러 사람이 호텔 방을 예약했는데, 호텔 직원의 실수나 우연으로 같은 방 번호를 배정받은 상황과 비슷하다.
왜 충돌은 피할 수 없는가?
크게 두 가지 이유 때문이다.
- 비둘기집 원리 (Pigeonhole Principle)
- 'n+1' 마리의 비둘기를 'n' 개의 비둘기집에 넣으려면, 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어갈 수밖에 없다는 원리이다.
- 해시맵에 적용시키면, 저장하려는 키의 가짓수(비둘기)는 무한대에 가깝다. 그러나 버킷 배열의 칸 수(비둘기집)는 유한하다.
- 아무리 배열 크기를 크게 잡아도, 언젠가는 서로 다른 키가 같은 버킷 인덱스를 공유하게 된다.
- 해시 함수의 한계
- 이상적인 해시 함수는 키들을 모든 버킷에 완벽하게 균등하게 분배해야 한다. 그러나 실제 세상에서 그런 해시 함수가 있을까?
- 아무리 잘 만든 해시 함수라도 키 패턴이나 데이터 분포에 따라서 특정 인덱스에 값이 쏠리는 현상이 발생할 수 있다(형편없는 해시 함수는 이 문제가 더욱 심각해진다고 보면 된다).
따라서 해시맵을 사용하는 한, 해시 충돌은 필연적이므로 완전한 해결보단 성능 저하를 최소화하는 것이 중요하다.
왜 충돌이 문제일까?
해시맵을 쓰고자 하는 근본 목적인 평균 O(1) 시간 복잡도가 깨지기 때문이다.
어떤 버킷 인덱스에 2개 이상의 키-값 쌍(엔트리)이 저장되어있다고 생각해보자.
- 즉시 접근 불가
- 더이상 해당 인덱스만으로는 내가 원하는 정확한 값을 바로 꺼낼 수 없게 된다.
- 추가 탐색 필요
- 버킷 안에 묶인 엔트리들을 하나씩 비교하면서 내가 찾으려는 키와 `equals()`로 일치하는 녀석을 찾아야 한다.
- 성능 저하
- 버킷에 엔트리가 2개가 아닌 10개, 100개 등 길게 연결될수록 당연하게도 이 추가 탐색 시간은 길어진다.
- 최악의 경우 모든 키가 하나의 버킷에 충돌한다면, 이젠 연결 리스트처럼 동작하게 된다.
충돌 해결 전략
해시 충돌은 피할 수 없다.
그러나 잘 관리하면 성능 저하는 최소화할 수 있다.
해시 충돌을 해결하는 대표적인 방법으로는 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing)이 있다.
분리 연결법(Separate Chaining)
가장 널리 쓰이고 직관적인 방법이다.
충돌이 발생한 데이터를 별도의 공간에 연결해 관리하는 방식이다.
- 동작 방식
- 각 버킷(배열의 칸)이 단순히 값 하나만 저장하는 게 아니라, 해당 버킷 인덱스로 매핑된 데이터(엔트리)들의 리스트(List) 또는 트리(Tree)를 가리키도록 한다.
- 충돌이 발생하면 (즉, 어떤 버킷에 데이터를 넣으려는데 이미 다른 데이터가 있다면), 새로운 데이터를 그 버킷이 가리키는 리스트나 트리의 끝에 추가한다.
- 데이터를 찾을 때는(Get), 먼저 키의 해시코드로 버킷 인덱스를 계산하고, 해당 버킷이 가리키는 리스트나 트리를 처음부터 순회하면서 `equals()` 로 키를 비교하여 원하는 데이터를 찾는다. 삭제(Remove)도 비슷하게 찾아서 제거한다.
- 장점
- 구현이 간단하고 직관적이다.
- 데이터가 아무리 많아져도 이론상 계속 데이터 추가가 가능하다(성능은 물론 보장 못한다).
- 데이터 삭제가 간편하다(연결된 자료구조에서 해당 노드만 제거하면 된다).
- 단점
- 각 노드를 저장하기 위해 결국 추가적인 메모리 공간이 필요하다.
- 하나의 버킷에 데이터가 몰리는 경우를 제대로 해결해주진 못한다(O(n)에 가까워진다).
- 데이터들이 메모리상에서 흩어져 있을 수도 있기에 캐시 효율성이 떨어질 수 있다.
- Java `HashMap`의 최적화
- Java 8 버전부터 `HashMap`은 이 분리 연결법 방식을 사용하는데, 굉장히 중요한 최적화를 도입했다!
- 바로 한 버킷에 연결된 엔트리가 특정 임계치(기본값은 8개)를 넘기면, 성능 향상을 위해 연결 리스트 구조를 레드-블랙 트리로 전환해, 최악의 경우에도 시간복잡도는 O(log n)이 된다.
- 그리고 엔트리 개수가 줄어들면 다시 연결 리스트 구조로 돌아오게 된다.
개방 주소법 (Open Addressing)
해시 충돌이 발생했을 때 데이터를 별도의 리스트에 저장하지 않고 버킷 배열 내의 다른 비어있는 버킷을 찾아 거기에 저장한다.
즉 모든 데이터가 어떻게든 버킷 배열 안에 들어간다고 보면 되겠다.
- 동작 방식
- 키의 해시코드로 버킷 인덱스를 계산한다.
- 해당 버킷을 찾아간다.
- 버킷이 비어있다면 그 자리에 데이터를 저장한다.
- 버킷에 이미 다른 데이터가 있다면, 미리 정해진 빈 버킷을 찾는 규칙에 따라 다음 후보 버킷을 찾아 이동한다.
- 이동한 버킷도 차 있다면 빈 버킷이 있을 때까지 반복한다.
- 데이터를 찾을 때(Get)도 저장할 때와 동일한 순서로 버킷을 확인하며 키를 비교한다.
- 삭제(Remove)는 조금 더 복잡한데, 그냥 데이터를 지워버리면 나중에 다른 데이터를 찾을 때 중간에 끊길 수 있기 때문에, 삭제된 자리라는 표시를 남겨둔다.
- 탐사 전략
- 선형 탐사(Linear Probing): 가장 간단한 방식이다. 충돌 시 바로 다음 칸(`+1`), 그 다음 칸(`+2`)... 순서대로 빈 칸을 찾는다. 구현은 쉬울 수 있으나 데이터들이 연속된 덩어리로 뭉치는 'Primary Clustering' 현상이 발생하기 쉬워 특정 영역의 충돌이 심해질 수 있다.
- 제곱 탐사(Quadratic Probing): 충돌시 다음 칸을 `+1^2`, `+2^2`, `+3^2`... 만큼 떨어진 칸을 순서대로 조사한다. Primary Clustering 문제는 완화되지만, 시작 위치가 같으면 탐사 순서도 같아지는 'Secondary Clustering' 문제가 발생할 수 있다.
- 이중 해싱(Double Hashing): 충돌 시 다음 칸을 찾는 간격(step)을 또 다른 해시 함수를 이용해 키마다 다르게 결정한다. 예를 들면 `(기존해시 + i * 두번째 해시(키)) % 배열크기`와 같은 식이다. 위 클러스터링 문제들을 완화해주지만... 추가되는 해시 함수도 좋은 해시 함수여야 하며, 계산 또한 복잡하다.
- 장점
- 모든 데이터가 버킷 배열 안에 있기 때문에 추가적인 메모리가 필요없다.
- 선형 탐사의 경우 데이터들이 같은 메모리 상에 위치할 확률이 높기 때문에, 캐시 효율성이 좋을 수 있다.
- 단점
- 배열이 점점 차기 시작하면(로드 팩터가 높아지면) 빈 버킷을 찾기 위한 탐사 횟수가 급격히 증가해 성능이 크게 저하된다. 그래서 보통 개방 주소법(Open Addressing)은 로드 팩터 임계치를 분리 연결법(Separate Chaining)보다 낮게 설정하는 경우가 많다.
- 삭제 표시 관리가 따로 필요하다.
- 클러스터링 문제가 발생하면 해시 테이블의 의미가 퇴색된다.
어떤 방식을 선택할까?
- 분리 연결법(Separate Chaining)
- 구현이 쉽다.
- 로드 팩터가 높아져도 비교적 안정적인 성능이 유지된다.
- 삭제가 간편하다.
- 메모리 사용량이 조금 더 많고 캐시 효율이 떨어질 수 있다.
- Java `HashMap`의 선택
- 개방 주소법(Open Addressing)
- 메모리를 더 효율적으로 사용한다.
- 캐시 친화적이다.
- 로드 팩터가 높아지면 성능이 급격히 나빠진다.
- 삭제 구현이 복잡하다.
- Python `dict`, C++ `unordered_map` 등 일부 구현체가 사용한다.
지금까지 빠른 시간 복잡도를 자랑하는 자료구조 중 하나인 해시맵의 내부를 깊숙이 들여다보았다.
키-값 쌍을 저장하는 기본 단위부터 시작해, 키를 배열 인덱스로 변환하는 핵심 엔진인 해시 함수, 그리고 실제 데이터가 거주하는 버킷 배열까지, 해시맵의 뼈대를 살펴보았다.
또한 데이터 저장, 검색, 삭제의 핵심 동작들이 이 구성 요소들을 기반으로 어떻게 이루어지는지도 확인했다.
더 나아가, 해시맵의 성능에 큰 영향을 미치는 필연적인 과제인 해시 충돌 문제에 주목했다.
충돌이 왜 발생할 수밖에 없는지, 충돌이 왜 문제인지,
그리고 충돌을 해결하는 두 가지 접근법인 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing)의 상세한 메커니즘과 각각의 장단점을 분석했다.
그러나 이 전략만으로는 사실 해시맵의 모든 성능 문제가 해결되지 않는다.
근본적으로 버킷 배열의 용량 대비 저장된 데이터의 양, 즉 로드 팩터가 높아지면 충돌 발생 빈도 자체가 증가해 성능은 저하한다.
해시맵은 이 근본적인 도전에 어떻게 맞서면서, O(1)에 가까운 성능을 유지하는 것인지 궁금해질 수밖에 없다.
다음 글에서는 이 질문에 대한 답이자 해시맵 성능 유지의 또 다른 핵심인 리사이징/리해싱, 그리고 기타 고려 사항들에 대해 다루겠다.
