[자료구조] Hash Table : 충돌이 발생하는 이유와 해결 방법

오늘은 Hash Table라는 자료구조에서 충돌이 발생하는 이유와 충돌이 발생하지 않도록 하기 위해서는 어떻게 해야 하는지 알아본다. 먼저 Hash Table은 저장되는 데이터가 (key, value)처럼 하나의 쌍을 이루는 자료구조를 말한다. 이때 key가 존재하지 않는 value는 저장할 수 없으며 key가 중복되어서는 안 된다. 

---

해쉬 함수

학생들의 정보를 Hash Table에 저장하려고 한다. 이때 학생들의 학번을 key로 하는데, 학번이 2020103과 같은 형태로 되어있어서 배열의 크기를 이에 맞춰서 선언해야하며 배열을 생성하더라도 쓰지 않는 공간이 많기 때문에 효율적이지 못하다.

 

따라서 학번을 해쉬 함수로 전달하여 반환된 값을 key로 설정하려고 한다. 해쉬 함수는 다음과 같다. 학번을 입력하면 학번을 1000으로 나눈 나머지를 반환하도록 한다. 이를 통해 학번에서 뒤의 3자리 숫자를 key로 설정할 수 있게 되었다.

function hash(studentId){
	return studentId % 1000
}

하지만 2020103인 학생과 2019103인 학생을 해쉬 함수로 전달했을 때 동일한 key를 사용하게 되는 문제가 발생한다. 이러한 문제를 해쉬 충돌이라고 한다. key를 간소화하기 위해 해쉬 함수를 사용하였지만 해쉬 함수에 의해 key가 중복되는 문제가 발생하였다.

 

해쉬 충돌 해결하기

선형 조사법

만약 학번에 1000으로 나눈 나머지를 key로 사용하였을 때 2020103과 2019103인 학생의 key가 중복된다고 해보자. 먼저 2019103인 학생이 key를 103으로 하여 데이터가 저장되었다면 2020103은 key를 103으로 저장하려고 할 때 이미 존재하는 것을 확인 후에 바로 옆 칸인 104에 저장할 수 있을 것이다. 

 

이처럼 중복된 key가 존재할 때 key를 +1씩 증가시켜 바로 옆자리를 key로 설정하는 것을 선형 조사법이라고 한다. 하지만 선형 조사법은 충돌의 횟수가 증가함에 따라서 특정 영역에 데이터가 집중되는 문제가 발생하여 충돌의 확률을 높이게 된다.

 

이차 조사법

선형 조사법을 활용하면 충돌이 발생할 수록 key가 한곳에 집중되고, 이는 충돌이 발생할 확률을 높이게 된다. 그렇다면 바로 옆 칸이 아닌 멀리 떨어져 있는 칸을 key로 설정할 수 있을 것이다. 이를 이차 조사법이라고 한다.

 

만약 key가 2인 곳에 이미 데이터가 저장되어 있다면 2^2인 4를 확인한다. 하지만 해쉬 충돌이 발생했을 때 다음 key의 후보를 위해 접근하는 위치가 항상 동일하게 된다. 따라서 이차 조사법 또한 특정 영역에 key가 집중되는 문제가 발생한다.

 

이중 해쉬

선형 조사법과 이차 조사법에서 문제가 되었던 것을 이중 해쉬로 어느 정도 해결할 수 있을 것이다. 이중 해쉬는 key가 2인 곳이 이미 존재하거나 삭제된 key라면 key를 특정 숫자인 c로 나눈 나머지에 +1을 하여 다음 위치에 접근한다. 1을 더하는 이유는 해쉬 값이 0이 되는 것을 방지하기 위함이다. 또한 통계적으로 c를 소수로 하면 클러스터 현상(특정 영역에 key가 집중되는 문제)이 발생활 확률이 낮다고 한다.

---

지금까지 선형 조사법, 이차 조사법, 이중 해쉬는 Open Addressing Method이라 하는데 충돌이 발생했을 때 다른 자리에 대신 저장한다는 의미이다. 아래의 체이닝은 Closed Addressing Method이며 충돌이 발생했을 때 다른 자리가 아닌 그 자리에 저장한다.

 

체이닝

체이닝은 특정 key가 저장될 곳에 연결 리스트로 연결하여 여러 개의 key를 저장할 수 있도록 한다. 만약 key가 103인 데이터가 존재할 때 key=103인 곳의 연결 리스트에 데이터를 저장한다. 이후에 또 다른 key가 103인 데이터가 저장하려고 할 때 기존의 연결 리스트 다음에 새로운 연결 리스트를 생성하여 저장한다. 

 

체이닝을 적용하면 하나의 해쉬값에 다수의 데이터가 저장될 수 있다. 따라서 탐색을 할 때 동일한 해쉬 값으로 묶여있는 데이터를 모두 조사해야하는 단점이 존재한다. 하지만 해쉬 함수를 잘 정의했을 때 충돌 확률이 현저히 낮아진다.