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

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.