473,320 Members | 1,945 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

What's the difference of hash table and binary tree?

This might not be the best place to post this topic, but I assume most
of the experts in C shall know this.

This is an interview question. My answer is:

hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the contrary,
binary tree gives you O(logN) searching but less memory.

Am I right?

Feb 6 '07 #1
6 16818
"fd*******@gmail.com" <fd*******@gmail.comwrites:
hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the contrary,
binary tree gives you O(logN) searching but less memory.
The memory used by many implementations of hash tables and binary
search trees is fixed for a given number of elements. That is,
in many implementations, the hash function has no effect on an
N-element hash table's memory usage, and the particular content
of an N-element binary search tree has no effect on the BTS's
memory usage.

I'd guess that, in fact, it's easier to optimize the memory usage
of a hash table than of a binary search tree, especially if
you're willing to let the hash table slow down a little (while
remaining O(1) average time). But I haven't made a study of it.
--
"It would be a much better example of undefined behavior
if the behavior were undefined."
--Michael Rubenstein
Feb 6 '07 #2
fd*******@gmail.com wrote:
hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the contrary,
binary tree gives you O(logN) searching but less memory.

Am I right?
One large difference is that ability to preserve some fundamental kind of
order with a tree and have a traversal reflect this.

Table of last names and you want to search them. Hash or binary tree are both
fine. Now what if you've got a partial last name you want to search - which
method do you think will be most efficient?
Feb 6 '07 #3
On Feb 5, 10:16 pm, "fdmfdm...@gmail.com" <fdmfdm...@gmail.comwrote:
This might not be the best place to post this topic, but I assume most
of the experts in C shall know this.

This is an interview question. My answer is:

hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the contrary,
binary tree gives you O(logN) searching but less memory.

Am I right?
The most important difference (besides hash tables being faster)
between hash tables and btrees is that hash tables only find on
equality searches.
Btrees can do range searches with things like <, >, <=, >=, between,
etc.

Your post is better aimed at a group like news:comp.programming

Feb 6 '07 #4
Christopher Layne wrote:
fd*******@gmail.com wrote:
>hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the
contrary, binary tree gives you O(logN) searching but less memory.

Am I right?

One large difference is that ability to preserve some fundamental
kind of order with a tree and have a traversal reflect this.

Table of last names and you want to search them. Hash or binary
tree are both fine. Now what if you've got a partial last name
you want to search - which method do you think will be most
efficient?
The binary tree requires considerably more care to avoid a worst
case O(N) operation, since it is easily fed a sorted list on input.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
Feb 6 '07 #5

"CBFalconer" <cb********@yahoo.comwrote in message
news:45***************@yahoo.com...
Christopher Layne wrote:
>fd*******@gmail.com wrote:
>>hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the
contrary, binary tree gives you O(logN) searching but less memory.

Am I right?

One large difference is that ability to preserve some fundamental
kind of order with a tree and have a traversal reflect this.

Table of last names and you want to search them. Hash or binary
tree are both fine. Now what if you've got a partial last name
you want to search - which method do you think will be most
efficient?

The binary tree requires considerably more care to avoid a worst
case O(N) operation, since it is easily fed a sorted list on input.
Why does not every sort of size, say, greater than fifty, permute the input
randomly from the get-go? There isn't anything theoretically difficult in
doing so. LS
Feb 6 '07 #6
On Feb 6, 1:56 am, "Lane Straatman" <inva...@invalid.netwrote:
"CBFalconer" <cbfalco...@yahoo.comwrote in message

news:45***************@yahoo.com...
Christopher Layne wrote:
fdmfdm...@gmail.com wrote:
>hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the
contrary, binary tree gives you O(logN) searching but less memory.
>Am I right?
One large difference is that ability to preserve some fundamental
kind of order with a tree and have a traversal reflect this.
Table of last names and you want to search them. Hash or binary
tree are both fine. Now what if you've got a partial last name
you want to search - which method do you think will be most
efficient?
The binary tree requires considerably more care to avoid a worst
case O(N) operation, since it is easily fed a sorted list on input.

Why does not every sort of size, say, greater than fifty, permute the input
randomly from the get-go? There isn't anything theoretically difficult in
doing so. LS
Skiplists do that. Some trees are self-balancing (AVL, Red-Black,
Weak Heaps...). A pure binary tree that does not self-balance is a
rarity in common usage where sorted distributions are likely to occur
anyway.

Feb 6 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

22
by: Tony Johansson | last post by:
Hello Experts! I'm reading i a book about C++ and they mention infix with telling what it is. I hope you out there can do so. Many thanks! //Tony
7
by: exonic | last post by:
I'm reposting this, as everyone went off on the "did this say c++" tangent, when someone thought he was reading a different group. Hope I get better results this time. I need an efficient...
11
by: Angus Comber | last post by:
Hello I want to create a lookup table where I can store string keys: For example: 192.168.0.1 -> Purple 192.168.0.2 -> Blue 192.168.0.3 -> Red
5
by: pembed2003 | last post by:
Hi, I have a question about how to walk a binary tree. Suppose that I have this binary tree: 8 / \ 5 16 / \ / \ 3 7 9 22 / \ / \ / \
21
by: Helge Jensen | last post by:
I've got some data that has Set structure, that is membership, insert and delete is fast (O(1), hashing). I can't find a System.Collections interface that matches the operations naturally offered...
8
by: sandeep | last post by:
Our team is developing proxy server(in VC++)which can handle 5000 clients. I have to implement cache part so when ever a new request com from client I have to check the request URL content is in...
1
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template...
2
by: db2db2db2 | last post by:
hello all, we know that db2 create index using B-Tree,but if i want to create index using hash structure,how can i do it? in my opinion, db2 usually create index using B-tree,my question is if db2...
7
by: Vinodh | last post by:
Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.