In: Computer Science
Compare and Contrast Hash Map to Binary Search Tree.
Memory, Time Efficiency for Operations for Retrieving Singular Values, Maintaining relationships between data.
Please be sure to use your own words.
To begin with definition, HashMap is a datastructure for storing key value pairs while Binary Search Tree is used for saving data in ordered manner. HashMap uses hashtable for storing data while Binary Search Tree uses a Binary Tree to store the data.
Memory:
Hashmap - O(n) as hashtable will be atmost of size 2*n.
Binary Search Tree - O(n) as For every data point we have single node and every node takes constant space so order of n.
Retreiving Singular Values/Search:
Hashmap - O(1) Asumming reasonably good hash function is used we can assume that search can be done in constant time.
Binary Search Tree - O(log n). Assuming BST is balanced we can retrieve values in atmost log n time.
Maintaining relationships between data:
Hashmap natively provides support for storing key value pairs i.e. related data.
For BST we need to implement custom node class and define their comparator to be able to maintain relationship between data while maintaining BST structure.