Ada.Containers Hash function for a set of small integers
in [ADA]
|
From: Michael R on 22 Apr 2010 19:26 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.
From: John B. Matthews on 22 Apr 2010 21:39 In article <50701baa-7c05-450c-a42d-c699516ddc00(a)t14g2000prm.googlegroups.com>, Michael R <michael(a)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>
From: Simon Wright on 23 Apr 2010 17:39 Michael R <michael(a)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.
From: Michael R on 23 Apr 2010 18:47 On Apr 23, 2:39 pm, Simon Wright <si...(a)pushface.org> wrote: > Michael R <mich...(a)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.
From: Jeffrey R. Carter on 23 Apr 2010 19:08
Michael R <michael(a)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 |