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

[Simon Wright <simon@pushface.org>]

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.