Algorithm
HashTable vs Binary Search Tree
dev_roach
2022. 8. 27. 20:15
728x90
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 을 이용하면 좋을 것 같다.