lkml.org 
[lkml]   [1999]   [May]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: 2.2.6_andrea2.bz2
From
Date

"Stephen C. Tweedie" <sct@redhat.com> writes:

> In other words, I can throw memory at hashing to make it faster,
> but trees have a fixed cost which necessarily grows with their
> size.

Well, sort of. If you assume your hash function is sufficiently good,
then yes. But this is a pretty strong assumption. On the other hand,
2^20 = 1048576, so if you're storing < 1 million objects, you've got
at worst 20 nodes to go through in a balanced tree. For a red-black
tree the lack of balance gives you a factor of 2 in the max path
length. So, at worst you have to go through 40 nodes for a million
objects.

With hash tables you can, for example, go from size N to size 2N
whenever you have more than 3N items, which is still O(1) on average,
but will take significant time on the (rare) occasions of doubling the
table size. But, even when you do this, you're only guaranteeing an
average bucket size <3, and if you happen into a pathological situation
(everything hashing to the same #), you'll have O(N) access times no
matter what you do to the hash table size. It's true you'll have ~3
nodes to walk in the average case, but you might also end up with
complaints of a system being dog slow which ends up being traced to a
hashing failure because of a particular program's memory usage. Not
to mention system exploits based on hashing failures.

Trees basically have worse average behavior but better worst case
behavior. Part of the decision depends on how good a hash function
you can find, and to what extent you're willing to live with its
failures. But trees could still be handy even if they're slower. For
example, if you really need the ordering that trees maintain (maybe
for the elevator algorithm for disk i/o), then they could be a big win
even if they're slower for the average case.

--
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.584 / U:0.300 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site