Re: Ada.Containers Hash function for a set of small integers

["Jeffrey R. Carter" <spam.jrcarter.not@spam.acm.org>]

Michael R <michael@zanyblue.com> writes:

> I'd like to use the generic Hashed_Maps container to store mappings
> from a set of small integers (three) to Wide_Strings
> (Indefinite_Hashed_Maps):
>
> (1, 10, 4) => "ABC",
> (10, 3, 5) => "XYZ",
>
> Does anyone have recommendations on how best to implement the Hash
> function for keys like this?

What is the definition of "small"? If it has a defined range, for example:

subtype Small is Natural range Low .. High;

then you can define

Offset = 0 - Low
Max = High + Offset

and for X = # bits needed to represent Max, if 3 * X <= 
Ada.Containers.Hash_Type'Size, then you can do a perfect hash:

type Triple is record
    A : Small;
    B : Small;
    C : Small;
end record;

Hash (R : Triple) = Shift_Left (R.A + Offset, 2 * X) or
                     Shift_Left (R.B + Offset, X)     or
                     (R.C + Offset)

-- 
Jeff Carter
"I was in love with a beautiful blonde once, dear.
She drove me to drink. That's the one thing I'm
indebted to her for."
Never Give a Sucker an Even Break
109