Java Collection 해시 도입 - 해시 충돌

3, 13 두 값 모두 10으로 나눈 경우 나머지가 3이 된다. 값은 다르나 같은 해시코드가 출력되는 것을 해시 충돌이라 부른다.

  • 3 % 10 = 3
  • 13 % 10 = 3

이러한 문제가 발생할 경우 해시인덱스로 사용 시 나중에 사용한 해시코드가 덮어씌워져 기존 값을 없애고 값이 변하게 된다.

단순한 해결 방법으로는 CAPACITY 입력 범위를 키우면 된다. 13이 문제라면 13보다 더 큰 범위로 설정하면 충돌이 발생되지 않으나, 처음에 문제 됬던 메모리 낭비가 다시 발생하게 될 것이다.

해시 충돌 받아들이기

이러한 해시 충돌을 피하지 않고 인정한다면 충돌 가능성을 낮추고, 충돌이 발생하면 동일한 인덱스로 값을 두 개를 함께 저장한다.

충돌 발생 - 저장

  • 3 % 10 = 3
  • 13 % 10 = 3
+-----+-----+-----+-----------+-----+-----+-----+-----+-----+-----+-----+
|     |     |     |  [3, 13]  | 14  |  5  | 16  |  7  |     |  9  |     |
+-----+-----+-----+-----------+-----+-----+-----+-----+-----+-----+-----+
[0]   [1]   [2]   [3]         [4]   [5]   [6]   [7]   [8]   [9]   [10]

다음과 같이 데이터를 입력하고 조회하는 알고리즘을 구성한다면 다음 순서로 진행될 것이다.

충돌 발생 - 조회

  • 3 과 13 모두 동일한 인덱스에 배열로 저장됨
  • 사용자가 3를 입력한 경우 충돌 난 인덱스에서 모든 값 비교
    • 첫 번째 for문으로 equals 비교하여 검색하여 true 로 인해 반환

충돌 발생 - 조회 (최악의 경우)

  • 3, 13, 23, 33, ...,99 모두 동일한 인덱스에 배열로 저장됨
+-----+-----+-----+----------------------------+-----+
|     |     |     |  [3, 13, 23, 33, ..., 99]  | 14  |
+-----+-----+-----+----------------------------+-----+
[0]   [1]   [2]   [3]                          [4]   ...
  • 사용자가 99를 입력한 경우 충돌 난 인덱스에서 모든 값 비교
    • for문으로 equals 비교하여 모든 데이터를 순회함
    • 마지막 배열에서 "99" equals 으로 비교해 true로 반환함
    • O(n) 가까운 성능이 발생함