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

[fdmfdmfdm]

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?

 

[Ben Pfaff]

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.

 

[Christopher Layne]

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?

 

[CBFalconer]

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

 

[user923005]

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

 

[Lane Straatman]

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

 

[user923005]

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.