develooper Front page | perl.perl5.porters | Postings from April 2000

Who invented storing hash values in hash table?

Thread Next
Mark-Jason Dominus
April 26, 2000 07:07
Who invented storing hash values in hash table?
Message ID:

When a key-value pair is stored in a Perl hash, the hash value for the
key is stored with it.  Then, when Perl is looking up a key, and finds
something in the bucket, it compares the hash values first, and only
compares the found key with the desired key if the hash values match.
This avoids many unnecessary string compares.

Folks on the mailing list for Dan Bernstein's CDB (constant database)
package are discussing how that works, and one of them mentioned:

        Incidentally, I don't know if Dan invented this brilliant
        idea.  It doesn't seem to be in Knuth.

I said that this innovation is in Perl 1, and was probably not new
then.  But I was surprised that it wasn't in Knuth---that suggests
that it is a more recent idea than one would have expected, perhaps
from the 1970s.  Does anyone know when this was invented or by whom or
remember seeing this idea used in anything that predates Perl?

Mark-Jason Dominus 	  			       
I am boycotting Amazon. See for details.

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About