Hash Table 기반 Set 도입을 통한 O(1) 시간 복잡도의 검색 성능 달성

Context

데이터 저장 시 순서 보장과 중복 허용이 특징인 Array 구조 사용. 데이터 규모 증가에 따라 contains() 호출 시 전체 요소를 스캔하는 Linear Search 방식의 성능 저하 발생.

Technical Solution

• Hash Table 기반의 Set 자료구조 채택을 통한 데이터 관리 방식 변경
• 순서 보장 제약을 제거하여 데이터의 즉각적인 위치 탐색이 가능한 구조 설계
• 내부적인 해싱 메커니즘을 활용해 데이터 규모와 무관한 상수 시간 복잡도 구현
• insert() 메서드의 반환 값을 활용한 중복 데이터 삽입 여부의 즉각적인 판별 로직 적용
• sorted() 메서드를 통해 필요 시에만 Set의 요소를 Array로 변환하여 정렬 순서 확보

Impact

10,000개 이상의 대규모 데이터셋에서 Array의 최대 10,000회 검색 작업을 단 1회의 즉각적인 조회를 통해 해결하는 성능 개선 달성.

Key Takeaway

데이터의 순서보다 고유성과 검색 속도가 우선되는 도메인에서는 선형 구조보다 해시 기반의 집합 구조를 선택하는 것이 시스템 효율성을 극대화하는 설계 원칙임.