Re: How to use associative arrays in Ada 2005?

[Matthew Heaney <mheaney@on2.com>]

Simon Wright wrote:
> 
> There's no reason I can see to use maps of maps *for this problem*. I
> would use a hash function (Nation x Family_Name x Name) => Hash_Type
> in a single map.

Yes, that's right, you could do it either way.

I prefer that OP's approach of using a map of maps of maps, since that 
allows you to perform queries like "give me all the entries for this 
nation", etc.


> Matt, I see (A.18.4(5)) that Ada.Containers doesn't allow hash
> collisions (which, if true, is demanding a lot of hash function
> designers). 

A.18.4 (5) says:

5/2{AI95-00302-03} {node (of a map)} A map contains pairs of keys and 
elements, called nodes. Map cursors designate nodes, but also can be 
thought of as designating an element (the element contained in the node) 
for consistency with the other containers. There exists an equivalence 
relation on keys, whose definition is different for hashed maps and 
ordered maps. A map never contains two or more nodes with equivalent 
keys. The length of a map is the number of nodes it contains.{length (of 
a map)}

The RM is here:

http://www.adaic.com/standards/05aarm/html/AA-A-18-4.html


You're misreading that paragraph.  It does say that:

"A map never contains two or more nodes with equivalent keys."

but that's very different from saying "hash collisions aren't allowed."

That sentence is simply saying that this is a (unique-key) map, not a 
multi-map.

Hash functions can map key values to the same hash value (that can 
happen easily if your hash function is poor).  That's not good if there 
are many such collisions, but it's certainly allowed by the standard.

But the hash value is only one aspect of a key used to determine its 
uniqueness: the other is equivalence.  The hash value of a key 
determines its bucket, and the equivalence relation is then used to 
compare the key to keys already in that bucket.

So it doesn't matter whether multiple keys hash to the same value (it 
would just mean they all get put in the same bucket), since the success 
of an insertion (say) is ultimately decided by equivalence.

Take a look at the generic formal region of the hashed map:

generic
    type Key_Type is private;

    type Element_Type is private;

    with function Hash (Key : Key_Type) return Hash_Type;

    with function Equivalent_Keys (Left, Right : Key_Type)
       return Boolean;

    with function "=" (Left, Right : Element_Type)
       return Boolean is <>;

package Ada.Containers.Hashed_Maps is

You have to supply both a hash function and an equivalence function. 
Typically you pass "=" as the generic actual for Equivalent_Keys, but 
not always.  (The reason why the general formal is declared that way is 
because equivalence is orthogonal to equality.)


 > If collisions aren't allowed we could go for an ordered
> map based on ... or some likely-to-be-more-efficient order.

If you have as your key a record comprising the 3 strings (nation, 
family name, given name), then "=" would be adequate for Equivalent_Keys.