Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 92903 invoked from network); 20 Jun 2002 18:00:17 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 20 Jun 2002 18:00:17 -0000 Received: (qmail 28404 invoked by uid 97); 20 Jun 2002 18:00:24 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 28388 invoked by uid 97); 20 Jun 2002 18:00:23 -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 28376 invoked by uid 98); 20 Jun 2002 18:00:23 -0000 X-Antivirus: nagoya (v4198 created Apr 24 2002) Reply-To: From: "Berin Loritsch" To: "'Jakarta Commons Developers List'" Subject: RE: [Collection] algorythms was [Commons-Avalon:collections] code integration Date: Thu, 20 Jun 2002 13:59:45 -0400 Message-ID: <005a01c21884$434f5ee0$ac00a8c0@Gabriel> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 In-Reply-To: <00cd01c21883$65a1cc40$0111010a@user> X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Importance: Normal X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N > 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: