2번째 복습 스터디📖 를 진행하고 스터디원분들과 나눈 질문들 입니다.(자료구조와 알고리즘)
144
138 asked
해시테이블의 시간복잡도는 해시 함수가 무엇이냐에 영향을 받을까요?
강의 내용에서는 해시 테이블은 키만 알면 조회, 삽입, 수정, 삭제까지 O(1)성능을 가진다고 했습니다. 해시 테이블을 만들 때 해시함수가 중요한 역할을 한다고 하는데 그렇다면 해시테이블의 시간복잡도는 해시 함수 종류에 영향을 받아 결정되는 것인지 궁금합니다.
Answer 2
1
맞습니다!
인프런 AI 인턴이 답변으로 모두 설명이 가능합니다.
이런 이유로 좋은 해시 함수를 구현하는 게 필수적이라 단점으로 생각할 수 있습니다.
궁금증이 해결되셨나요?
1
안녕하세요, 인프런 AI 인턴입니다.
rhkdtjd_12님께서 문의하신 해시테이블의 시간 복잡도와 해시 함수의 관련성에 대해 답변드리겠습니다.
해시 테이블의 시간 복잡도는 기본적으로 조회, 삽입, 수정, 삭제의 평균 시간 복잡도가 O(1)입니다. 그러나 이는 이상적인 상황을 가정한 것이며, 해시 함수의 선택에 대단히 큰 영향을 받습니다.
해시 함수가 좋은 품질이라면 데이터가 테이블 내에 균등하게 분포되어 충돌이 적게 발생하고, 이는 O(1) 시간 복잡도를 유지하는 데에 도움을 줍니다. 반면에, 해시 함수가 비효율적이라면 충돌이 빈번하게 발생하여 데이터를 처리하기 위한 시간 복잡도가 O(n)까지 올라갈 수도 있습니다.
따라서 해시 함수를 잘 설계하는 것이 해시 테이블의 성능을 최적화하는 데 매우 중요합니다. 충돌을 최소화하고 데이터를 효과적으로 분배할 수 있는 해시 함수를 사용하는 것이 바람직합니다.
위와 관련된 이해를 돕기 위한 기존 질문의 답변을 참고해 보세요:
- HashTable set 메서드
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
큐의 마지막 데이터가 head에 위치해야 하는 이유가 궁금합니다.
0
71
2
이중연결 리스트 데이터 삭제시 질문이 있습니다.
1
60
2
자바스크립트 배열은 동적이 아닌가요?
1
85
2
자바스크립트 배열
0
75
2
코테에서 링크리스트 자료구조를 사용해야 하면, 이번 강의에서 구현한 메서드들도 모두 직접 구현하면 되나요?/
0
148
2
공부 방식 질문 드립니다.
1
115
2
메모이제이션과 타뷸레이션 관련해서 질문드립니다.
1
166
2
병합정렬에서 질문이 있습니다.
2
140
1
병합정렬 질문 있습니다.
1
136
5
데이터 삽입, 삭제 함수 오류 범위 설정
0
156
2
해시 테이블에서 질문이 잇습니다.
2
126
2
시간복잡도 계산 시 1회 연산당 연산량은 왜 고려하지 않는 건가요?
1
146
2
터미널 설정
0
112
2
2:13분 관련 질문입니다
0
89
1
8:47초경부터 9:00초까지 질문입니다.
1
132
2
tail을 삭제하는 경우에 관련해서 질문이 있습니다.
0
106
1
2:36초 head 위치가?
1
108
2
환경구축강의 중 터미널 파일 실행오류
0
159
2
4:58 이중for문 질문있습니다.
0
103
1
hanoi함수 처음 호출에 대해서 여쭤봅니다.
1
127
2
해쉬테이블 데이터 관련해서 질문있습니다.
0
145
2
자바스크립트 Map과 어떤 차이가 있나요??
0
201
2
질문이있습니다.
0
101
1
3:54 질문 clear() 함수
1
77
1