Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!sdd.hp.com!samsung!noose.ecn.purdue.edu!iies.ecn.purdue.edu!psmith
From: psmith@iies.ecn.purdue.edu (Paul F Smith)
Newsgroups: comp.lang.c
Subject: Re: Efficient STRing CoMPares?
Message-ID: <1991Mar21.160607.5742@noose.ecn.purdue.edu>
Date: 21 Mar 91 16:06:07 GMT
References: <1991Mar20.020957.9180@athena.mit.edu> <1991Mar20.213615.11223@noose.ecn.purdue.edu> <1991Mar20.235613.20480@athena.mit.edu>
Sender: root@noose.ecn.purdue.edu (ECN System Management)
Organization: ADPC, Purdue University
Lines: 45

In article <1991Mar20.235613.20480@athena.mit.edu> scs@adam.mit.edu writes:
>In article <1991Mar20.213615.11223@noose.ecn.purdue.edu> psmith@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@ecn.purdue.edu
<someday I'll think of something profound to put here, maybe>