HashTable vs Binary Search Tree

HashTable vs Binary Search Tree

Criteria	Binary Search Tree	HashTable
Time Complexity(Insertion / Deletion / Searching)	O(nlogN)	O(1)
Sorted Order	데이터가 삽입시 부터 정렬되어 있음. 중위 순회를 하면 정렬된 데이터가 나옴.	데이터가 랜덤한 형태로 저장되어 있음(해시값 이용). 만약 Sort 하려면 추출해서 Sort 해야함
Hash Function	X	O(1) 시간에 수행하기 위해서는 적절하게 키를 생성해내는 Hash Function 이 필요
Collsion	X	충돌 발생시 Chaining 이나, Open Address 방법을 이용
Input Data Size	딱히 Input Size 를 알아야 할 Needs 는 없음	HashTable 을 구성하기 전에 input Size 를 알아야 함
Range Search	BST 에서 Range Search 는 정렬되어 있으므로 빠름	HashTable 은 RangeSearch 는 느리고, Single Search 에 유리

적절한 사용처

• Range Search: Hash Table 에서 Range Search 를 하는 것은 사실상 전체 테이블을 전부 다 보는 것과 비슷한 비용이므로, 적절하지 않다. Binary Search Tree 를 이용하면, 몇몇의 Sub Tree 들은 Ignore 할 수 있게 되므로, Range Search 에 유리하다. 따라서 자신이 Range Search 를 구성해야 한다면, 이 상황에서는 Hash Table 보다는 BST 가 유리할 것이다.
• Cache-Freindly: 만약 Cache-Friendly 한 Application 을 만든다면, Hash Table 을 사용하는게 메모리적으로 유리하다. (예를 들면, Redis Application)
• Hash Function: 만약 Hash Function 으로 균일하게 분배되는 Key 를 만들기 쉬운구조라면, Hash Table 을 이용하면 유리하고, Hash Function 을 통해 균일하게 분배되는 키를 얻기 힘들다면 (Collision Rate 가 높을 것 같다면) BST 를 사용하는게 유리할 수도 있다.
• Dicitionary: 사전식의 Key-Value Search 를 원한다면 Hash Table 을 사용하는게 좋다.

내 생각

일단 중요한건 대부분 Search 를 위주로 어떻게 Optimize 할 것이냐에 따라서 고르면 될것 같다. Range Search 가 중요하다면 BST 로 구성하고, 그게 아닌 Dictionary 형태로 Optimization 이 가능하다면 Hash Table 을 이용하면 좋을 것 같다.

Reference

• https://afteracademy.com/blog/binary-search-tree-vs-hash-table