Re: find words that contains some specific letters

["Giovanni Azua" <bravegag@hotmail.com>]

"Patricia Shanahan" <pats@acm.org> wrote:
>>>> 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.

"Giovanni Azua" <bravegag@hotmail.com> wrote:
>>> For example the Character class.

"John B. Matthews" <nospam@nospam.invalid> wrote:
>> 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>

"Patricia Shanahan" <pats@acm.org> wrote:
> Yes, that's the sort of thing I meant.
>
> The Long hash code is also not perfect, and cannot be, because there are
> more longs than ints.
>

To achieve the perfect, optimal and ideal no collisions Hash table "perfect 
Hash table" these are the two factors that play a role:

1-. the "perfect" property of the hash function as defined in the wiki page 
cited above
2-. the size of the elements set

If #2 goes arbitrarily large meaning allocating a hash table of the size of 
that elements set becomes prohibitive memory-wise then it does not really 
matter how perfect the hash function is, there will be collisions anyway and 
an additional search algorithm will be needed to disambiguate the colliding 
elements that fall under the same buckets. This is what I think John 
Matthews hasn't realized yet about his implementation of the Jumble 
algorithm. For a realistic dataset he will be returning elements that do not 
match the of input (String built on top of the sorted character input) but 
matches that happen to collide under the same bucket.

e.g. trying to allocate a Hash table of the size ( Integer.MAX_VALUE - 
Integer.MIN_VALUE) would be prohibitive unless you place unrealistic 
requirements so you have the Integer with a perfect hash function but you 
will not get a "perfect Hash table". It is of course worse for the String 
class where neither #1 nor #2 are fulfilled.

Character class offers the perfect hash function but since the elements set 
is discrete i.e. 26 elements http://en.wikipedia.org/wiki/English_alphabet 
you can build a perfect Hash structure like the one I described and edited 
by Tom McGlynn.

Best regards,
Giovanni