From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,693e247f5dca709d X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news2.google.com!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news-in-01.newsfeed.easynews.com!easynews.com!easynews!newsfeed.news2me.com!newsfeeds.sol.net!posts.news.twtelecom.net!nnrp2.twtelecom.net!not-for-mail Date: Mon, 27 Nov 2006 17:22:46 -0500 From: Matthew Heaney Organization: On2 Technologies, Inc User-Agent: Thunderbird 1.5.0.8 (Windows/20061025) MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: How to use associative arrays in Ada 2005? References: <1164103903.240838.37230@j44g2000cwa.googlegroups.com> <1164152113.623461.130190@e3g2000cwe.googlegroups.com> <1164310051.811802.237400@l12g2000cwl.googlegroups.com> <14xluht6idlik$.1cxod3mnfvcfs.dlg@40tude.net> <1164567954.228842.32980@h54g2000cwb.googlegroups.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: <456b6536$0$1006$39cecf19@news.twtelecom.net> NNTP-Posting-Date: 27 Nov 2006 22:22:46 GMT NNTP-Posting-Host: 4c65e3fb.news.twtelecom.net X-Trace: DXC=]lkl49NmEDRX[IiQ1]c_gPC_A=>8kQj6]Y;@_o827nGSfN1<9fN_ X-Complaints-To: abuse@twtelecom.net Xref: g2news2.google.com comp.lang.ada:7715 Date: 2006-11-27T22:22:46+00:00 List-Id: 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.