해시 테이블과 충돌 해결
해시 테이블 (Hash Table)과 충돌 해결
해시 테이블(Hash Table)은 키(Key)와 값(Value)을 하나의 쌍으로 저장하는 자료구조로, 해시 함수(Hash Function)를 사용하여 키를 배열의 인덱스(해시 값)로 변환하고, 이 인덱스를 통해 데이터에 평균적으로 O(1)의 매우 빠른 속도로 접근할 수 있습니다.
🔑 해시 테이블의 동작 원리
1. 키(Key)를 해시 함수에 입력하여 해시 코드(Hash Code)를 얻습니다. 2. 해시 코드를 배열(버킷, Bucket)의 인덱스로 변환합니다. (보통 `해시코드 % 배열의 크기` 연산 사용) 3. 해당 인덱스에 값(Value)을 저장합니다.
- 해시 함수 (Hash Function) : 임의의 길이의 데이터를 고정된 길이의 데이터(해시)로 매핑하는 함수입니다. 좋은 해시 함수는 키를 해시 테이블의 인덱스 공간에 고르게 분산시켜야 합니다.
- 시간 복잡도 : 충돌이 없는 이상적인 경우, 데이터 삽입, 삭제, 조회가 모두 평균적으로 O(1)의 시간 복잡도를 가집니다.
💥 해시 충돌 (Hash Collision)
- 정의 : 서로 다른 두 개 이상의 키가 해시 함수를 통해 동일한 인덱스로 매핑되는 현상입니다.
- 필연성 : 아무리 좋은 해시 함수를 사용하더라도, 입력값의 범위(키의 집합)가 출력값의 범위(해시 테이블의 크기)보다 크기 때문에 '비둘기집 원리'에 의해 충돌은 필연적으로 발생합니다.
- 문제점 : 해시 충돌이 잦아지면, 특정 인덱스에 데이터가 집중되어 해시 테이블의 성능이 저하되고, 최악의 경우 O(n)까지 성능이 떨어질 수 있습니다.
🛠️ 충돌 해결 방법 (Collision Resolution)
- 체이닝 (Chaining / Separate Chaining)
> * '방식': 동일한 인덱스로 해싱되는 키-값 쌍들을 연결 리스트(Linked List)나 트리(Tree)로 연결하여 저장합니다. > * '장점': 구현이 비교적 간단하고, 데이터가 많아져도 성능 저하가 완만합니다. > * '단점': 연결 리스트를 위한 추가적인 메모리 공간이 필요합니다. > * '참고': Java의 `HashMap`은 체이닝 방식을 사용하며, 하나의 버킷에 저장된 데이터 개수가 8개를 넘으면 연결 리스트를 레드-블랙 트리 구조로 전환하여 성능을 최적화합니다.
- 개방 주소법 (Open Addressing)
> * '방식': 충돌이 발생하면, 미리 정해진 규칙에 따라 다른 비어있는 버킷을 찾아 데이터를 저장합니다. > * '종류': > > * 선형 탐사 (Linear Probing): 현재 버킷의 다음 버킷부터 순차적으로 탐색하여 빈 공간을 찾습니다. (특정 영역에 데이터가 몰리는 '클러스터링' 현상에 취약) > > * 제곱 탐사 (Quadratic Probing): 탐사 폭을 제곱수로 늘려가며 빈 공간을 찾습니다. > > * 이중 해싱 (Double Hashing): 두 개의 해시 함수를 사용하여, 충돌 시 탐사할 이동 폭을 결정합니다. 클러스터링 문제에 가장 강합니다.
💡 개발자 핵심 Point
- 해시 테이블은 빠른 속도를 장점으로 하여, 연관 배열(associative arrays), 데이터베이스 인덱싱, 캐시 구현 등 다양한 곳에서 활용됩니다.
- 좋은 해시 테이블 성능을 위해서는 데이터의 분포를 최대한 고르게 만드는 '좋은 해시 함수'를 사용하는 것이 매우 중요합니다.
- 리사이징(Resizing): 해시 테이블에 데이터가 일정 수준 이상으로 차게 되면(보통 Load Factor가 0.75 이상), 충돌이 잦아져 성능이 저하됩니다. 이를 방지하기 위해, 더 큰 크기의 새 해시 테이블을 만들고 기존 데이터를 모두 다시 해싱하여 옮기는 '리사이징' 과정이 필요합니다.
