Re: suggestion for dictionary representation

[Daniel Jacobowitz <drow@mvista.com>]

On Mon, Sep 23, 2002 at 08:34:50PM -0400, Daniel Berlin wrote:
> >I'm also curious about how it would affect the speed of reading in
> >symbols.  Right now, that should be O(n), where n is the number of
> >global symbols, right?
> 
> > If we used expandable hash tables, then I
> >think it would be amortized O(n) and with the constant factor larger.
> 
> Nope.
> Our string hash function is O(N) right now (as are most). Hash tables 
> are only O(N) when the hash function is O(1).
> 
> Now, if you have it only hash the first x characters, you can make your 
> hash table O(N) again, with the x as the constant. Of course, if only 
> hashing the first x characters causes tons of hash conflicts, it's not 
> going to make your hash table very fast.

Wait a second... aren't you switching N's on us?  N is the number of
global symbols.  We're talking about the total time of adding all
symbols to the table.  Hashing a string is "effectively" constant time,
because all string lengths are "small".

> >(But, I think, not larger in a way that would make a difference.)  I'm
> >curious about how often the "amortized" bit would lead to strange
> >hiccups, but I don't think that's a big deal.
> >
> >But for skip lists, wouldn't it be something like O(n log n)?  If so,
> >that's an issue we have to consider.
> 
> Put it in perspective.
> for 1 billion symbols, n is 29.89.
> for 1 million symbols, n is 19.93.

You mean "log n", of course.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer