인프런 커뮤니티 질문&답변
작성한 질문수
2번째 복습 스터디📖 를 진행하고 스터디원분들과 나눈 질문들 입니다.(자료구조와 알고리즘)
작성
·
49
·
수정됨
1
해시테이블의 시간복잡도는 해시 함수가 무엇이냐에 영향을 받을까요?
강의 내용에서는 해시 테이블은 키만 알면 조회, 삽입, 수정, 삭제까지 O(1)성능을 가진다고 했습니다. 해시 테이블을 만들 때 해시함수가 중요한 역할을 한다고 하는데 그렇다면 해시테이블의 시간복잡도는 해시 함수 종류에 영향을 받아 결정되는 것인지 궁금합니다.
답변 2
1
1
안녕하세요, 인프런 AI 인턴입니다.
rhkdtjd_12님께서 문의하신 해시테이블의 시간 복잡도와 해시 함수의 관련성에 대해 답변드리겠습니다.
해시 테이블의 시간 복잡도는 기본적으로 조회, 삽입, 수정, 삭제의 평균 시간 복잡도가 O(1)입니다. 그러나 이는 이상적인 상황을 가정한 것이며, 해시 함수의 선택에 대단히 큰 영향을 받습니다.
해시 함수가 좋은 품질이라면 데이터가 테이블 내에 균등하게 분포되어 충돌이 적게 발생하고, 이는 O(1) 시간 복잡도를 유지하는 데에 도움을 줍니다. 반면에, 해시 함수가 비효율적이라면 충돌이 빈번하게 발생하여 데이터를 처리하기 위한 시간 복잡도가 O(n)까지 올라갈 수도 있습니다.
따라서 해시 함수를 잘 설계하는 것이 해시 테이블의 성능을 최적화하는 데 매우 중요합니다. 충돌을 최소화하고 데이터를 효과적으로 분배할 수 있는 해시 함수를 사용하는 것이 바람직합니다.
위와 관련된 이해를 돕기 위한 기존 질문의 답변을 참고해 보세요:
- HashTable set 메서드
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
감사드립니다 감자님!!