Re: find words that contains some specific letters

["John B. Matthews" <nospam@nospam.invalid>]

In article <alpine.DEB.1.10.0906070035110.5405@urchin.earth.li>,
 Tom Anderson <twic@urchin.earth.li> wrote:

> > John B. Matthews wrote:
> >> The jumble algorithm relies on a hashed map for efficiency, but a 
> >> 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>
> 
> John, i think you've missed a trick there - doesn't Rotate_Left do a 
> barrel shift, where the bits that fall off the left-hand end get 
> shoved back in at the right, rather than a plain shift? If so, the 
> basic algebraic structure is actually a bit different to java's hash.

D'oh, you're absolutely right. I overlooked this when I was tinkering 
with my own hash function, too. Thank you for looking at this.

[...]

> I still think this is a shoddy hash.

Well, it's a legacy from GNAT.HTable.Hash, but it does very well in the 
context of Ada.Containers.Hashed_Maps. Java uses a bucket list whose 
size is an integral power of two, while (this implementation of) Ada 
uses the next largest prime. Modeling an Ada collision counter on your 
example <http://urchin.earth.li/~twic/tmp/Collisions.java>, I got these 
results for collision count, number of buckets having that count, and 
the percentage of the total:

$ ./collisions 
 0: 218586 (55.6%)
 1: 126250 (32.1%)
 2: 38432 (9.8%)
 3: 8362 (2.1%)
 4: 1354 (0.3%)
 5: 229 (0.1%)
 6: 24 (0.0%)
 7: 4 (0.0%)
 8: 1 (0.0%)

The code is here: <http://home.roadrunner.com/~jbmatthews/jumble.html>

[Followup-To set to comp.lang.ada.]
-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>