commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael A. Smith" <...@apache.org>
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:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_func.html

Here's another reference that talks about this, but mentions a drawback 
to Knuth's multiplication method:
http://www.cris.com/~Ttwang/tech/inthash.htm

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:

http://nagoya.apache.org/eyebrowse/ReadMsg?listName=commons-dev@jakarta.apache.org&msgNo=10390

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

regards,
michael



--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message