해시 테이블에서 충돌(collision)/ 적재율 (load factor) 개념
1. Hash Table 충돌
hash table에서는 충돌을 줄이는 것이 알고리즘의 성능을 높이는 데 핵심 이슈이다.
여기서 충돌은 한 원소를 해싱해서 저장하려고 하는 상황에서 이미 다른 원소가 그 자리를 차지한 상황을 뜻한다.
2. Hash Table 충돌 원인
예를 들어,
.png)
위와 같은 그림의 hash table이 있다고 하자. 여기서 hash 함수는 간단히 h(x)= xmod5라고 해보겠다. 즉, x를 5로 나눈 나머지라는 것이다. 이럴 때 처음으로 9라는 숫자가 들어간다면,
9는 hash 함수에 따라서 9 mod 5 즉, 4의 위치에 저장이 되는 것이다.
.png)
위 그림처럼 말이다. 여기까지는 문제가 없다. 하지만 만약에 14가 추가로 해시 테이블에 들어가고 싶다면 어떻게 되는가?
그러면 또한 hash 함수에 의해 14 mod 5를 계산한 4 자리에 14를 넣고 싶어한다. 하지만 이미 4 자리에는 9가 있기 때문에 충돌이 일어나는 것이다.
3. 충돌, load factor 정의
이렇게 한 원소를 해싱이란 방법을 통해 저장하려고 하는데 다른 원소가 그 전에 해당 자리를 차지한 상황을 충돌 (collision)이라고 한다. 간단히 말해서 해시 테이블의 한 주소를 두개 이상의 원소가 다투는 상황과 유사하다고 보면 된다.
또한 해시 테이블에서 자주 등장하는 용어로는 load factor (적재율) 이라는 개념이 있다. 위에서 볼 수 있듯이 해시 테이블의 성능을 높이기 위해서는 충돌을 줄여야 하고 그렇기 위해서는 해시 테이블에 원소가 차 있는 비율이 성능에 중요하게 작용한다. 여기서 해시 테이블에 원소가 차 있는 비율을 우리는 load factor (적재율)이라고 하는 것이다.
해시 테이블의 전체 크기가 m이라고 가정하고, 테이블에 저장되어 있는 원소의 개수가 n개라고 가정하면 적재율은 n/m이라고 표현할 수 있다. 위 그림에서는 전체 크기 5 중에서 1개만 차 있으므로 적재율은 1/5이 되는 것이다. 주로 load factor는 α로 표현하는 경우가 많다.
4. 충돌을 막기 위한 방법
또한 위에서도 언급했듯이 충돌이 일어나면 해시 테이블의 성능은 굉장히 안좋아지기 때문에 이를 해결할 수 있는 방법이 필요하다.
충돌을 막기 위한 방법으로 chaining이라는 방법과 open addressing이라는 방법이 존재한다.
이 두 방법은 다음 포스팅에서 소개하도록 하겠다.