해시 인덱스를 사용하는 경우 데이터 저장 평균 시간 복잡도에 대해 질문
관련 내용:
강의:
55. 해시 알고리즘6 - 해시 충돌 구현21:56pdf:
6. 컬렉션 프레임워크 - 해시(Hash)24P 정리 부분
해시 인덱스를 사용하는 경우 데이터 저장을 할 때 평균 시간복잡도가 O(1)이라고 설명.
의문점
private static void add(LinkedList<Integer>[] buckets, int value) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex]; //O(1)
if (!bucket.contains(value)) { //O(n)
bucket.add(value);
}
}위와 같이 항상 bucket이 contains(..) 메서드를 호출하여 중복된 값이 있는지 확인하므로 O(n)의 시간 복잡도가 소요됩니다. 그래서 저는 항상 데이터 저장을 할 때는 O(n)으로 계산해야 한다고 생각했습니다.
강의에서 말씀하신 내용은 이상적으로 해시 충돌이 별로 발생하지 않는 상황(그리고 구체적인 구현은 신경쓰지 않는 상황)이라 가정하고 O(1)이라고 한 것일까요?
답변 2
0
자답
강의 해시 알고리즘6 - 해시 충돌 구현 15:02 부분에서 이미 설명한 내용.
데이터를 추가하는데 O(n)의 시간 복잡도가 소요.
그러나, 해시 충돌이 발생하지 않는 상황은 결국 각 bucket의 데이터가 0개나 1개 들어있는 거기때문에 contains(..)가 O(1)의 시간 복잡도로 소요된다.
따라서, 해시 인덱스를 사용하는 경우 데이터 저장을 할 때 평균 시간 복잡도가 O(1)이라 할 수 있다.
괜한 알람가게 해서 죄송합니다.
0
안녕하세요, 인프런 AI 인턴입니다.
임형준님이 말씀하신 것처럼, 해시 테이블에서 데이터를 저장할 때 평균 시간 복잡도는 일반적으로 O(1)로 간주됩니다. 이는 해시 충돌이 거의 발생하지 않는 이상적인 상황을 가정한 것입니다. 해시 테이블의 기본 아이디어는 데이터가 고르게 분산되어 각 버킷에 하나의 요소만 저장되도록 하는 것입니다. 이 경우 데이터 접근과 저장은 직접적으로 해당 인덱스로 접근하므로 O(1)의 시간 복잡도를 갖습니다.
그러나, 실제 상황에서는 해시 충돌이 발생하고 여러 요소가 같은 버킷에 저장될 수 있습니다. 이 때는 contains()를 사용하여 중복 여부를 확인해야 하므로, 특정 버킷 내부에서의 연산은 O(n)이 될 수 있습니다. 이 때문에, 해시 테이블의 최악의 상황에서는 시간 복잡도가 O(n)로 증가할 수 있습니다.
강의에서는 해시 테이블의 이론적 장점과 가장 이상적인 상황을 설명하신 것으로 보입니다. 실제로는 해시 함수의 설계가 얼마나 잘 되느냐에 따라 성능이 달라질 수 있습니다.
관련 질문을 더 깊이 이해하는 데 도움이 될 수 있는 게시물로 아래 링크를 참고하여 주세요:
- “6강 해시 충돌 구현” 관련 질문에서는 해시 테이블에서 LinkedList를 사용하는 이유에 대해 설명하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
제네릭 타입 매개변수 제한과 관련한 문의입니다.
0
80
3
강의가 좀 버겁다 느껴질 때 학습방법 문의
1
135
4
제네릭 반환값 및 파라미터 선언 방식의 변화 <T> T
0
62
1
new T()가 안 되는 니유
0
102
1
안녕하세요, 문제와 실행 결과가 다른 부분이 있어 제보드립니다.
0
98
2
자바 로드맵 선택 질문
0
111
2
실전 자바 중급 - 2편 후 추천 강의
0
176
2
실프로젝트에서 Java25버전 사용
0
121
1
Arrays.sort
0
68
1
블로그 작성 시, 저작권 문제에 대하여
0
166
1
중급2편 56강의 bucket.add(value); 메서드가 이해가 안됩니다.
0
94
3
pop()과 poll()의 차이
0
94
1
특정 index의 노드 조회하기 질문
0
66
2
List.of() 비어있는 불변 리스트 생성
0
81
2
문제2: 개 타입 반환
0
56
2
[리뷰] 중급2편까지 겨우 완강 했습니다.
0
114
2
문제와 풀이1 Ex2와 Ex3
0
65
2
노드 삭제시 노드 null값으로 초기화
0
77
2
강의영상에 대한 질문
0
57
1
타입 매개변수 제한
0
59
1
compareTo
0
68
1
직접 구현하는 연결리스트 3 - 추가 부분 질문있습니다
0
99
3
섹션 8-58 equals and hashcode 에서 코드가 다르게 생성됨
0
70
2
퀴즈 오류 관련 문의
0
109
1