Re: suggestion for dictionary representation

Daniel Berlin
2002-09-24T00:34:56Z

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