commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Berin Loritsch" <blorit...@apache.org>
Subject RE: [Collection] algorythms was [Commons-Avalon:collections] code integration
Date Thu, 20 Jun 2002 17:59:45 GMT
> From: Juozas Baliuka [mailto:baliuka@centras.lt] 
> 
> Ok,
> I see it is "linear probing".
> We can implement "double hashing" I am not sure it is 
> somethin better, but my book says "double hashing" is better 
> it says "Empyricaly proved", I don't believe empyric, but we 
> can try it.


Ok. I guess.  But please keep the original as a reference.

I'm not sure what the difference is between them, but I can
tell you this: the less work done on each lookup, the quicker
the Map works.  Using the hashCode as an index to the array
is about as fast as it gets.

It might be something like the difference between LinkedList
and ArrayList.

Up to a certain number of elements, ArrayList smokes (or at
least beats) the LinkedList.  After that threshold, LinkedList
wins.  However, that threshold is so high in JDK 1.3/1.4
Hotspot JVMs that you'd be better off with ArrayList in 99%
of all applications.

Just something to think about before going down that road...

> 
> > > From: Juozas Baliuka [mailto:baliuka@centras.lt]
> > >
> > > Hi,
> > > I want to ask about Map implementation (BucketMap).
> > > Is it like HashMap (linear probing) or something different like 
> > > "double hashing". If it is "linear probing", is it plans to 
> > > implement alternatyve algorythms ?
> >
> > Not sure what you mean.  My implementation was rather simplistic.  
> > Basically there is an array of buckets. Each Bucket 
> represents a hash 
> > value (hashCode() % n). Synchronization occurs on the bucket.
> >
> > I don't pretend to be an algorithmic genious.  I just
> > hacked it together and saw it did a better job than
> > HashMap at removing the race conditions (because
> > HashMap is not threadsafe), and better than a
> > Synchronized Map because there was less thread contention.
> >
> > Anything more than that, I couldn't tell you.  I actually
> > got the algorithm I used from a magazine article, and
> > hacked in the Map support that you do see in there.
> >
> >
> > --
> > To unsubscribe, e-mail:
> <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> > For additional commands, e-mail:
> <mailto:commons-dev-help@jakarta.apache.org>
> >
> 
> 
> --
> To unsubscribe, e-mail:   
> <mailto:commons-dev-> unsubscribe@jakarta.apache.org>
> For 
> additional commands, 
> e-mail: <mailto:commons-dev-help@jakarta.apache.org>
> 


--
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