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: 103376,76e8d825615718a
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news2.google.com!news3.google.com!proxad.net!feeder1-2.proxad.net!newsfeed.straub-nv.de!nuzba.szn.dk!pnx.dk!news.tornevall.net!not-for-mail
From: "Jeffrey R. Carter" <spam.jrcarter.not@spam.acm.org>
Newsgroups: comp.lang.ada
Subject: Re: Ada.Containers Hash function for a set of small integers
Date: Fri, 23 Apr 2010 16:08:17 -0700
Organization: TornevallNET - http://news.tornevall.net
Message-ID: <hqt9ot$fm8$1@tornado.tornevall.net>
References: 
 <50701baa-7c05-450c-a42d-c699516ddc00@t14g2000prm.googlegroups.com>
 <m28w8dyhjr.fsf@pushface.org>
NNTP-Posting-Host: c3bf54c739a533492e4eb7d971de629e
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: 81b3743dcd73c4d333d16683530af94c
X-Complaints-To: abuse@tornevall.net
X-Complaints-Language: Spoken language is english or swedish - NOT ITALIAN,
 FRENCH, GERMAN OR ANY OTHER LANGUAGE!
In-Reply-To: <m28w8dyhjr.fsf@pushface.org>
X-Validate-Post: 
 http://news.tornevall.net/validate.php?trace=81b3743dcd73c4d333d16683530af94c
X-SpeedUI: 1738
X-Complaints-Italiano: Non abbiamo padronanza della lingua italiana - se
 mandate una email scrivete solo in Inglese, grazie
User-Agent: Thunderbird 2.0.0.24 (X11/20100411)
X-Posting-User: 0243687135df8c4b260dd4a9a93c79bd
Xref: g2news2.google.com comp.lang.ada:11148
Date: 2010-04-23T16:08:17-07:00
List-Id: <comp.lang.ada>

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