More efficient: BST or Hash search??

This is a discussion on More efficient: BST or Hash search?? within the C Programming forums, part of the General Programming Boards category; Hi, Does anyone know which search is more efficient, the hash table search or the Binary Search Tree search..Respond only ...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    63

    Question More efficient: BST or Hash search??

    Hi,
    Does anyone know which search is more efficient, the hash table search or the Binary Search Tree search..Respond only if you're confident of your answer. If possible, please also explain. Thanks.
    A

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    For a properly designed hash table access is O(1).
    If not designed right worse case is O(n). binary search trees
    average case is O(lg n) and worse case is O(n).
    You will have to get a book to see a fuller explanation.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Does anyone know which search is more efficient, the hash table search or the Binary Search Tree search..
    It depends on the tree structure you're using and the quality of your hash table implementation. A balanced binary tree has an O(log n) search complexity while a well made hash table has O(1) complexity. So if both are made well then the hash table will be more efficient for searching.

    >Respond only if you're confident of your answer.
    Of course, I could be wrong.

    -Prelude
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    63
    Thanks guys..any more responses anyone?
    A

  5. #5
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    Sure!
    Do your own homework. Learn to use a search engine. If this is not homework and you want to know what to use for your code then go with the hashed structure.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Hash Array Index Search
    By NavyBlue in forum C Programming
    Replies: 3
    Last Post: 10-10-2002, 03:02 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21