O(n) 탐색 한계를 극복한 Hashmap의 O(1) 상수 시간 복잡도 구현 원리

Context

Array 및 String과 같은 순차 구조의 데이터 탐색 시 발생하는 O(n) 시간 복잡도 병목 현상 분석. 데이터 규모 증가에 따라 선형적으로 증가하는 탐색 비용을 제거하기 위한 효율적인 Key-Value 매핑 구조 필요성 대두.

Technical Solution

• Hash Function을 통한 임의의 Key 값을 정수형 Hash Code로 변환하는 매커니즘 설계
• 변환된 Hash Code에 Modulo 연산을 적용하여 고정된 크기의 Bucket 인덱스로 매핑하는 구조 채택
• Hash Collision 해결을 위해 연결 리스트를 활용한 Chaining 또는 빈 슬롯을 찾는 Open Addressing 전략 적용
• Load Factor(요소 수/Bucket 수)가 임계값(통상 0.75) 초과 시 내부 배열 크기를 확장하고 재배치하는 Rehashing 프로세스 수행
• Deterministic, Uniform Distribution, Fast Calculation이라는 세 가지 Hash Function 제약 조건을 통해 O(1) 성능 보장