FNV-1a 해시 기반 O(1) 평균 시간 복잡도를 갖는 C 언어 Set 구현

Context

중복 없는 고유 요소 저장을 위해 데이터 구조 설계 필요. 정렬되지 않은 집합 특성상 빠른 탐색과 삽입 성능이 핵심 요구사항임.

Technical Solution

• 평균 O(1)의 시간 복잡도 달성을 위한 Hashtable 기반 아키텍처 채택
• 해시 충돌 해결을 위해 버킷당 Linked List를 연결하는 Chaining 기법 적용
• 데이터 분포의 균일성을 확보하기 위한 32-bit FNV-1a Hash 함수 활용
• 메모리 효율성을 고려한 malloc 기반 동적 노드 할당 및 free를 통한 자원 해제
• 중복 데이터 삽입 방지를 위해 삽입 전 기존 Linked List 전체를 탐색하는 검증 로직 구현
• 고정 크기 배열(SET_LIMIT_SIZE 1000) 사용으로 단순한 인덱스 매핑 구조 설계