HashMap: O(n) 최악 사례를 O(log n)으로 개선한 Treeification 구조

Context

Hash Collision 발생 시 LinkedList 기반의 데이터 저장으로 인한 검색 성능 저하 문제 분석. 특히 특정 버킷에 데이터가 집중될 때 발생하는 O(n)의 시간 복잡도가 시스템 병목 지점으로 작용함.

Technical Solution

• Array와 LinkedList의 조합을 기본 구조로 채택하여 빠른 데이터 접근 구현
• (n-1) & hash 비트 연산을 통한 Modulo 연산 대체로 버킷 인덱스 계산 최적화
• Bucket 내 노드 수가 8개를 초과하는 시점에 Red-Black Tree로 변환하는 Treeification 전략 적용
• hashCode()와 equals()의 상호 보완적 설계를 통한 정확한 엔트리 식별 및 Collision 제어
• Load Factor 0.75 기준의 Dynamic Resizing을 통한 해시 분포 최적화 및 Collision 빈도 감소

Impact

• 최악의 경우 검색 시간 복잡도를 O(n)에서 O(log n)으로 단축

Key Takeaway

데이터 구조의 선택은 평균 성능뿐 아니라 최악의 상황(Worst-case)에 대한 방어 기제 설계가 필수적임.