"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