Ada.Containers Hash function for a set of small integers

Ada.Containers Hash function for a set of small integers

[Michael R]

Hi Folks,

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?

Take care,
Michael.

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

[John B. Matthews]

In article 
<50701baa-7c05-450c-a42d-c699516ddc00@t14g2000prm.googlegroups.com>,
 Michael R <michael@zanyblue.com> wrote:

> Hi Folks,
> 
> 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?

I'd try something simple like shift and add, but it might depend on the 
definition of "small".

Whatever you decide, here's some code I used to examine the distribution 
of collisions in a map keyed by "/usr/share/dict/words":

$ ./collisions 
 0: 218586 (55.59%)
 1: 126250 (32.10%)
 2: 38432 (9.77%)
 3: 8362 (2.13%)
 4: 1354 (0.34%)
 5: 229 (0.06%)
 6: 24 (0.01%)
 7: 4 (0.00%)
 8: 1 (0.00%)

<http://home.roadrunner.com/~jbmatthews/jumble.html#sec2>

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

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

[Simon Wright]

Michael R <michael@zanyblue.com> writes:

> Hi Folks,
>
> 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?

I don't know about 'best', but in ColdFrame
(http://coldframe.sourceforge.net/coldframe/) I would generate this hash
for use with Booch Maps, where the key components of Instance are
{A:Integer, B:Integer, C:Integer}:

   function Instance_Hash (I : Instance) return Natural is
      type M is mod 2**31;
      Result : M := 0;
   begin
      Result := Result xor M (I.A mod 2**31);
      Result := Result * 10019;
      Result := Result xor M (I.B mod 2**31);
      Result := Result * 10019;
      Result := Result xor M (I.C mod 2**31);
      Result := Result * 10019;
      return Natural (Result);
   end Instance_Hash;

I believe the 10019 came from Knuth, but can't see a reference.

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

[Michael R]

On Apr 23, 2:39 pm, Simon Wright <si...@pushface.org> wrote:
> Michael R <mich...@zanyblue.com> writes:
> > Hi Folks,
>
> > 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?
>
> I don't know about 'best', but in ColdFrame
> (http://coldframe.sourceforge.net/coldframe/) I would generate this hash
> for use with Booch Maps, where the key components of Instance are
> {A:Integer, B:Integer, C:Integer}:
>
>    function Instance_Hash (I : Instance) return Natural is
>       type M is mod 2**31;
>       Result : M := 0;
>    begin
>       Result := Result xor M (I.A mod 2**31);
>       Result := Result * 10019;
>       Result := Result xor M (I.B mod 2**31);
>       Result := Result * 10019;
>       Result := Result xor M (I.C mod 2**31);
>       Result := Result * 10019;
>       return Natural (Result);
>    end Instance_Hash;
>
> I believe the 10019 came from Knuth, but can't see a reference.

Hi,

Thank you for this suggestion.  Just fyi, my GNAT 4.4.3 compiler
generated

xtest.adb:20:40: value not in range of type "Standard.Integer"
xtest.adb:20:40: static expression fails Constraint_Check

for "M (I.A mod 2**31)" expressions.  Rephrasing as

Result := Result xor M'Mod (I.A);

compiled OK.

Take care,
Michael.

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

[Jeffrey R. Carter]

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

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

[Simon Wright]

Michael R <michael@zanyblue.com> writes:

> On Apr 23, 2:39 pm, Simon Wright <si...@pushface.org> wrote:

>> I don't know about 'best', but in ColdFrame
>> (http://coldframe.sourceforge.net/coldframe/) I would generate this hash
>> for use with Booch Maps, where the key components of Instance are
>> {A:Integer, B:Integer, C:Integer}:
>>
>>    function Instance_Hash (I : Instance) return Natural is
>>       type M is mod 2**31;
>>       Result : M := 0;
>>    begin
>>       Result := Result xor M (I.A mod 2**31);
>>       Result := Result * 10019;
>>       Result := Result xor M (I.B mod 2**31);
>>       Result := Result * 10019;
>>       Result := Result xor M (I.C mod 2**31);
>>       Result := Result * 10019;
>>       return Natural (Result);
>>    end Instance_Hash;
>>
>> I believe the 10019 came from Knuth, but can't see a reference.
>
> Thank you for this suggestion.  Just fyi, my GNAT 4.4.3 compiler
> generated
>
> xtest.adb:20:40: value not in range of type "Standard.Integer"
> xtest.adb:20:40: static expression fails Constraint_Check
>
> for "M (I.A mod 2**31)" expressions.  Rephrasing as
>
> Result := Result xor M'Mod (I.A);
>
> compiled OK.

I looked into this and found that for this specific case I would in fact
generate rather different code -- sorry about that, a bit like posting
untested Ada :-(

Actually it would be

   function Instance_Hash (I : Instance) return Natural is
      type M is mod 2**31;
      Result : M := 0;
   begin
      Result := Result xor Integer'Pos (I.A);
      Result := Result * 10019;
      Result := Result xor Integer'Pos (I.B);
      Result := Result * 10019;
      Result := Result xor Integer'Pos (I.C);
      return Natural (Result);
   end Instance_Hash;

and, before anyone rushes to check it out, yes, it fails with negative
values and I'm about to file a bug against it.

Thanks for the response.

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

[Warren]

Simon Wright expounded in news:m28w8dyhjr.fsf@pushface.org:
..
> for use with Booch Maps, where the key components of Instance are
> {A:Integer, B:Integer, C:Integer}:
> 
>    function Instance_Hash (I : Instance) return Natural is
>       type M is mod 2**31;
>       Result : M := 0;
>    begin
>       Result := Result xor M (I.A mod 2**31);
>       Result := Result * 10019;
>       Result := Result xor M (I.B mod 2**31);
>       Result := Result * 10019;
>       Result := Result xor M (I.C mod 2**31);
>       Result := Result * 10019;
>       return Natural (Result);
>    end Instance_Hash;
> 
> I believe the 10019 came from Knuth, but can't see a reference.

I think this is just a selected prime number:

 http://www.mathematical.com/primes3000kto4000k.html

Probably a compromise between "wideness" and memory
used in the map itself (affects number of buckets perhaps).

Warren.

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

[Jeffrey R. Carter]

Warren wrote:
> Simon Wright expounded in news:m28w8dyhjr.fsf@pushface.org:
>>
>> I believe the 10019 came from Knuth, but can't see a reference.
> 
> I think this is just a selected prime number:

Except that 10_019 is not a prime number, according to:

http://www.mathematical.com/primes0to1000k.html

9949,9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10093

-- 
Jeff Carter
"Ah, go away or I'll kill ya."
Never Give a Sucker an Even Break
100

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

[Charmed Snark]

Jeffrey R. Carter expounded in news:hr4lnl$6m8$1@tornado.tornevall.net:

> Warren wrote:
>> Simon Wright expounded in news:m28w8dyhjr.fsf@pushface.org:
>>>
>>> I believe the 10019 came from Knuth, but can't see a reference.
>> 
>> I think this is just a selected prime number:
> 
> Except that 10_019 is not a prime number, according to:
> 
> http://www.mathematical.com/primes0to1000k.html
> 
> 9949,9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10
> 093 

Oh I see - these numbers start at 3000017-- my haste, my bad.

Warren

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

[Robert A Duff]

Simon Wright <simon@pushface.org> writes:

>       type M is mod 2**31;
>       Result : M := 0;
>    begin
>       Result := Result xor Integer'Pos (I.A);

> and, before anyone rushes to check it out, yes, it fails with negative
> values and I'm about to file a bug against it.

I don't think that's a compiler bug.  Conversion of negative numbers
to modular raises Constraint_Error.  I think that's a language
design flaw, but not everyone agrees with me.  The 'Mod attribute
works around the problem.

- Bob

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

[Simon Wright]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> Simon Wright <simon@pushface.org> writes:
>
>>       type M is mod 2**31;
>>       Result : M := 0;
>>    begin
>>       Result := Result xor Integer'Pos (I.A);
>
>> and, before anyone rushes to check it out, yes, it fails with
>> negative values and I'm about to file a bug against it.
>
> I don't think that's a compiler bug.  Conversion of negative numbers
> to modular raises Constraint_Error.  I think that's a language design
> flaw, but not everyone agrees with me.  The 'Mod attribute works
> around the problem.

No, I meant a bug against my code generator!

On the other hand, I found some strange behaviour with GNAT GPL 2009
(and GCC 4.5.0) while investigating possible solutions:

------------------------------------------------------------------------
with Ada.Text_IO; use Ada.Text_IO;

procedure Odd_Warning is

   procedure Inner (X : Integer) is
      type M is mod 2**31;
      Result : M;
   begin

      begin
         Result := 0;
         Result := Result xor (Integer'Pos (X) mod 2**30);
         --  No compiler warning, but raises exception
      exception
         when others => Put_Line ("exception a");
      end;

      begin
         Result := 0;
         Result := Result xor (Integer'Pos (X) mod 2**31);
         --  odd_warning.adb:20:53: warning: mod with zero divisor
         --  odd_warning.adb:20:53: warning: "Constraint_Error" will be
         --    raised at run time
      exception
         when others => Put_Line ("exception b");
      end;

      begin
         Result := 0;
         Result := Result xor M (Integer'Pos (X) mod 2**31);
         --  No warning (and executes as I had expected)
         Put_Line ("result:" & M'Image (Result));
      exception
         when others => Put_Line ("exception c");
      end;

   end Inner;

begin

   Inner (-1);

end Odd_Warning;
------------------------------------------------------------------------

The second block's compiler warning is strange, especially the part
about the zero divisor. The Aonix ObjectAda 7.2 compiler gives a very
similar warning referring to 95LRM4.5.5(22), and gives an error at the
third block (95LRM4.9(35)). 

I think my route will be via unchecked conversion, if I don't decide
that it's a feature - in 10 years of use no one has needed to use a
negative value as a component of a hash.

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

[Adam Beneschan]

On Apr 26, 2:05 pm, Simon Wright <si...@pushface.org> wrote:
> Robert A Duff <bobd...@shell01.TheWorld.com> writes:
>
> > Simon Wright <si...@pushface.org> writes:
>
> >>       type M is mod 2**31;
> >>       Result : M := 0;
> >>    begin
> >>       Result := Result xor Integer'Pos (I.A);
>
> >> and, before anyone rushes to check it out, yes, it fails with
> >> negative values and I'm about to file a bug against it.
>
> > I don't think that's a compiler bug.  Conversion of negative numbers
> > to modular raises Constraint_Error.  I think that's a language design
> > flaw, but not everyone agrees with me.  The 'Mod attribute works
> > around the problem.
>
> No, I meant a bug against my code generator!
>
> On the other hand, I found some strange behaviour with GNAT GPL 2009
> (and GCC 4.5.0) while investigating possible solutions:
>
> ------------------------------------------------------------------------
> with Ada.Text_IO; use Ada.Text_IO;
>
> procedure Odd_Warning is
>
>    procedure Inner (X : Integer) is
>       type M is mod 2**31;
>       Result : M;
>    begin
>
>       begin
>          Result := 0;
>          Result := Result xor (Integer'Pos (X) mod 2**30);
>          --  No compiler warning, but raises exception
>       exception
>          when others => Put_Line ("exception a");
>       end;
>
>       begin
>          Result := 0;
>          Result := Result xor (Integer'Pos (X) mod 2**31);
>          --  odd_warning.adb:20:53: warning: mod with zero divisor
>          --  odd_warning.adb:20:53: warning: "Constraint_Error" will be
>          --    raised at run time
>       exception
>          when others => Put_Line ("exception b");
>       end;
>
>       begin
>          Result := 0;
>          Result := Result xor M (Integer'Pos (X) mod 2**31);
>          --  No warning (and executes as I had expected)
>          Put_Line ("result:" & M'Image (Result));
>       exception
>          when others => Put_Line ("exception c");
>       end;
>
>    end Inner;
>
> begin
>
>    Inner (-1);
>
> end Odd_Warning;
> ------------------------------------------------------------------------
>
> The second block's compiler warning is strange, especially the part
> about the zero divisor. The Aonix ObjectAda 7.2 compiler gives a very
> similar warning referring to 95LRM4.5.5(22), and gives an error at the
> third block (95LRM4.9(35)).

The warning looks correct to me.  The way the expression is
constructed in the second block, all of the operators have operands of
type M (except for the right operand of "**").  This means that you're
using "**" with the definition

   function "**" (Left : M; Right : Integer) return M;

And modular operations wrap around.  The result of the above operator
with arguments Left=2, Right=31 is therefore 0, since the range of M
is 0 .. 2**31-1.

In the third block, the type conversion to M changes everything; the
argument of this type conversion can be anything that works (as
opposed to the second block, in which the right side must be an
expression of type M).  Since the type of Integer'Pos(X) is a
universal integer, the end result is that the operators inside the
type conversion are interpreted as being the operations of the
"root_integer" type.  Whether the error message is correct, incorrect,
or implementation-dependent, I'm not sure without further study, but I
suspect that it may be implementation-dependent and may depend on what
base ranges the implementation has chosen for its built-in integer
types.

In any case, unless you're trying to develop code that compiles with
an Ada95 compiler, I'd prefer to use 'Mod over Unchecked_Conversion.
The whole purpose of 'Mod was to eliminate the need for
Unchecked_Conversion in cases like this, since it was impossible to
write "normal" code that would do the computation correctly.

                               -- Adam

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

[AdaMagica]

> >          Result := Result xor M (Integer'Pos (X) mod 2**31);
> >          --  No warning (and executes as I had expected)
> >          Put_Line ("result:" & M'Image (Result));
> >       exception
> >          when others => Put_Line ("exception c");
> >       end;
> about the zero divisor. The Aonix ObjectAda 7.2 compiler ...
> gives an error at the third block (95LRM4.9(35)).

I'm no language lawyer, but I'll give it a try.

RM95 4.9(35): If the expression is not part of a larger static
expression, then its value shall be within the base range of its
expected type. Otherwise, the value may be arbitrarily large or small.

RM TC1 AM1 4.9(35/2) {AI95-00269-01} If the expression is not part of
a larger static expression *and the expression is expected to be of a
single specific type*, then its value shall be within the base range
of its expected type. Otherwise, the value may be arbitrarily large or
small.

Since Aonix quotes 95RM4.9(35), it must be a pure Ada95 compiler.
2**31 is not part or a larger static expression. The further condition
of being of a single specific type (which is not the case here, the
expected type is any integer type) was added later.

So Aonix is correct, and so is GNAT, if the latter is new enough to
obey AM1.

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

[Simon Wright]

AdaMagica <christoph.grein@eurocopter.com> writes:

> Since Aonix quotes 95RM4.9(35), it must be a pure Ada95 compiler.

Thanks for the analysis.

The '95' in that quote was actually me. But since the compiler binaries
are no later than Feb 2000 I think your conclusion is correct!

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

[Simon Wright]

Adam Beneschan <adam@irvine.com> writes:

> In any case, unless you're trying to develop code that compiles with
> an Ada95 compiler, I'd prefer to use 'Mod over Unchecked_Conversion.
> The whole purpose of 'Mod was to eliminate the need for
> Unchecked_Conversion in cases like this, since it was impossible to
> write "normal" code that would do the computation correctly.

Ada95 it is .. though I could actually change now with no impact on the
current user project, which is not going to migrate.

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

[Yannick Duchêne (Hibou57)]

Le Fri, 23 Apr 2010 23:39:52 +0200, Simon Wright <simon@pushface.org> a  
écrit:
> I don't know about 'best', but in ColdFrame
> (http://coldframe.sourceforge.net/coldframe/) I would generate this hash
> for use with Booch Maps, where the key components of Instance are
> {A:Integer, B:Integer, C:Integer}:
>
>    function Instance_Hash (I : Instance) return Natural is
>       type M is mod 2**31;
>       Result : M := 0;
>    begin
>       Result := Result xor M (I.A mod 2**31);
>       Result := Result * 10019;
>       Result := Result xor M (I.B mod 2**31);
>       Result := Result * 10019;
>       Result := Result xor M (I.C mod 2**31);
>       Result := Result * 10019;
>       return Natural (Result);
>    end Instance_Hash;
>
> I believe the 10019 came from Knuth, but can't see a reference.
Unlucky, I was to ask you how this 10_019 was computed. At least, this  
magic number is not a prime number, the nearest is 1009.

If this can help, may be some goodies there :
http://www.isthe.com/chongo/tech/comp/fnv/
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

-- 
No-no, this isn't an oops ...or I hope (TM) - Don't blame me... I'm just  
not lucky

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

[Warren]

=?iso-8859-15?Q?Yannick_Duch=EAne_=28Hibou57=29?= expounded in 
news:op.vb7teo1pxmjfy8@garhos:

>> I believe the 10019 came from Knuth, but can't see a reference.

> Unlucky, I was to ask you how this 10_019 was computed. At least, this  
> magic number is not a prime number, the nearest is 1009.
> 
> If this can help, may be some goodies there :
> http://www.isthe.com/chongo/tech/comp/fnv/
> http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

Thanks for those references. That is good information
for my own project, since several maps are used in it.

Warren