RE: [Collection] algorythms was [Commons-Avalon:collections] code integration

[Juozas Baliuka <ba...@mwm.lt>]

Hi,
I as understand all of them are almost the same,
I need "fast" iteration and "add", I am not expert, but there are a lot of 
books,
I believe it is possible to implement "faster" Set for iteration.

At 13:15 2002.06.20 -0500, Michael A. Smith wrote:
>On Thu, 20 Jun 2002, Berin Loritsch wrote:
> > > 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...
>
>double hashing and linear probing are two different methods for
>resolving collisions in the hashtable.  Double hashing is a technique
>where you use two different hashing algorithms to determine two
>difffernt likely bucks that an element may be located.  Linear probing
>involves putting an element in the "next empty bucket" if the hashed
>bucket is already taken.  The implementation used here (and in java.util
>implementaions) is direct chaining hashing, where elements of the bucket
>are actually linked lists of the elements whose hashcode maps to
>that bucket.
>
>Linear probing and double hashing do not allow the number of
>elements to exceed the number of buckets in the hashtable and thus are
>not really appropriate for this collection.
>
>regards
>michael
>
>
>--
>To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
>For additional commands, e-mail: <ma...@jakarta.apache.org>



--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>