Hash - 해시 알고리즘5 - 해시 충돌 설명

해시 충돌

99, 9의 두 값은 10으로 나누면 9가 된다. 따라서 다른 값을 입력했지만 같은 값의 해시 코드가 나오게 되는데 이것을 해시 충돌이라 한다.

• 99 % 10 = 9
• 9 % 10 = 9

 

해시 충돌이 발생하면 어떤 문제가 나타나는지 알아보자.

• 먼저 99의 값을 저장한다. 해시 인덱스는 9이므로 9번 인덱스에 99 값을 저장한다.
• 다음으로 9의 값을 저장한다. 해시 인덱스는 9이므로 9번 인덱스에 9 값을 저장한다
• 결과적으로 배열의 인덱스 9 에는 처음에 저장한 값 99는 사라지고, 마지막에 저장한 값 9만 남게된다.

 

이 문제를 해결하는 가장 단순한 방법은 CAPACITY를 값의 입력 범위만큼 키우면 된다. 여기서는 99까지만 입력하므로 CAPACITY를 100으로 늘리면 된다. 그러면 충돌이 발생하지 않는다. 하지만 앞서 보았듯이 이 방법은 메모리 낭비가 심하고, 모든 int 숫자를 다 받는 문제를 해결할 수 없다.

 

 

해시 충돌 해결

해시 충돌을 인정하면 문제 해결의 실마리가 보인다.

해시 충돌은 낮은 확률로 일어날 수 있다고 가정하는 것이다.

해결 방안은 바로 해시 충돌이 일어났을 때 단순하게 같은 해시 인덱스의 값을 같은 인덱스에 함께 저장해버리는 것이다.

 

해시 충돌과 저장

 

해시 충돌과 조회

해시 충돌이 난 경우 내부의 데이터를 하나씩 비교해보면 원하는 결과를 찾을 수 있다. 예를 들어 99를 조회한다고 가정해보자.

 

• 99의 해시 인덱스는 9이다. 배열에서 9번 인덱스를 찾는다.
• 배열 안에는 또 배열이 들어있다. 여기에 있는 모든 값을 검색할 값과 하나씩 비교한다.
  • [99,9]의 데이터가 들어있는데 첫 비교해서 원하는 데이터를 찾을 수 있다.

• 9의 해시 인덱스는 9이다. 배열에서 9번 인덱스를 찾는다.
• 배열 안에는 또 배열이 들어있다. 여기에 있는 모든 값을 검색할 값과 하나씩 비교한다.
  • [99,9]의 데이터가 들어있다. 첫 비교에서 99 equals 9 는 거짓이므로 실패한다. 다음 비교에서 9 equals 9 이므로 원하는 데이터를 찾았다.
  • 비교시 equals를 사용했지만 기본형이라면 물론 ==을 사용해도 된다.

최악의 경우

• 값을 9, 19, 29, 99만 저장한다고 가정해보자. 이 경우 모든 해시 인덱스가 9가 된다.
• 따라서 9번 인덱스에 데이터가 모두 저장된다.
• 이렇게 되면 데이터를 찾을 때 결국 9번에 가서 저장한 데이터의 수 만큼 값을 반복해서 비교해야 한다.
• 따라서 최악의 경우 O(n)으 성능을 보인다.

 

정리

해시 인덱스를 사용하는 방식은 최악의 경우 O(n)의 성능을 보인다. 하지만 확률적으로 보면 어느 정도 넓게 퍼지기 때문에 평균으로 보면 대부분 O(1)의 성능을 제공한다. 해시 충돌이 가끔 발생해도 내부에서 값을 몇 번만 비교하는 수준이기 때문에 대부분의 경우 매우 빠르게 값을 찾을 수 있다.