C 언어로 해시 테이블 직접 구현하기: 선형 탐색 기반 오픈 어드레싱

핵심 기술

이 글은 C 언어를 사용하여 효율적인 데이터 구조인 해시 테이블을 직접 구현하는 방법을 상세히 안내합니다. 특히, 키-값 쌍을 저장하는 구조체 정의부터 시작하여 문자열 해시 함수, 충돌 해결을 위한 선형 탐색(Linear Probing) 기반의 오픈 어드레싱 기법, 그리고 삽입(insert), 탐색(get), 삭제(delete) 연산까지 전 과정을 코드로 설명합니다.

기술적 세부사항

• 데이터 구조 설계: HashItem 구조체를 정의하여 key(문자열 포인터), value(정수), isOccupied(슬롯 상태: 0-빈칸, 1-사용 중, -1-삭제됨)를 관리합니다.
• 해시 함수: unsigned int hash(const char* key) 함수는 입력된 문자열에 대해 간단한 곱셈 및 덧셈 연산을 수행하고 테이블 크기로 나눈 나머지를 반환하여 인덱스를 생성합니다.
• 삽입 로직 (선형 탐색): 해시 인덱스에서 충돌이 발생하면, 다음 빈 슬롯이나 동일한 키를 찾을 때까지 테이블을 순차적으로 탐색(index = (index + 1) % TABLE_SIZE)합니다. 테이블이 가득 찼을 경우 오류 메시지를 출력합니다.
• 탐색 로직 (선형 탐색): 삽입과 유사하게 해시 인덱스부터 시작하여, 슬롯이 비어있거나(isOccupied == 0) 해당 키와 일치하는 경우(isOccupied == 1 && strcmp(...) == 0) 탐색을 종료합니다. 삭제된 슬롯(-1)은 탐색을 계속 진행합니다.
• 삭제 로직: 해당 키를 찾으면, 메모리 해제(free()) 후 isOccupied 상태를 -1(삭제됨)로 변경하여 '툼스톤(tombstone)' 마커로 표시합니다. 이는 삭제된 슬롯 이후에 있는 데이터의 탐색 경로가 끊어지지 않도록 합니다.
• 메모리 관리: strdup()을 사용하여 키 문자열을 힙에 복사하고, 삭제 시 free()를 통해 메모리를 해제하는 등 수동 메모리 관리가 이루어집니다.

개발 임팩트

이 콘텐츠를 통해 개발자는 해시 테이블의 내부 동작 원리를 명확하게 이해할 수 있습니다. 실제 코드 구현을 통해 추상적인 개념을 구체화하고, 충돌 해결 전략의 중요성과 장단점을 파악하며, C 언어에서의 메모리 관리 기법을 익힐 수 있습니다. 이는 알고리즘 및 자료구조에 대한 실질적인 이해도를 높이고, 성능이 중요한 애플리케이션 개발에 직접적으로 활용될 수 있는 실무적 지식을 제공합니다.

커뮤니티 반응

(원문에 커뮤니티 반응에 대한 구체적인 언급이 없어 생략합니다.)