해쉬 충돌

java · 16 Jan 2023

해쉬값 하나에 여러값이 존재하는 현상으로, 해쉬값이 유한하고, 입력값은 무한하기 때문에 생기는 문제다
해결방법으로는 폐쇄주소법(close addressing), 개방주소법(open addressing), separate chaining 기법등이 있다.

중복된 해시 코드를 가진 데이터들을 연결하는 방식
linked list(가변배열 메모리 할당) 또는 red-black tree(메모리 사용량 많음)로 체이닝한다.

빈 버킷을 찾아서 데이터를 넣어주는 방식

폐쇄주소법과 개방주소법을 합친 방식이다.

해쉬함수에서 해쉬코드의 범위를 배열의 크기만큼으로 지정하고 모든 해쉬맵이 찰때까지 해쉬 코드 할당한다.
다 찬 경우에는 체이닝을 이용해 데이터를 연결한다.

8개까지는 링크드 리스트로 관리하다가 8개 이후부터는 트리로 관리한다.

자바의 해쉬맵도 이 기법을 사용한다.