Hash 자료구조는 키값 쌍으로 이루어진 데이터구조를 키를 해시함수를 이용해서 O(1)시간 복잡도를 찾을 수 있다. 실제 값들은 버킷이자 테이블에 저장되어있으며, 위치는 키를 해시해서 저장하고 찾는다.
그런데 이 때 키를 해시해서 저장할 때, 이미 버킷에 값이 있다면, 충돌이 일어날 것이다. 이를 해시충돌이라고 한다.

해시 충돌의 해결방법

해시 충돌완화 기법에는 크게 다른 비어있는 버킷에 사용하는, 개방 주소법, 버킷을 연결리스트나 트리 형태로 관리해서 버킷에 들어갈 값의 수에 제한 두지 않는 분리 연결법을 사용해서 충돌을 완화한다.

개방 주소법에는 어떤게 있을까?

선형 탐사법

충돌이 일어날 때 고정된 크기 만큼 한번 옮겨서 빈 버킷을 찾는 것 이다. 빈 버킷을 못찾는다면, 즉 특정 버킷 주변에 모두 채워져있다면, 계속 탐사를 하므로 시간이 오래걸릴수 밖에 없다.

제곱 탐사법

선형 탐사는 충돌이 났을 때, 한 칸씩 옮기면서 빈 버킷을 찾는 반면에 제곱 탐사법은 보폭이 제곱씩 늘어난다. 그렇기에, 특정 영역에 값이 밀집되어 저장되어도 해당영역을 빠르게 벗어날 수 있다. 하지만 여러 값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서로 탐사 할 수 밖에없어 비효율적인 상황이 발생할 수 있다.(2차 군집현상)

이중 해싱

해시 충돌이 발생할 경우, 보조 해시를 사용하는 방법이다. 해시 충돌 가능성이 가장 작지만, 추가적인 보조 해시 함수에서 연산이 발생하기에, 다른 방식에 비해 많은 연산량이 요구된다.

실제 자바에서 HashMap은 분리 연결법을 사용하며
연결은 RBT트리 형태를 이용한다고 한다.
이를 통해서 링크드리스트를 사용할 때보다, remove연산이 일어날 때와 get연산시의 속도 향상을 개선할 수 있다고한다.
https://d2.naver.com/helloworld/831311