해시 자료구조는 키-값 쌍으로 이루어진 데이터 구조로, 키를 사용해서 O(1) 시간복잡도로 값을 구할 수 있다. 이때 해시 자료구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 값을 관리한다.
해시충돌은, 다른 키를 사용해서 해시 함수를 돌렸을 때 같은 결과가 나오는 경우를 말한다.
해시가 뭐야?
해싱이란 어떠한 데이터를 고정된 길이의 code에 맵핑하는 과정을 말한다. 전체 과정은 1) raw 데이터를 해싱 매커니즘을 돌린다 2)이렇게 돌린 결과물로 hash라는 output이 나오게 된다.
해싱 과정은 one-way 과정이다. 즉, 원 데이터를 해싱값으로 변경할 수는 있어도, 이 해싱 코드를 원 데이터로 복구하는 건 거의 불가능하다. 그래서, 비밀번호같은 데이터를 db에 저장할 때 스프링 시큐리티는 해싱 방법을 사용한다.
키밸류 자료구조도 이러한 해싱 방법을 사용해서, 유니크한 키에 해싱 값을 맵핑하고 값을 조회하는 방식을 쓴다.
해시충돌은 왜 생겨?
두개의 인풋 데이터가 같은 해시값을 만들어버릴 때 해시 충돌이 발생한다.
하지만, 이건 어떠한 문제라기보다는 해시의 특성으로 보는 게 맞다고 한다. 해싱과정은 결국 인풋값의 길이에 관계 없이 고정된 길이의 해시값을 만든다.
그래서, 우리가 인풋에 대한 무한한 경우의수를 갖고 있고, 아웃풋에 대한 유한한 경우의 수를 갖고 있다면 당연히 나타날 수밖에 없는 현상이다.
해시 충돌은 어떻게 막아?
개방 주소법을 쓸 수 있다. 특정 값이 들어가야 할 자리(버킷)이 이미 사용되오 있으면 다른 해시 버킷에 데이터를 삽입하거나, 분리 연결법으로 버킷을 연결리스트나 트리 형태로 관리해서 버킷에 들어갈 수 있는 값의 수에 제한을 두지 않는 방식이다.
개방 주소법에서 다른 해시 버킷을 찾을 때는
-
선형 탐사법 : 임이의 고정된 크기만큼 한칸씩 옮기면서 빈 버킷을 찾는다. 특정 버킷 주변이 모두 채워져 있다면 해시 성능이 저하될 수 있다. 이 접근 방법은 해시 자료 구조 전체에 해시 충돌이 균등하게 발생할 때 유용합니다.
-
제곱 탐사법 : 제곱으로 칸을 늘리면서 빈 버킷을 찾는다. 보폭이 점점 늘어나기 때문에 선형 탐사법처럼 특정 영역에 값이 밀집되어 저장되어도 해당 영역을 빠르게 벗어날 수 있다. 하지만, 여러 값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서로 탐사할 수밖에 없어 비효율적인 상황이 발생할 수 있다.
-
이중 해싱 : 해시 충돌이 발생하면 보조 해시 함수를 사용하는 방법이다. 추가적인 보조 해시 함수에서 연산이 발생하기 때문에 다른 방식에 비해 많은 연산량이 요구된다.
참고자료
