해시 충돌

면접 질문으로 유명한 해시 충돌이다.

해시 충돌에 대해 이야기하려면 먼저 해시에 대해 알아야 하고, 왜 충돌이 일어나게 되는 지도 알아야 한다.

해시란 무엇인가?

해시 알고리즘에 대해서는 많이들 들어봤을 것이다. 자바에서 HashMap/Set을 사용해 보았을 수도 있고, 기본적으론 무언가를 저장하고, 다시 찾는 것에 아주 속도가 빠른 알고리즘으로 기억하고 있다. 명확하게 해싱Hashing을 하는 것은 다음을 의미한다.

해싱은 가변 크기의 입력값에서 고정된 크기의 출력값을 생성해 내는 과정. 이는 해시 함수(해싱 알고리즘으로 구현됨)라 알려진 수학적 공식을 따라 진행된다.
출처 : academy.binance.com/ko/articles/what-is-hashing

이렇게 해싱을 거친 값들은 일반적으로 해시 테이블에 저장된다.

해시 테이블Hash Table은 Hash Map으로도 불린다. (자바의 Hash Map이 그렇고, Set의 경우엔 중복이 제거된다)

위의 사진처럼 keys들을 해시 함수에 의해 buckets이라는 테이블에 저장한다고 하자.

그러나 keys에 들어올 수 있는 값은 무한한 데에 비해 buckets는 유한하다. 심지어 해시 함수로 변환된 값이 동일할 수도 있다! 따라서 이러한 *비둘기 집 원리에 의해 해시 충돌이 발생하게 된다.

(= 해시 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해시 함수도 충돌을 피할 수는 없다!)

*비둘기 집 원리 : n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다.

해시를 저장하는 과정에서, 다음처럼 John Smith와 Sandra Dee라는 Key 값이 해시 함수에 의해 동일한 값 152로 변환되었다고 가정하자. 이 상황을 해시 충돌이 일어났다고 볼 수 있고, 이를 해결하기 위해서는 다음과 같은 방법들이 있다.

변환된 key값을 저장하는 bucket에 entires(연결 리스트Linked List)를 할당하여 해시 충돌이 발생하면 데이터를 체인처럼 연결시키는 것을 말한다.

bucket 당 들어갈 수 있는 entrie 수에 제한을 두지 않으므로 메모리 문제를 야기할 수 있다.

분리 연결법Chaining과 달리 한 bucket에 들어갈 수 있는 entrie가 하나 뿐인 방법이다.

충돌이 일어나게 되면 해시 테이블 내에서 충돌이 일어난 곳보다 뒤의 빈 공간을 찾아서 key값을 저장한다.

개방 주소법의 장점은 추가적인 메모리 공간을 사용하지 않는다는 것이지만, 데이터를 찾아서 삭제하기 어렵다는 단점이 있다.

key를 저장하는 방식에는 대략적으로 3가지가 있다.

선형 탐색(Linear Probing ): 해시충돌 시 다음 빈 bucket, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.

제곱 탐색(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입한다.

이중 해시(Double Hashing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용한다.

참고자료

Squared