commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael A. Smith" <>
Subject RE: [Collections][SUBMIT] ReferenceMap...take 3...
Date Sat, 20 Jul 2002 01:49:49 GMT
On Fri, 19 Jul 2002, Michael A. Smith wrote:
> On Fri, 19 Jul 2002, Jack, Paul wrote:
> > Hm.  I couldn't really find my way around the above page.  It definitely
> > has a lot of good stuff but it's organized chronologically, so I couldn't
> > find specific things related to hash functions... I'll keep looking.
> My Intro to Algorithms book lists a "Multiplication Method" that should
> work well.  Don't have the book with me at the moment, but I'll try to 
> summarize tonight...

rather than try explaining it, here's a reference that says pretty much 
the same thing:

Here's another reference that talks about this, but mentions a drawback 
to Knuth's multiplication method:

One suggestion in that second reference is to use:

int inthash(int key)
  key += ~(key << 15);
  key ^=  (key >>> 10);
  key +=  (key << 3);
  key ^=  (key >>> 6);
  key += ~(key << 11);
  key ^=  (key >>> 16);
  return key;

This bit-mixing type function looks similar to what Berin used in
Avalon's BucketMap (modifications made after we imported our version).  
I mentioned that on the list last week sometime.  Apparantly Beric took
it from the JDK, which probably isn't the best idea:

That version uses less operations to determine the key, but I can't find 
a reference for it to argue its effectiveness. 


To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message