[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: A good hash algorithm
- From: RLake@...
- Date: Tue, 18 Jun 2002 16:13:54 -0500
> But don't you still need to do a O(1,000,000) string compare on
> potentially each of the 20 strings?
You only need to do the string compare once, when the string is first
interned. After that, the comparison is by address. I'm assuming that a
program which used enormous strings as keys would enter new keys only
rarely compared with the number of table accesses.
Even so, it is highly likely that the difference will be encountered early
in unequal strings. Equal strings will of course require the full megabyte
comparison, but that would be true regardless of the hashing algorithm used
(unless one chose to be allow very-low-probability bugs with an MD5-type
hashing algorithm; personally, I would find that unacceptable, though.)