Resolve Hash Collision

💡 선형조사법 (Linear Probing)

채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법이다.
비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 한다.

 

예시

• 객체 x
  
  • 객체 x의 hashCode 값인 h를 구한다.
  • h를 양수로 변환 -> h & 0x7FFFFFFF;
  • 테이블의 크기와 % 연산 -> h % table.size();
  • h를 가지고 x를 적절한 위치로 저장, 이 때 위치는 hashCode의 값에 따라 다름
• 객체 y
  • 위와 동일한 방법으로 h를 구한다.
  • x의 위치와 동일한 값이 나오면 x의 위치에 y를 저장해야 한다.
  • 이런 상황을 충돌이라고 한다.

 

해결

• x의 다음 칸에 y를 저장
  • y의 위치가 바뀌었다는 사실을 알려야 한다.\
  • 삭제의 경우 데이터 삭제 후 null이 아닌 데이터가 삭제되었다는 별도의 표시가 필요하다.
  • 즉, null에 도착할 때 까지 위치값을 +1 씩 더하면서 자료구조를 탐색하는 것이다.

 

단점

관계가 있든 없든 데이터가 뭉치게 된다. (비효율적)

결국 배열에 순차적으로 추가하게 되어버린다.

이 문제를 해결하기 위한 2차식 조사법이 있다.

---

💡 2차식 조사법(quadratic probing)

이미 값이 있는 배열 칸에 무언가를 넣으려 할 때 선형조사법처럼 위치값에 +1을 하지 않고,
그 값의 제곱만큼 더하는 방법

ex:
hash value 의 1제곱
hash value의 2제곱
...

 

다음 칸 대신 1부터 순서대로 제곱하여 더한 칸( 1^21​2​​,  2^22​2​​, ... )을 확인하는 방법이다.
테이블의 끝을 넘어간다면 % 연산을 해서 다시 테이블의 범위 안에 들어오게 한다.

---

💡 이중 해싱(double hashing)

hashCode 함수가 2개 있어 채우려는 공간이 이미 차 있다면
두 hashCode의 결과를 더한 값을 테이블 내의 위치가 되게 하는 방법이다.

• 이 두 HashCode의 결과를 더한 값은 요소가 들어가야 할 테이블 내의 위치값이 된다.

 

이중 해싱은 아예 다른 해시 함수를 사용할 수 있기 때문에 데이터를 더 골고루 넣을 수 있다.
하지만 첫 위치를 알기위한 기본적인 Hash 함수와, 그 자리가 차 있을떄 호출하는 두번째 해시 함수
2개의 Hash 함수가 필요하다는 단점이 있다.

• 2번째 hashCode 함수는 첫 함수와 달라야 한다.
• 0을 반환하면 안된다.

---

💡 팁

 

이중 해싱이 선형 조사법, 2차식 조사법보다 데이터를 더 골고루 넣을 수 있는 이유는?

선형 조사법과 2차식 조사법은 더하는 값(1, 2, 3, ... 또는 1^2, 2^2, 3^2, ...)에 규칙성이 있는 반면에,
이중 해싱은 두번째 해시 함수가 리턴하는 값이 임의적이기 때문에 배열의 더 다양한 위치에 값을 저장할 수 있다.