해시테이블과 이진 검색트리의 장단점 비교

1. 정의

1) 해시테이블: 키-밸류로 데이터를 저장하는 자료구조 중 하나로  빠르게 데이터를 검색할 수 있고, 내부적으로 배열(버킷)을 사용하여 데이터를 저장한다. 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

 

2) 이진검색트리: 키-밸류로 데이터를 저장하는 자료구조 중 하나로 이진검색과 연결리스트(Linked list)를 결합한 자료구조이며 이진검색의 효율적인 탐색능력을 유지하면서도, 번번한 자료 입력과 삭제를 가능하게끔 고안되었다. 정렬된 이진트리라고 생각하면 되며 중복된 키를 허용하지 않는다.

 

 

2. 장단점

1) 해시테이블

• 장점: 데이터 저장/읽기 속도가 빠르며, 중복 데이터 확인이 쉽고 충돌이 없다면 시간복잡도 O(1)로 짧다.
• 단점: 일반적으로 저장공간을 많이 차지하며, 여러 키에 해당하는 주소가 동일한 경우 충돌 해결을 위한 별도의 자료구조가 필요하다. 데이터 충돌이 발생한다면 O(N)까지 시간복잡도가 발생할 수 있다.

2) 이진검색트리

• 장점: 입력시 값에 따라 곧바로 위치가 지정되기 떄문에 데이터 검색 속도가 빠르며 숫자값 검색이 잦을 경우에 유리하다.
• 단점: 최악의 경우에 한쪽으로만 이어질 수 있으며 자료가 많아질 수록 트리의 높이가 커지기 때문에 검색에 불리해지고 최악의 경우 특정노드를 탐색하는 데에 log(n)이 걸릴수 있다.

3. 결론

• 이진 검색트리는 딱 필요한 원소만큼의 공간만을 할당하는 반면, 해시 테이블은 해시 적중률을 높이기 위해 원소의 개수 이상의 메모리를 유지해야 한다. 따라서 사용량 측면에선 이진검색트리가 유리하다.
•  문자열과 같은 데이터를 다루는 상황이나, 순서와 밀접한 연관이 있는 데이터를 다루는 상황에선 이진검색트리가 유리하고, 데이터가 엄청 많아지는 경우엔 비용측면에서 성능최적화 면에서 해시테이블이 유리하다.
• 캐시적중률 면에선 이진검색트리는 노드 기반의 자료구조로 메모리 파편화가 진행되어 캐시 적중률이 떨어지게 된다. 반면, 해시테이블은 배열기반 자료구조로 연속된 메모리를 유지하기 때문에 캐시 적중률이 상당히 높다.