Efficient STRing CoMPares?

[Paul F Smith]

In article <1991Mar20.235613.20480 at athena.mit.edu> scs at adam.mit.edu writes:
>In article <1991Mar20.213615.11223 at noose.ecn.purdue.edu> psmith at iies.ecn.purdue.edu (Paul F Smith) writes:
>>...could you 
>>please elaborate on how your symbol table works. I just implemented a
>>hash table that keeps the hash value around (like your struct above), 
>>which I then use in scanning the list at the given bucket to minimize
>>strcmp()s.  But, I can't see how you can get rid of it and still reduce 
>>the number of strcmp()s. Please describe, Thanks!
>
>Well, I didn't say the number of strcmp's was reduced to 1.
>Hashing has done its work (i.e. eliminated a lot of strcmp's and
>associated searching) when it has computed the right bucket to
>look in; there aren't supposed to be large numbers of collisions
>to scan over.  

Ok. You were just talking about the normal effect of a hash table.
I used a hash table, but for each entry I keep the full hash value
to try and keep the # of strcmp()s close to 1. Like this...

>
>for(step = stp->st_hashtab[h]; step != NULL; step = step->st_next)
>	{
>	if(strcmp(step->st_name, name) == 0)

Instead I do:
(compute "hash(name)" once at the beginning)

if((step->hashval == hash(name)) && strcmp(step->st_name, name) == 0)

>		return step;
>	}
>

I thought you had achieved this property without keep the hashvalue with
the symbol entry. (wouldn't that be nice!)

I think this reduction in strcmp()s is worth the space. Does anyone
know of a reason that it isn't? (other than not having enough space :-)

Thanks for the reply!

--
------------------------------------------------------------------
Paul F. Smith - ADPC - Purdue University     psmith at ecn.purdue.edu
<someday I'll think of something profound to put here, maybe>