공부 목적으로 작성되었습니다.
잘못된 점이나, 수정되어야 할 부분 언제든지 지적해주시면 감사하겠습니다.
Linear Probing
Separate Chaining 과는 다른 Hash Collision 해결 방법이다.
선형 조사법이란, 충돌이 발생한 곳에서 다음 Bucket 중 빈 Bucket 이 나올 때까지 탐색해나가는 알고리즘이다.
우리는 데이터를 넣을 때, 1개의 Bucket 만 허용한다.
→ 주어진 Index 내에서
동작 원리
- Hash Collision ( 해시 충돌 ) 이 일어나면, Hash Table 을 차례대로 탐색한다.
a. 이때, 충돌이 일어난 Index 를 기준으로 1칸씩 탐색해나간다. - 빈 Bucket 이 있을 경우, 그 부분에 Data 를 삽입한다.
예시
위의 예시를 보면서 이해를 조금 해보자.
Hash Table 을 하나 만들고, 내부의 Hash 함수는 input 값을 7로 나눈 나머지 값을 반환한다.
Bucket 의 개수는 6개로 되어 있으며, 값이 들어갔을 때, 충돌이 일어나면, 충돌이 난 Bucket 의 Index 를 기준으로 오른쪽으로 탐색한다.
-
따라서 44가 input 으로 들어왔을 경우, 2 의 index 를 가지지만, 3 의 index 에 위치한다.
-
80 또한 2 의 index 를 가지지만, 3을 거쳐 4의 index 로 밀려난 것을 확인할 수 있다.
이렇듯 빈 Bucket 을 찾으면서 탐색을 계속해ㅓㅅ 한다.
만약 Table 의 Index 의 끝까지 도달하였다면, 다시 0번째 Index 로 돌아가 탐색을 재개한다.
값을 찾고 싶을 경우
값을 찾을 때도 위와 같은 이미지를 사용할 수 있다.
f(30) = 2 를 반환하므로,
Linear Probing 을 이용해, 탐색을 하며 값을 찾아낸다.
값을 삭제할 때 또한 동일하게 값을 찾아내, 삭제하는 방식을 사용한다.
값을 삭제했을 경우 문제점
위의 예시를 자세히 봐주길 바란다.
우리가 80값을 삭제하면, index 4 의 Bucket 이 비게 된다.
값이 Null 일 경우에, 그 즉시 탐색이 종료되기 때문에, 12라는 값이 없다고 처리가 되는 것이다.
그러면 12의 값을 찾고 싶을 때는 어떻게 해야하는가?
삭제한 값에 대하여 마킹을 해주는 것이다.
마킹을 해줄 경우, 4번째 Index 에서 끝이 나지 않고, 계속해서 탐색을 진행하는 것이다.
따라서 우리가 원하는 12의 값을 찾을 수 있고, 탐색은 종료한다.
이처럼 수행했을 때, 최적의 시간복잡도는 O(1), 최악의 시간복잡도는 O(n) 을 가진다.
Reference
