알고리즘에서 '해시 테이블(Hash Table)'의 평균 시간 복잡도와 충돌 해결 방법으로 올바른 것은?

보통 freeCodeCamp

보기 및 정답

A 검색, 삽입, 삭제의 평균이 O(1)이며, 충돌은 체이닝(Chaining)이나 오픈 어드레싱(Open Addressing)으로 해결한다

B 검색, 삽입, 삭제 연산의 시간 복잡도가 항상 O(n)이며, 완벽한 해시 함수를 사용하면 충돌이 절대로 발생하지 않는다

C 삽입 연산만 O(1)이고 검색과 삭제 연산은 지원하지 않으며, 한 번 저장된 데이터는 읽기 전용으로만 사용할 수 있는 쓰기 불가 자료구조이다

D 해시 충돌이 발생하면 기존에 저장되어 있던 데이터가 자동으로 삭제되며, 새로운 데이터로 완전히 덮어쓰는 방식으로 동작한다

해시 테이블은 해시 함수로 키를 인덱스로 변환하여 O(1) 평균 시간에 데이터를 접근합니다. 다른 키가 같은 인덱스로 매핑되는 충돌은 체이닝(연결 리스트 사용)이나 오픈 어드레싱(빈 슬롯 탐색)으로 해결합니다. 최악의 경우 O(n)이 될 수 있습니다.

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

로그인