Re: suggestion for dictionary representation

[David Carlton <carlton@math.stanford.edu>]

On Tue, 24 Sep 2002 13:42:18 -0400, Daniel Berlin <dberlin@dberlin.org> said:

> (Who the heck thought it would be smart to have a big Oh and little
> Oh, fer instance)

:-)

> If your average chain lengths go above log n (the number of keys
> we'd have to strcmp in the skiplist), which in fact, for large
> files, they were, then the skiplist will likely be better, because
> it'll perform less comparisons, *and* doesn't have do to the hash
> function calculation.

I'm not entirely sure I understand your assumptions in this last
paragraph; are you assuming the number of buckets will remain
constant?  I think that, if we're going to use hash tables for global
symbols, we'll want to resize the hash tables as necessary.  My
apologies for not making that clear; that's why I said that hash
tables were amortized O(n) rather than just O(n).  (But this is, of
course, yet another way that the constant factor for hash tables could
be larger than one might like.)

> I would actually suggest neither hash tables or skiplists, but
> ternary search trees.

Thanks for the references; I'll give them a look.

David Carlton
carlton@math.stanford.edu