Ada.Containers Hash function for a set of small integers
in [ADA]
|
From: Yannick Duchêne (Hibou57) on 5 May 2010 00:29 Le Fri, 23 Apr 2010 23:39:52 +0200, Simon Wright <simon(a)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
From: Warren on 6 May 2010 11:46
=?iso-8859-15?Q?Yannick_Duch=EAne_=28Hibou57=29?= expounded in news:op.vb7teo1pxmjfy8(a)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 |