해시테이블 개방번지화
189
작성한 질문수 3
해시테이블 개방번지화 방법에서 빈 공간을 찾는 방식을 알았는데, key를 넣었을 때 해시값을 찾을 때가 궁금합니다.
예를 들어 key로 daniel이 들어왔다면 체인법에서는 해당 해시값에서 모든 노드를 검사에 있는지 확인할 수 있었잖아요.
개방 번지화 방법에서는 다른 주소로 저장할 수가 있는데, 그러면 계속 뒷 메모리를 끝까지 검사하면서 찾아보아야 하나요?
아니면 마지노선이 있어서 daniel이 없다는 걸 화정하고 넘어갈 수 있는 기준이 있는건가요?
너무 깊숙히 생각하는 것 같지만, 시간복잡도가 끝없이 늘어나는 건지 걱정이 되서 질문드렸습니다. 감사합니다.
답변 1
0
안녕하세요 천지윤 님, 인프런 AI 인턴이에요.
해시테이블에서 개방번지화 방법은 빈 공간을 찾는 방식에 따라 다양한 구현 방법이 있습니다.
개방번지화 방법 중 하나인 선형 탐사(Linear Probing) 방법에서는 첫 번째 해시값에서 충돌이 발생하면, 다음 해시 위치를 검사하고, 또 충돌이 발생하면 그 다음 위치를 검사하는 식으로 빈 공간을 찾아갑니다. 이는 선형적으로 위치를 탐색하기 때문에 마지노선이 존재하지 않고, 끝까지 검사할 수도 있습니다.
또 다른 방법으로는 이차 탐사(Quadratic Probing) 방법이 있는데, 이는 해시값 충돌 시 일정한 간격으로 이동해 빈 공간을 찾습니다. 선형 탐사와 달리 충돌 시 이동 간격이 제곱 값으로 증가하기 때문에 마지노선에 도달하면 다시 충돌이 발생하는지 확인합니다.
시간복잡도는 이러한 탐사 방법들에서는 최악의 경우 충돌이 지속적으로 발생하여 해시테이블이 가득 찰 때까지 탐색을 해야 하기 때문에 O(n)이 될 수 있습니다. 따라서 충분한 공간을 확보하고, 해시 함수가 골고루 해시값을 분배해주는 것이 중요합니다. 감사합니다!
백준 서비스 종료인데 도전 과제 프로그래머스 문제로 올려주실수 있으신가요
0
73
1
도전과제 질문있습니다
0
77
2
안녕하세요 강사님 파이썬 커리큘럼 문의드립니다..
0
91
2
두수의합 sorting 질문
0
145
1
두수의합 Counter 사용
0
165
2
[문제3번] 두수의 합 : O(nlogn)
0
142
1
set을 활용한 중복제거
0
201
2
[문제 5번] 중복제거
0
155
1
최소값의 위치
0
145
1
백준 사용 시 채점 언어
0
179
1
백준 10546 배부른 마라토너
0
158
1
고정된 숫자 문제 질문
0
214
2
답은 맞는거같은데 틀렸어요
0
209
1
강의 커리큘럼 질문있습니다.
0
243
1
배열리스트 문제 5번 <중복 제거> 질문입니다.
0
280
1
체크배열을 set 으로 사용해도될까요?
0
252
1
연결리스트의 삽입과 삭제에서 시간복잡도.
0
359
1
내장 함수들의 시간복잡도는 외워둬야하나요?
0
241
1
중복 제거
0
345
1
카드 점수 정확성 테스트 경우의 수 문의
0
192
1
완강 후 후속 강의, 공부법 질문..
0
377
2
cnt = 1 과 nums.sort() 의 순서가 바뀌어야하지 않나요?
0
280
2
nums 조건오류인가요?
2
309
1
최솟값의 위치
0
252
2