20221102 TIL 해시 충돌을 어떻게 해결할 것인가

오늘은 홀맨님이 맵 자료구조를 직접 구현해서 푼 코딩 문제 풀이를 공유해주셨다.
풀이처럼 필요에 따라 자료구조를 직접 구현할 경우도 있다고 하셔서 해시맵이 어떻게 구현되어 있는지 찾아보았다.

https://www.google.com/imgres?imgurl=https%3A%2F%2Fcdn.icon-icons.com%2Ficons2%2F2098%2FPNG%2F512%2Fhash_icon_128843.png&imgrefurl=https%3A%2F%2Ficon-icons.com%2Fko%2F%25EC%2595%2584%25EC%259D%25B4%25EC%25BD%2598%2Fhash%2F128843&tbnid=Z0ON-6sDu-37VM&vet=1&docid=fWkj0Q7lc90igM&w=512&h=512&hl=ko&source=sh%2Fx%2Fim

먼저 '맵'은 키와 키에 해당하는 값의 쌍으로 데이터를 다룬다.
그리고 키로 키에 해당하는 값을 바로 조회할 수 있기 때문에 어떤 값을 조회할 때 매우 유리한 자료구조이다.

해시 맵은 이름처럼 해시를 이용한 맵이다.
키에 대한 해시값으로 값을 저장하고 조회한다.
그런데 해시함수는 반환 값으로 가능한 경우의 수가 정해져 있기 때문에 그 개수 이상의 값을 해시함수에 돌렸을 때 무조건 겹치는 값이 나올 수 밖에 없다.
따라서 해시 함수를 돌렸을 때 동일한 결과가 나올 수 있는데, 이를 해시 충돌이라고 하고, 해시 맵에서는 해시 충돌이 일어났을 때 어떻게 값을 저장할 지가 중요하다.

이 때 크게 두 가지 해결 방식이 있다.
첫 번째 방식은 open addressing 방식이다.
이 방식은 해시 충돌이 난 경우에 다양한 probing방식을 이용해서 비어있는 다른 해시 테이블의 다른 슬롯에 데이터를 넣는다.

https://www.geeksforgeeks.org/hashing-set-3-open-addressing/amp/

두 번째 방식는 separate chaining방식이다.
이 방식은 해시 충돌이 난 경우에 그 값들을 링크드 리스트로 만들어서 저장하게 된다.

https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/amp/

하지만 해시 충돌이 많이 일어날수록 결국 링크드리스트를 이용하게 되어 조회에 강점이 있는 해시맵의 특성이 무뎌진다.

따라서 자바8부터는 충돌이 일어나면 조금 더 효율적인 형태로 저장한다.
충돌 개수가 적을 때는 링크드 리스트를 사용하다가 일정 수준 이상 많아지면 balanced binary tree를 이용한다.
링크드 리스트를 사용하다가 하나의 해시테이블 슬롯에 8개 키-값 쌍이 담기면 트리로 변경된다.
그리고 만약 키-값 쌍이 삭제되어 6개가 되면 다시 링크드 리스트로 변경된다.

자바 8에서 구현된 충돌 개수에 따라 변경되는 것까지 코딩테스트를 풀면서 구현하기는 어렵겠지만, 자주 활용되는 separate chaining 방식으로 꼭 구현을 해보자!