들어가기 전에
해시 충돌은 어떻게 해결할 수 있을까요? 해결 방법인 선형 조사법, 2차식 조사법, 이중 해싱에 대해 살펴보도록 하겠습니다.
학습 목표
해시 충돌의 해결 방법을 설명할 수 있습니다.
핵심 단어
- 해시 충돌
강의 듣기
1-8. 충돌 해결
해시 충돌을 해결하는 방법
1. 선형 조사법(linear probing)
채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법입니다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 합니다.
2. 2차식 조사법(quadratic probing)
다음 칸 대신 1부터 순서대로 제곱하여 더한 칸( 1^212, 2^222, ... )을 확인하는 방법입니다. 테이블의 끝을 넘어간다면 % 연산을 해서 다시 테이블의 범위 안에 들어오게 합니다.
3. 이중 해싱(double hashing)
hashCode 함수가 2개 있어 채우려는 공간이 이미 차 있다면 두 hashCode의 결과를 더한 값을 테이블 내의 위치가 되게 하는 방법입니다.
이중 해싱은 아예 다른 해시 함수를 사용할 수 있기 때문에 데이터를 더 골고루 넣을 수 있습니다. 하지만 해시 함수가 2개 필요하다는 단점이 있습니다.
생각해보기
1) 이중 해싱이 선형 조사법, 2차식 조사법보다 데이터를 더 골고루 넣을 수 있는 이유는 무엇인가요?
comment
선형과 2차식 조사법은 결국 첫번째 해싱을 통해 구한 인덱스 값 주변에 몰려서 분포할 수밖에 없다
그러나 두번째 해싱을 추가로 진행하게 되면 첫번째 해싱을 통해 얻은 인덱스 값과 아예 다른 위치로 가므로
충돌이 발생한 구역에 데이터가 몰리는 현상을 방지할 수 있다
이중해싱: 대입하는 해시함수를 전혀 다른 식을 사용할수 있기 때문에 배열이 조금더 다양하게 분포할수 있다.
선형 조사법과 2차식 조사법은 더하는 값(1, 2, 3, ... 또는 1^2, 2^2, 3^2, ...)에 규칙성이 있는 반면에, 이중 해싱은 두번째 해시 함수가 리턴하는 값이 임의적이기 때문에 배열의 더 다양한 위치에 값을 저장할 수 있다.