×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

Comparison between Hash Table and Binary Search Tree

In this article we are going to see the comparison between the two different data structures hash table and Binary search tree.
Submitted by Radib Kar, on September 19, 2020

Comparison b/w operation in hash table & Binary Search Tree

  1. Insertion:
    Insertion in a hash table is less expensive that insertion in a Binary Search Tree. Insertion in hash table in O(1) which is constant time whereas insertion in a Binary search Tree is O(logn)( Considering the self-balancing BST).
  2. Deletion:
    Deletion in a hash table is less expensive that deletion in a Binary Search Tree. Deletion in hash table in O(1) which is constant time whereas deletion in a Binary search Tree is O(logn)( Considering the self-balancing BST)
  3. Searching:
    Searching in hash table is also less expensive as searching in BST is also of logarithmic complexity but hash table has constant time complexity.
  4. Sorting
    Inorder traversal of the BST produces a sorted list. Hash table doesn't guarantee any such sorted list.(Don't think about map, map is not a hash table, map is actually implemented with self-balancing tree).
Operation Hash table Binary Search Table
Insertion O(1) O(logn)
Deletion O(1) O(logn)
Search O(1) O(logn)


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.