Re: suggestion for dictionary representation

[Daniel Berlin <dberlin@dberlin.org>]

> 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.


> (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.