비선형 데이터구조, 해시(Hash) #5 충돌 해결(Collision Solution)

이전글

https://yonghwankim-dev.tistory.com/174

비선형 데이터구조, 해시(Hash) #4 LoadFactor 메서드

 

개요

이전글에서는 테이블에서 데이터가 차지하는 수치인 LoadFactor에 대해서 알아보았습니다. 이번글에서는 테이블에서 해쉬코드 값이 같아서 충돌이 발생하는 경우 해결하는 방법에 대해서 알아보겠습니다.

 

1. 선형 조사법(Linear Probing)

선형 조사법(Linear Probing)은 채우려는 공간이 이미 차있다면, 비어있는 칸을 찾을때까지 다음 칸을 확인하는 방법입니다.

선형 조사법의 특징은 다음과 같습니다.

• 해시 충돌이 발생하면 비어있는 칸을 찾을때까지 다음 칸을 확인함
• 요소를 제거할 때 null로 두지 않고 해당 위치에 무언가가 있었는데 이제는 비었다는 표시를 해야합니다. 그래서 추후에 다른 요소를 탐색할 때 비어있는 칸에서 멈추지 않고 처음부터 끝까지 요소들을 탐색이 가능함
• 추가된 데이터를 찾기 위해 더 많은 칸을 탐색해야 함
• 배열에서 선형 조사법으로 데이터를 추가시 순차적으로 추가됨.

2. 2차식 조사법(Quadratic Probing)

2차식 조사법(Quadractice Probing)은 선형 조사법에서 순차적으로 다음칸에 데이터를 추가하는 대신 1부터 순서대로 제곱하여 더한 칸(1*1, 2*2, 3*3, ..., n*n)을 확인하는 방법입니다. 만약 테이블의 끝을 넘어간다면 % 연산을 하여 다시 테이블의 범위안에 들어오게 합니다.

3. 이중 해싱(Double Hashing)

이중 해싱 해결방법은 해시 충돌이 발생할 경우 2번째 해시함수를 호출하고 첫번째 해시함수 값과 두번째 해시함수 값을 합한 값을 새로운 해시함수 값으로 하여 데이터를 저장합니다.

 이중 해싱 방법의 대표적인 특징은 다음과 같습니다.

• 해시 함수가 2개 존재
• 두번째 해시 함수는 첫번째 해시 함수와 달라야 함
• 두번째 해시 함수는 정수 0을 반환하면 안됨 (0을 반환하면 충돌 발생한 위치에서 변함이 없음)
• 대표적인 단점은 2개의 다른 해시 함수가 필요함

지금까지 해쉬 충돌 해결방법으로 대표적인 방법인 선형조사법, 2차식 조사법, 이중 해싱에 대해서 소개하였습니다. 이러한 해결방법에도 불구하고 위 3가지 방법의 공통적인 단점이 존재합니다. 그것은 테이블의 데이터가 빠르게 찬다는 단점이 존재합니다. 이러한 방법을 해결하기 위해서 다음 글에서는 체이닝(chaining)에 대해서 소개하겠습니다.

 

References

[부스트코스] 자바로 구현하고 배우는 자료구조