[Algorithm] Hash Table vs Binary Search Tree 비교

Binary Search Tree vs Hash Table

기본적으로 Binary Search Tree와 Hash Table은 모두 키 & 값 형태로 자료를 저장하는 자료구조이다.

그렇기 때문에 사용성 측면에서는 굉장히 유사한 인터페이스를 갖고 있고, 지원하는 연산들도 아주 흡사하다.

그런 이유로, 자주 비교대상이 되는 자료구조로써 각각의 장단점을 한번쯤 정리해볼 필요가 있다.

 

기능적인 측면

 

탐색, 삭제, 삽입과 같은 기본기능들에 대해서,

해시 테이블 : O(1) 

이진탐색트리 : O(logN)

정도 성능으로 동작한다.

해시 테이블의 해시 함수의 비용과, 충돌 해결비용까지 고려하더라도 데이터가 엄청 많아지는 경우에는 해시 테이블이 효과적이라고 볼 수 있다. 그리고 만약 입력 사이즈를 알고 있다면, 입력 사이즈에 맞게 최적화된 해시 함수를 이용하여 해시 테이블의 해시 값을 균일하게 분포시켜서 성능을 최적화시킬 수 있을 것이다.

 

하지만 이진탐색트리에는 데이터들의 순서가 정렬된 상태로 유지된다는 강력한 장점이 있다.

이 특성으로 인해 데이터를 정렬된 형태로 순회할 수 있다는 장점도 있겠지만,

아주 좋은 성능으로 범위기반 쿼리가 가능하다는 장점도 있다.

그러므로 순서와 밀접한 연관이 있는 데이터를 다루는 상황에서는 이진탐색트리가 효과적일 것이다.

또한 문자열과 같은 데이터를 다루는 상황에서는 키의 동등 비교를 수행하는 해시 테이블보다, 키의 크기 비교를 수행하는 이진트리가 유리할 것이다.

 

메모리 측면

 

메모리 사용량

이진탐색트리는 딱 필요한 원소 만큼의 공간만을 할당하는 반면, 해시 테이블은 해시 적중률을 높이기 위해 원소의 개수 이상의 메모리를 유지해야한다. 그러므로 사용량 측면에서는 이진탐색트리가 유리하다.

 

캐시 적중률

이진탐색트리는 노드 기반 자료구조로 메모리 파편화가 진행되어 캐시 적중률이 떨어지게 된다.

반면, 해시 테이블은 배열 기반 자료구조로 연속된 메모리를 유지하기 때문에 캐시 적중률이 상당히 높다.

 

 

결론

두 자료구조는 외부적으로는 키&값을 사용하는 자료구조로 굉장히 흡사한 인터페이스를 갖고 있지만,

내부적으로는 완전히 다른 형태로 데이터를 관리한다. 그렇기 때문에 어떤 자료구조가 반드시 더 좋다고 결론을 지을 수는 없고, 데이터의 형태나, 환경, 상황에 맞게 적절한 자료구조를 선택하는것이 좋을 것이다.