해싱의 성능 분석

• 해싱의 성능 분석
  

해싱의 시간 복잡도는 이다. 그러나 이것은 충돌이 전혀 일어나지 않는 상황에서만 가능하다. 따라서 실제 해싱의 탐색 연산은 보다는 느려지게 된다. 해싱의 성능을 분석하기 위해 해시 테이블이 얼마나 채워져 있는지를 나타내것을 적재 밀도(loading density) 또는 적재 비율(loading factor) 라 한다.

* n = 저장된 항목의 개수, M = 해싱 테이블의 버켓의 개수

가 0 이면 해시 테이블은 비어있다. 의 최댓값은 충동 해결 방법에 따라 달라지는데, 선형 조사법에서는 테이블이 가득하면 모든 버켓에 하나의 항목이 저장되므로 1이 된다. 체인법에서는 저장할 수 있는 항목의 수가 해시 테이블의 크기를 넘어설 수 있기 때문에 는 최댓값을 가지지 않는다.

기존의 연구 결과들을 바탕으로 해싱을 정리해보자. 머저 선형 조사법은 적재 밀도를 0.5이하로 유지해야 한다. 이차 조사법과 이중 해싱법에서는 적재 밀도를 0.7 이하로 유지시키는 것이 좋다고 한다. 체인법은 적재 밀도에 비례하는 성능을 보인다. 성능을 저하시키지 않고 얼마든지 저장할 수 있는 요소릐 개수를 늘릴 수 있다는 것이 장점이다. 링크를 위한 메모리 낭비 문제는 저장되는 자료의 크기에 따라 달라진다.

• 해싱과 다른 탐색 방법의 비교

해싱을 배열을 이용하는 이진 탐색과 비교하여 보면 해싱이 일반적으로 빠르다. 또한 삽입이 어려운 이진 탐색과는 달리 해싱은 삽입이 쉽다.

해싱을 이진 탐색 트리와 비교하여 보면 이진 탐색 트리는 현재 값보다 다음으로 큰 값이나 다음으로 작은 값을 쉽게 찾을 수 있는 장점이 있다. 또한 이진 탐색 트리에서는 값의 크기순으로 순회하는 것이 쉽다. 이에 반하여 해싱은 그야말로 순서가 없다. 또한 해시 테이블에 초기에 얼마나 공간을 할당해야 되는지가 불명확하다. 또한 해싱은 최악의 시간 복잡도가 아주 나쁘다. 최악의 경우는 모든 값이 하나의 버킷으로 집중되는 것으로 이 경우 시간 복잡도는 이 될 것이다. 따라서 아주 심각한 응용에는 부적절한 방법이다. 다음은 여러 가지 탐색 방법들의 시간 복잡도를 정리해서 보여주고 있다.

탐색 방법		탐색	삽입	삭제
순차 탐색
이진 탐색
이진 탐색 트리	균형 트리
	경사 트리
해싱	최선의 경우
	최악의 경우