commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Juozas Baliuka" <bali...@centras.lt>
Subject Re: [Collection] algorythms was [Commons-Avalon:collections] code integration
Date Thu, 20 Jun 2002 18:08:49 GMT
I will implement Set interface based on this algorythm, It besause need
"fast" implementation for "large" sets, I will try to implement Set based on
your Map
too. I will submit this implementation if it will be "faster".

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


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