commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael A. Smith" <...@apache.org>
Subject RE: [Collection] algorythms was [Commons-Avalon:collections] code integration
Date Thu, 20 Jun 2002 18:15:10 GMT
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:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message