Messages in this thread | | | Subject | Re: 2.2.6_andrea2.bz2 | From | (Harvey J. Stein) | Date | 02 May 1999 00:23:23 +0300 |
| |
"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/
| |