아래 참고 포스팅에서 다양하게 자바에서 Hash 사용되는것들에 대해서 볼수 있다.
이 많은 해시들은 결국 Hash Function 에 의해서 가능한 서로 다른 키들에 대해 다른 해시 값을 생성하는데
만약 이때 해시값이 충돌하여 동일한 값을 가지게 되면 어떻게 될까?
정답은
Hash Collision
이다.
해시 충돌은 서로 다른 데이터가 동일한 해시 값을 가지는 상황(key는 다른데, hash가 같을 때)이다.
해시 테이블의 크기는 제한되어 있기 때문에 현실적으로는 피할 수 없는 현상이다.
정리해서 다시 말하면 hash 충돌은 피할 수 없지만, 해시 함수의 결과 값이 골고루 분포되도록, 해시 충돌이 균등하게 발생하도록 해시 함수를 정하는 것이 좋다.
방법은 아래와 같다.
- seperate chaining (체이닝)
- 각 배열의 인덱스에 LinkedList를 사용하여 키들을 모아둔다.
충돌이 발생하면 연결 리스트에 노드를 추가한다. - 과정
- 해시 테이블 초기화 진행
해시 테이블을 만들고, 각 인덱스에 빈 LinkedList를 할당한다. - 데이터 삽입
해당 데이터의 해시 값을 계산하고 그 해시 값을 인덱스로 하는 LinkedList에 데이터를 추가한다.
해당 인덱스에 다른 데이터가 이미 존재하는 경우에, 그냥 LinkedList의 다음 노드에 데이터를 추가한다. - 데이터 검색 또는 삭제
동일한 해시 함수로 해당 인덱스을 찾고, LinkedList에서 데이터를 검색하거나 삭제한다.
- 해시 테이블 초기화 진행
- 장점
구현이 간단하고 유연하다.
동적으로 크기를 조절하기 쉽다. - 단점
메모리 사용이 비효율적일 수 있다. ⇒ 모든 인덱스에 LinkedList를 넣어놔야만 한다.
연결 리스트의 길이가 길어지면 검색 시간이 길어질 수 있다. ⇒ LinkedList의 탐색 시간 복잡도는 O(n)
(시간 복잡도 관련해서는 아래 참고 포스팅 참고)
참고: LinkedList 대신 트리를 사용하여 충돌을 해결할 수 있으며, 이로써 탐색 시간을 효율적으로 유지할 수 있다.
- 각 배열의 인덱스에 LinkedList를 사용하여 키들을 모아둔다.
- open addressing (개방 주소법)
- 충돌이 발생하면 다른 빈 버킷을 찾아 이동하거나 특정 규칙에 따라 다른 위치에 값을 저장한다.
대표적인 개방 주소법에는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다. - 과정
- 해시 테이블 초기화 진행
해시 테이블을 만들고, 인덱스가 아닌 버킷을 초기화 한다. - 데이터 삽입
데이터를 삽입할 때, 해당 버킷이 비어있으면 데이터를 삽입한다.
충돌이 발생하면 다른 방법을 사용하여 빈 버킷을 찾아 데이터를 삽입한다. - 데이터 검색 또는 삭제
검색 또는 삭제 시에도 동일한 방법으로 데이터를 찾거나 삭제한다.
- 해시 테이블 초기화 진행
- 장점
캐시 및 메모리 사용이 효율적이다. - 단점
복잡한 구현이 들어간다.
클러스터링 성능 저하 우려가 있다.
- 충돌이 발생하면 다른 빈 버킷을 찾아 이동하거나 특정 규칙에 따라 다른 위치에 값을 저장한다.
또 다른 방법으로는 아예 해시 테이블 크기를 늘려주는방법도 있다.
해시 테이블 리사이징
테이블 리사이징은 기존 테이블 크기의 2배 크기의 테이블 선언하여, 기존 테이블의 데이터를 옮긴다. 자바의 경우, 테이블 공간의 3/4 이상을 차지하면 리사이징을 한다. 이는 사용하는 언어에 따라 리사이징 되는 수치는 다르다.
또한 테이블 리사이징을 하게 되면, 중첩되는 해시의 경우 다시 해시하여 다른 해시로 값을 이동하기도 한다.
참고 포스팅
https://thenicesj.tistory.com/1008
https://thenicesj.tistory.com/349
https://thenicesj.tistory.com/772
https://thenicesj.tistory.com/599
https://thenicesj.tistory.com/417
https://thenicesj.tistory.com/284
'IT > Java' 카테고리의 다른 글
RequestParam 에서 @Valid 사용 (14) | 2024.08.11 |
---|---|
DatasSource Exclude 설정 관련(DataSourceAutoConfiguration) (13) | 2024.08.10 |
try-with-resources (AutoCloseable) (20) | 2024.08.05 |
[ArrayList] 조건 삭제를 위한 removeIf (15) | 2024.08.02 |
[Error] incompatible types / Type mismatch (13) | 2024.08.01 |
댓글