인프런 커뮤니티 질문&답변
작성한 질문수
안녕하세요 해시 관련 질문이 있습니다.
작성
·
276
0
강사님 안녕하세요 ㅎㅎ 강의 잘 듣고 있습니다.
현재 챕터 5 자료구조 파트를 공부하고 문제를 풀면서 관련 개념들을 정리하고 있는데요.
HashMap에 대한 질문이 있습니다.
HashMap의 경우 시간 복잡도가 O(1)이라고 하는데
hashmap 내부 로직 구현 예제를 보니 다음과 같더라고요...
public String get(String key) {
String value=values[getIndex(key)];
return value;
}
private int getIndex(String key) {
for(int i=0;i<=this.index;i++) {
if(this.keys[i].equals(key)) {
return i;
}
}
return -1;
}
(https://jk4564.tistory.com/8)
이 경우 시간복잡도가 O(n)이어야 하는거 아닌가요?
제가 시간복잡도 개념을 잘 못 이해하고 있는건지
아니면 저 예시가 잘 못 된건지
잘 이해가 안 되네요 ㅜㅜ
답변 2
0
0
김태원
지식공유자
안녕하세요^^
위에 코드는 그냥 개인이 짠 코드일 뿐입니다. 파이썬 라이브러리 내부 코드는 저도 본적이 없습니다.
파이썬 딕셔너리의 get 함수만 보더라도 해쉬이론이 총 동원된 함수로 만들어져 있을 겁니다.
구글링으로 시간복잡도를 정리해 놓은 블로그들을 본 것입니다.