Re: find words that contains some specific letters

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

In article <78rpbkF1mqrc7U1@mid.individual.net>,
 "Giovanni Azua" <bravegag@hotmail.com> wrote:

> "Patricia Shanahan" <pats@acm.org> wrote in message
> > A perfect hash function is one that guarantees distinct hash codes 
> > for a specific set of keys. There are algorithms for constructing 
> > one, given a set of keys.
>
> For example the Character class.

I think all of the primitive wrappers (except Double) have trivially 
perfect integer hashes, as they wrap distinct values. Patricia was 
perhaps referring to algorithms of the kind discussed here:

<http://en.wikipedia.org/wiki/Perfect_hash_function>

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>

[Cross-posted to comp.lang.java.programmer and comp.lang.ada;
Followup-To header not set.]

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>