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) 가까운 성능이 발생함