From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,918406c619dd104d
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news2.google.com!news3.google.com!proxad.net!feeder1-2.proxad.net!newsfeed.straub-nv.de!news.albasani.net!not-for-mail
From: Lew <noone@lewscanon.com>
Newsgroups: comp.lang.java.programmer,comp.lang.ada
Subject: Re: find words that contains some specific letters
Date: Sat, 06 Jun 2009 14:23:04 -0400
Organization: albasani.net
Message-ID: <h0ec6a$gvk$1@news.albasani.net>
References: 
 <edaeda6b-3793-48f2-8f8f-6c9701759de5@r33g2000yqn.googlegroups.com>
 <f350aaae-d045-450d-b255-308eb7fb8f8a@e24g2000vbe.googlegroups.com>
 <d121e6f6-6afa-43e7-bcd1-c9a770e12704@z9g2000yqi.googlegroups.com>
 <nospam-83CE7B.07382201062009@news.aioe.org>
 <78i1lbF1m69gkU1@mid.individual.net> <78i2ajF1m4nglU1@mid.individual.net>
 <h00l40$r5h$1@news.albasani.net> <78i4i2F1magkfU1@mid.individual.net>
 <3f1d007f-bcae-42b4-afb0-215b18f51b9c@n21g2000vba.googlegroups.com>
 <78ib19F1mfh7qU1@mid.individual.net>
 <3b519936-3db9-4dad-85ba-371fa4b29c8f@z5g2000vba.googlegroups.com>
 <78quiaF1n95fsU1@mid.individual.net> <h09q6f$41t$1@news.albasani.net>
 <MJWdnUzVI6hADrXXnZ2dnUVZ_q2dnZ2d@earthlink.com>
 <78rpbkF1mqrc7U1@mid.individual.net>
 <nospam-B6C8E0.12131906062009@news.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net
 2Ywz1wXR8KUtALbALS46Qqvoqr9CKJ4EaCWAtQwm6jOzMBUSrT5JHHkGceyRD6149fDAQ6Atx45kbb1cAWiPfYzsLDnMJQd3kryy1jrwiSAgGjm61iJ7sgHZFPFxvrgX
X-Complaints-To: abuse@albasani.net
NNTP-Posting-Date: Sat, 6 Jun 2009 18:23:06 +0000 (UTC)
X-User-ID: tme1Zg1x9AF8g7Qqot+xtsx8HdU/SqyqPE4FjVY/8Ko=
In-Reply-To: <nospam-B6C8E0.12131906062009@news.aioe.org>
Cancel-Lock: sha1:TmK66EZNV95GtFIRn+zr712xwpc=
User-Agent: Thunderbird 2.0.0.21 (X11/20090409)
X-NNTP-Posting-Host: FMd1KbZAhD2cMsPUvpKdZWaXqPveebDlPSmJBEBjDLc=
Xref: g2news2.google.com comp.lang.java.programmer:42914 comp.lang.ada:6341
Date: 2009-06-06T14:23:04-04:00
List-Id: <comp.lang.ada>

John B. Matthews wrote:
> The jumble algorithm relies on a hashed map for efficiency, but a

Because it has constant-time performance for get() with the String hash code.

> perfect hash is not essential. I recently implemented the algorithm
> in both Java and Ada using library routines:
> 
> <http://en.wikipedia.org/wiki/Jumble>
> <http://sites.google.com/site/drjohnbmatthews/jumble>
> <http://home.roadrunner.com/~jbmatthews/jumble.html>
> 
> I was intrigued to compare the two languages' library implementations 
> of a general purpose string hash. Using a multiplicative function with 
> an initial value of zero, both offer excellent performance. Java uses a 
> multiplier of 31 on a signed 32-bit integer; Ada uses a multiplier of 
> eight on an unsigned (modular) value whose size is implementation 
> defined (e.g. mod 2**32):
> 
> <http://www.docjar.org/html/api/java/lang/String.java.html>
> <http://gcc.gnu.org/viewcvs/trunk/gcc/ada/a-strhas.adb>

The Java String hash is just about verbatim from Knuth.  It has the virtue of 
being a well-studied algorithm that has been shown to have good distribution 
characteristics.

I'm not so sure about the Ada one.  I haven't studied this in a while, but I 
seem to recall that power-of-two multipliers mod 2**32 don't have as good a 
distribution.  Perhaps someone could correct me on that.

-- 
Lew