O(1) 조회를 위한 Hash-to-Bucket 매핑 및 Java 8 Treeify 최적화

Context

데이터 검색 시 발생하는 O(n) 선형 탐색의 성능 저하 및 확장성 한계 해결 필요. 단순 리스트나 병렬 배열 구조로는 대규모 데이터셋에서 조회, 중복 확인, 삭제 작업의 비용이 기하급수적으로 증가하는 문제 발생.

Technical Solution

• hashCode()를 통한 Key 값을 정수형 인덱스로 변환하여 특정 Bucket에 즉시 접근하는 O(1) 시간 복잡도 구현
• Hash Collision 발생 시 Linked List 기반의 체이닝 구조를 사용하여 동일 Bucket 내 데이터 관리
• Bucket 내 노드 수가 8개 초과 시 Red-Black Tree로 전환하여 최악의 경우 검색 성능을 O(n)에서 O(log n)으로 개선
• Load Factor 0.75 도달 시 Bucket 크기를 2배로 확장하는 Resizing 메커니즘을 통해 Hash Collision 빈도 제어
• hashCode()와 equals()의 상호 보완적 설계를 통해 객체 식별의 정확성과 비교 연산 비용 최적화