Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 630 invoked from network); 20 Jun 2002 18:09:32 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 20 Jun 2002 18:09:32 -0000 Received: (qmail 17087 invoked by uid 97); 20 Jun 2002 18:09:04 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 16980 invoked by uid 97); 20 Jun 2002 18:09:04 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 16892 invoked by uid 98); 20 Jun 2002 18:09:03 -0000 X-Antivirus: nagoya (v4198 created Apr 24 2002) X-Qmail-Scanner-Mail-From: baliuka@centras.lt via jim.skynet.vl X-Qmail-Scanner: 1.03 (Clean. Processed in 1.359585 secs) Message-ID: <00db01c21885$88433ca0$0111010a@user> From: "Juozas Baliuka" To: "Jakarta Commons Developers List" , References: <005a01c21884$434f5ee0$ac00a8c0@Gabriel> Subject: Re: [Collection] algorythms was [Commons-Avalon:collections] code integration Date: Thu, 20 Jun 2002 20:08:49 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N 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: > > > > > For additional commands, e-mail: > > > > > > > > > > > -- > > To unsubscribe, e-mail: > > unsubscribe@jakarta.apache.org> > > For > > additional commands, > > e-mail: > > > > > -- > To unsubscribe, e-mail: > For additional commands, e-mail: > -- To unsubscribe, e-mail: For additional commands, e-mail: