해쉬맵의 단점

우선 그 전에 다루었던 단점은 전 글에서도 다루었고, 찾아보면 많이 나오기 때문에, 간단하게만 짚고, 다른 이유들에 대해

써보려고 합니다.

해시 충돌

해시 충돌이란, 동일한 해시값을 갖는 것이 많을때, 로우체이닝 혹은 개방주소법으로 치환하는데,

극단적으로 한곳에 몰릴 경우 O(N) 의 시간복잡도로 변경이 됩니다.

재 해싱

해시 충돌이 많아질 경우, 해시 메모리를 2배로 늘려 새로 해시 테이블을 만듭니다.

이경우 O(N) 의 시간복잡도가 들어갑니다.

순서가없다

물론 해시를 사용한다면, 애초에 순서 없이, 빠른 삽입, 탐색을 위해 사용 하는 것이 대부분 일텐데요,

순서가 없다는 점으로 인해서, 정렬이 불가능 하고,

정렬이 필요한 경우에는 해쉬맵을 사용 하면 안됩니다.

또한, 그로인해 DB에서 해쉬를 사용 할 시 인덱스 정렬에 문제가 생겨서

해시조인을 위해 임의로 만드는 경우가 아닌 한, 해시를 사용 하지 않습니다.

(이러한 이유로 파일시스템에서는 해시가 아닌 B-Tree 를 사용합니다. )

또한 빈공간이 아무래도 많이 생성 됩니다.

그럼 어떤일이 일어날까요?

전체 순회를 하려고 한다면, 모든 해시테이블을 뒤져봐야 합니다.

값이 들어있지 않은 주소도, 일일이 값이 들어있는지, 들어있지 않은지에 대한 탐색을 필요로 합니다.

물론 크게 시간이 드는 작업은 아니지만, 해시테이블의 크기가 크다면,

그만큼 시간이 많이 들어 가게 되죠.

함수형 언어에서의 문제점

기본적으로 해시는 destructive update 를 사용하는 만큼, 함수형 언어에서는 사용 하지 않습니다.

함수형 언어는

 int a = 1;
 a = a + 1;

이런식으로 코드를 짜면, 에러가 날 수도 있습니다.

a = (a ( a ( a ….. ) +1 ) +1 )+1 ) +1

이런식으로 치환되며 무한으로 넘어가게 되기 때문입니다.

즉 이런식으로 메모리를 갱신하는 것을 지양 합니다.

그래서 만약 함수형 언어에서 빠른 탐색이 필요로 한다면,

노드 자체에 부여하는 레드블랙노드트리, AVL트리 처럼

이진트리를 사용하는 일이 많습니다.