Talk:Associative array/Archive 1

Archive 1

References as Keys

In a tree where each node is an associative array, the keys can be references to other nodes in the tree rather than using a textual name. This can be implimented with the Tie function.

I'm implimenting a distributed one of these and wondering if anyone knows of any other implimentations or documentation about this kind of data structure, or whether it goes by any specific names etc. Nad 21:21, 31 January 2006 (UTC)

• PERL Tie information
• Tie::RefHash - use references as hash keys

Hmmm, Do you mean that the values can be references to other associative sub-arrays, rather than the keys? For example, if I had to represent a Unix directory tree of just sub-directories, files and links to sub-directories then I would first walk the directory tree ignoring any links. Each directory would become an associative array,(AA), with directory entry names as keys and either file 'objects' as values for each file; or sub-AAs to represent sub-directories. A second walk of the directory tree would allow my to insert references to appropriate AA's as values for keys representing directory links.

In Python, AA values can be any object, so an AA with a recursive value example is just:

*** Python 2.4.2 (#67, Jan 17 2006, 15:36:03) [MSC v.1310 32 bit (Intel)] on win32. ***
>>> dir1 = { 'file1': 'file1' }      # AA creation with one file
>>> dir1
{'file1': 'file1'}
>>> dir1['link1'] = dir1             # The recursive link
>>> dir1
{'file1': 'file1', 'link1': {...}}
>>> dir1['link1']                    # Accesses through the reference
{'file1': 'file1', 'link1': {...}}
>>> dir1['link1']['link1']
{'file1': 'file1', 'link1': {...}}
>>> dir1['link1']['link1']['file1']
'file1'

Again in Python; all non-mutable types are able to be AA keys. Other user-defined types can be used as AA keys if they define a hashing method. (The main mutable built-in type affected by the restriction is the Python list type. Lists are easily converted to the non-mutable tuple type for use as dictionary keys). --Paddy 07:39, 30 April 2006 (UTC)

Delete reference to TAWK?

Thomson Automation are nolonger selling there version of AWK. (follow the link). Sould it be removed from the AWK entry --Paddy 17:22, 22 September 2006 (UTC)

Removed "Map" from the "Data structures" section

I undid a good-faith edit by User:Irishjugg that added a new section titled "Maps" and went as follows:

The map (associative array) is a structure with no stored order, similar to an orderless list. Values are stored by certain key values in the form mapname[keyvalue] = value. In C++ implementations, such as the STL, the maps are templated and can have values of any standard or user defined type. Insertion into a map is is O(1) time, while for accessing elements it is O(nlogn) as it mush search for the keys. The STL implementation uses a Red Black tree to handle the key searches which ensures worst case O(nlogn). Maps are at the heart of associative arrays.

I have a number of issues with this addition, as follows:

• A map is just another name for an associative array, so saying you can implement an associative array as a map is pretty vacuous
• The most insightful point in this section, that the STL map is implemented as a red-black tree, was already covered; mention of self-balancing trees is under "Efficient representations"
• Insertions into a tree (if you don't provide a good hint to the insert function) is O(log n), not O(1)
• Accessing elements is O(log n), not O(n log n)
• Saying that the STL implementation is red black trees is not really correct, since an implementor is free to choose any structure that satisfies the appropriate complexity requirements. An AVL tree, various variants of B-trees, skip lists, and probably many other structures would all be reasonably appropriate as a backing store, and would result in a reasonable STL implementation.

EvanED 22:07, 10 December 2007 (UTC)

Edited again for a minor fix, and additional objection, EvanED 22:10, 10 December 2007 (UTC)

That all sounds correct to me. Dcoetzee 03:06, 16 June 2008 (UTC)

Associative array X Regular array

The article says the following about the difference:

While a regular array maps an index to an arbitrary data type such as integers, other primitive types, or even objects, an associative array's keys can be arbitrarily typed. The values of an associative array do not need to be the same type, although this is dependent on the programming language.

However, in my opinion, the difference between arrays and maps/dictionaries/hash tables lies on keys, not on values. At least in the programming languages I've programmed on so far, a traditional array is (conceptually) a special kind of map where indices are integers that are immediately consecutive (without "holes" or "jumps").

Comments? --Antonielly (talk) 19:06, 20 October 2008 (UTC)

Association lists

The section under Association lists defines these to be a linked list of key-value pairs. This is consistent with the common definition of the term in Lisp/Scheme -- for example, [1]. The DADS page at [2] notes that the term is primarily associated with Lisp and the AI community.

User:Pgr94 recently made an edit [3] that doubts this, and the edit comment states that "decent implementations use balanced trees which give O(log n) look up time". However, the article itself lays out a contrast between efficient implementations -- balanced trees and hash tables -- in the immediately preceding section, and the inefficient linked-list-based implementation commonly called an association list. The DADS page, cited by User:Pgr94, makes no specific claim as to efficiency of an association list, and notes that they are often much smaller than general dictionaries. Indeed, an a-list is semantically equivalent to a tree-based dictionary, and the first page cited above notes that an a-list in practice (in one implementation) is in fact a true linked list.

There are two possible solutions to this -- either the claim that an association list might be tree-based is wrong, in which case User:Pgr94's edit should be reverted, or else the rest of the article needs to be made consistent with this new fact, since its structure sets up a contrast between linear-time and log-time implementations. My understanding of a-lists leans toward the former, i.e., that a true a-list is always a linked list and anything else is a dictionary but not an a-list. Thoughts?

cfallin|(talk) 11:33, 21 December 2008 (UTC)

I am questioning whether association lists have to be linked lists.

The DADS page says "dictionary" and "association list" are synonyms.

It would be good to have some more sources, specifically data-structure textbooks. Unfortunately, the books I have to hand don't mention the topic. pgr94 (talk) 12:03, 21 December 2008 (UTC)

Unfortunately I couldn't find anything in my data structures book (Cormen et al, Intro to Algorithms 2nd ed) either. But here's a mention of association lists in an O'Reilly book on Haskell: Real World Haskell, pg 299 (Google Books preview). This states "An association list is just a normal list containing (key, value) tuples." My understanding of the DADS page connection between association lists and dictionaries is that an association list and a dictionary are equivalent at the semantic level -- thus, the operations listed on the page are implemented by both -- but that association list implies a particular underlying structure, namely, a simple list. The two citations I've given -- the O'Reilly book and the CMU lisp page -- both support this common usage. Here's another Lisp page that describes an alist specifically as a true list: www.faqs.org/faqs/lisp-faq/part2/section-2.html LISP FAQ part 2 section 2. Again, I'd be interested in any examples of a tree-based alist you could find (some casual Googling didn't turn up anything on my end). If not, I'd be glad to incorporate some of these citations into the article and make the Lisp connection more clear. cfallin|(talk) 22:29, 21 December 2008 (UTC)

There are two definitions of "assocation list" floating around. One is a synonym for associative array; the other refers to a specific implementation of an associative array usign a simple unordered linked list of key-value pairs. I think the latter is more useful, since otherwise there is no simple term for such an implementation, but we could potentially mention both, at the risk of introducing confusion. Dcoetzee 22:04, 22 December 2008 (UTC)

I made an edit that will hopefully clarify this -- thanks to both of you for the input. cfallin (talk) 03:19, 24 December 2008 (UTC)

I'm not sure. An association list is, by name, a sort of list, and certainly not a hash table or a tree. I would discourage readers from confusing the abstract data type "associative array" from any of its common implementations -- including association lists, hash tables, or various sorts of trees. --FOo (talk) 07:20, 24 December 2008 (UTC)

You're right. I was hesitant to force this at first, but the distinction between the semantic level (at which an alist and a dictionary are synonyms) and implementation level is what I was arguing above. Given this and the fact that pgr94's only objection was a citation of the DADS page, which makes no claim on implementation, I've brought the paragraph into close alignment with the original, but with a few citations. cfallin (talk) 21:51, 24 December 2008 (UTC)

Hashes

Please don't confuse hash-tables with hashes. They are very different things. —Preceding unsigned comment added by 203.222.167.145 (talk) 02:19, 8 September 2009 (UTC)

Confused with Ordering vs Sorting

I find this phrase confusing:

Ordering preservation: Balanced binary trees and skip lists preserve ordering — allowing one to efficiently iterate over the keys in order or to efficiently locate an association whose key is nearest to a given value. Hash tables do not preserve ordering and therefore cannot perform these operations as efficiently (they require the data to be sorted in a separate step).

I feel that the phrase should refer to the preservation of the "insertion order" when iterating over the collections of Keys or Values. But "key is nearest to a given value" supposes a kind order in the set of keys, and this is not part of the contract for the associative array abstract type. Note that Java JDK1.5 includes the class LinkedHashMap that preserves insertion order when browsing the map.

For the same reason I don't see the point to mention "range queries" for associative arrays, as they are not part of the contract. Maybe you could include among the "Specialized representations" the ones with sorted key sets. I mean, to define the abstract subtype "Sorted Associative Array" that would allow for range queries, and would exclude the simple has table implementations. —Preceding unsigned comment added by 83.43.153.47 (talk) 20:53, 20 November 2009 (UTC)

Redirects are a bit of a mess

Hi. Between this article ("Associative array") and the article Attribute–value pair, some redirects are a bit messy:

• Key-value association
• Key-value data
• Key-value store
• Key-value database

These four redirects above currently point to Associative array.

• Key-value pair
• Key Value Pair
• Name-value pair
• Arbitrary key-value pairs
• Arbitrary key-value pair
• Arbitrary key value pair
• Attribute-value pair
• Key-value
• Key value

These nine redirects above currently point to Attribute–value pair.

Previously, some of these redirects pointed to NoSQL, which I felt wasn't appropriate. This all seems a bit messy. Perhaps someone could take a look? --MZMcBride (talk) 19:20, 27 January 2013 (UTC)

PHP

Where is the PHP example??

Sign your edits. Wouter Lievens 08:56, 31 May 2005 (UTC)

"In PHP all arrays can be associative, except that the keys are limited to integers and strings and can only be a single level of subscripts."

Maybe I'm just reading this wrong, but can someone explain to me what this above statement means? --CheesyPuffs144 (talk) 02:27, 15 June 2008 (UTC)

The PHP example is at comparison of programming languages (mapping)#PHP.

CheesyPuffs144, I agree that the above statement is confusing and probably incorrect. The associative array#Language support section of this article currently says

"In PHP, all arrays can be associative, except that the keys are limited to integers and strings."

which as you probably already know means that, in PHP, each key must be either an integer, or a string -- in PHP, you can't anything else as a key -- a float, an array, etc.

The comparison of programming languages (mapping)#PHP includes an example

$phonebook['contacts']['Sally Smart']['number']      = '555-9999';

which has 3 subscripts (also called indexes). The remaining parts of the above statement seem to be (incorrectly) saying that PHP doesn't support such multiple-subscript statements.

--DavidCary (talk) 16:02, 29 April 2015 (UTC)

<source lang="PostScript"> ... </source>

Or at least I would if I could, but "PostScript" is not a recognised source language...

actionscript, ada, apache, applescript, asm, asp, autoit, bash, blitzbasic, bnf, c,
c_mac, caddcl, cadlisp, cfdg, cfm, cpp, cpp-qt, csharp, css, d, delphi, diff, div,
dos, eiffel, fortran, freebasic, gml, groovy, html4strict, idl, ini, inno, io, java,
java5, javascript, latex, lisp, lua, matlab, mirc, mpasm, mysql, nsis, objc, ocaml,
ocaml-brief, oobas, oracle8, pascal, perl, php, php-brief, plsql, python, qbasic,
rails, reg, robots, ruby, sas, scheme, sdlbasic, smalltalk, smarty, sql, tcl, text,
thinbasic, tsql, vb, vbnet, vhdl, visualfoxpro, winbatch, xml, xpp, z80

Any suggestions how to remedy this? nemo 11:35, 4 October 2007 (UTC)

It appears to be a recognized language now:

  % Level 1 declaration
  3 dict dup begin
    /red   (rouge) def
    /green (vert)  def
    /blue  (bleu)  def
  end

See Help: Wiki markup#Text formatting and Wikipedia: syntaxhighlight. --DavidCary (talk) 02:59, 24 May 2015 (UTC)

search tree

A recent edit([4]) makes this article say that both hash tables and search trees can solve the dictionary problem.

Previous versions of this article implied that there are some cases where a search tree cannot solve the dictionary problem (but a hash table could solve the problem).

Are there really cases where a search tree cannot solve the problem (forcing us to use hash tables in those cases)? If so, what are those cases? --DavidCary (talk) 15:50, 31 July 2016 (UTC)

It's usually more about abstract data types than actual information-theoretic impossibility, and happens when you have objects of data types that can be compared for equality and hashed but don't have a total order. For instance the equality test could be something defined within another data type that you have no access to, so it might not be either address comparison or bitwise data comparison, but that other data type for whatever reason hasn't defined ordered comparisons. —David Eppstein (talk) 16:16, 31 July 2016 (UTC)

This is backwards. If you have a comparison and an equality operation, you can use a search tree. If you have some way of assigning a number or a bitstring to every object, then you can use a hash table. Of course, once you have a number or bitstring, you can also use a search tree, though the ordering may have no "meaning" in terms of the abstract data type; so things like range queries will no longer be meaningful.

As for the 'requirement' of an equality operation, if you have a strict < operation, then a=b == not(a<b or b<a) is the equality operation; if you have a ≤ operation, then a=b == (a≤b) and (b≤a) is. --Macrakis (talk) 20:31, 31 July 2016 (UTC)

Bash 4.0

is it missing information about Bash 4.0? Tech201805 (talk) 15:15, 25 June 2018 (UTC)

Protected

I have temporarily edit-protected this article (in, of course, the wrong version) because of the edit-warring going on over its lead. Please discuss the lead here rather than repeatedly reverting to your preferred versions. —David Eppstein (talk) 03:27, 9 August 2019 (UTC)

Thank you! This article needs protecting. Which is what I've tried to do. The editor refused to accept obvious consensus, and kept adding changes that had been reverted by multiple other editors. I tried to get the editor to read and respect Wikipedia policy, by repeatedly linking to the applicable sections. I even tried putting information about 3RR on the editor's talk page.

The lead should identify the topic and summarize the body of the article with appropriate weight. It should not summarize an unreferenced "body of research", or be original research. Claims should cite reliable sources, not unspecified schoolbooks. Repeated incoherent edits where the only arguments are about an apparent war with the "C++ people" and their alleged "grandiose cooky reason", unintelligible claims that every "definition must be defined by set theory" in computer science article, et cetera, are disruptive. Is there an actual coherent argument, for why these edits are constructive and in line with Wikipedia policy, and what's allegedly wrong with the time-tested revision? I have yet to see one.

185.213.154.172 (talk) 11:29, 9 August 2019 (UTC)

Clarification: I'm not claiming that the time-tested revision is inherently correct, just because it's time-tested and vetted by many editors/readers. I'm claiming that there is no coherent argument for blatant attacks like: "The article as previously was written had some huge holes in it big enough to fit a ship through. You can't just put up a definition in Wikipedia that is wrong on its face."

185.213.154.172 (talk) 12:56, 9 August 2019 (UTC)

Consensus: Edits were incompetent or vandalism?

Either way they were clearly disruptive, and a total waste of time. There ought to be at least a pending changes protection on this page, for the editor in question, since it's recurring behavior (with about a week between episodes). There is an obvious obsession with the "C++ people" and "set theory" here, and no apparent respect for Wikipedia policy.

185.213.154.172 (talk) 17:56, 10 August 2019 (UTC)

Wiki is Scientifically Inaccurate

Dale Walker 1996 specifically states that formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations". In this sentense shall specifically means that you CAN, not that it's optional to do so. The entire idea behind an ADT is that you can take the mathematical definition and implement that definition in any programming language. We use math to define an ADT for one reason because it is the one and only Universal Language. This means that in the official cited literature, such as Dale Walker 1996, you define the data type using formal mathematical logic. Wikipedia is a secondary source, in which case they cite the official literature, which specifically makes mention of at least one set and at least one operation that can be performed on that set where you can manipulate an element of that set. A Collection is not an ADT because a collection is it doesn't spell out the implementation of a concrete data type because the elements of most math sets are often impossible to code. I came to this wiki because I'm writing the ASCII Data Specification to find the formal mathematical logic and language to reference for my specification. When I found it was not here it was like I was in an alternate reality. Every math article on Wikipedia is EXTREMELY detailed with set theory and logic and pretty graphs, and then there this wiki page, which makes no mention of the word set or an operation on a set outside of methods of a hash table, which isn't an ADT, it's a data structure. Every set has a domain and a codomain, so what's in the domain of the codomain of an Associative Array? I know because I'm a computer scientist, other people, however, do not know and when they go to the Wiki they should learn computer science, not computer programming.

The second order of business, the Wiki incorrectly states that a map is an Associative Array. That is like saying that all share circles. Every dictionary is a map but not every map is a dictionary. The article makes this mention because the C++ STL use map<Char,T> which is actually a map of strings to type T. That doesn't mean that a map is a dictionary. A map is like in set theory, a very well defined mathematical structure. The next question for the C++ folks is the map<Char,T> an Associative Array with Unique keys or is it an Associative List with duplicate keys? And so does this map do a map of integers to floating-point numbers? They called it map for a very silly reason and C++ isn't an ADT specification and thus should not be used to name the dictionary a map.

Fourth, a Key is not a thing in math. A string is a well defined mathematical construct. A "binding" to is not a math word, but mapping is. Its something you do when you map a key to a value in a dictionary.

As you can see, there are some MAJOR problems with this article that require it to be completely rewritten. What did Dale and Walker 1996 say about the dictionary? Let's see the citation. Here is a mathematical model of a dictionary that should be included in the Wiki. We have a domain with some unique strings, we have codomain, both sets include the empty set, and we map the strings in an onto configuration to the instances of objects in the codomain. This is not debatable, this is a mathematical fact.

File:Wiki associative array.png

— Preceding unsigned comment added by KabukiStarship (talk • contribs) 07:29, 12 August 2019 (UTC)

Here is a more scientifically correct definition, which I apologize about being rude, I'm new and drink too much coffee.

In computer science, an associative array, symbol table, dictionary, or collection of (unique-key, value) tuples is a surjective abstract data type that maps a set of unique strings in the domain, typically called Keys or Symbols, to instances of objects or the empty set in the codomain, typically called Values. The association between a Key and a Value, called a Key-value tuple, is referred to in Set theory as a "mapping", and the same word mapping may also be used to refer to the process of modifying an existing mapping, known as remapping and where remapping a Key to the empty set is referred to as Unmapping. A Key-value tuple is a Surjective mapping because each member of the Codomian is mapped to at least member of the domain such that for each member of the domain Key->Value.

Key->Value is the definition of a Surjection. — Preceding unsigned comment added by KabukiStarship (talk • contribs) 15:55, 12 August 2019 (UTC)

Sorry, that definition is wrong in several ways.

• Associative arrays in general are not surjective. For example, with a domain of 1..5 and a codomain of 1..5, the following are all valid associative arrays: [], [1=>5, 2=>4], [1=>2, 2=>2].
• The domain of an associative array is not necessarily a set of strings. It may be integers, booleans, or various other types.
• Neither keys nor values need be objects. They may be simple values like integers. (In some languages, integers are objects; in others, they are not.)
• "Mapping" and "remapping" do not mean modifying an existing associative array.
• Mapping something to the empty set is not the same as deleting a mapping.

--Macrakis (talk) 16:17, 12 August 2019 (UTC)

You are 100% wrong and I'm going to have to call out your credentials. I actually write ADT specifications. An associative array maps a string, no an integer, your example is of a map from an integer-> an integer. The term array in Assocaitiave Array means that each string acts like an array index. If you allow duplicate keys it's called an Associative List. These things have formal definitions. — Preceding unsigned comment added by KabukiStarship (talk • contribs) 16:33, 12 August 2019 (UTC)

You have an array of Key-Value tuples, it's surjective by all accounts. Look, please note the empty set is always mapped to the empty set because the function always returns the empty set: [{∅->∅} {"Foo"->∅} {"A"->3} {"B"->2} These are all Key-Value pairs. Every value in the domain, ∅, "Foo", "A", "B" all have Key-Value mappings into the codomain. Mind you, and Bijection is also called a Bijection surjective mapping because it is both Surjective and Bijective. — Preceding unsigned comment added by KabukiStarship (talk • contribs) 16:40, 12 August 2019 (UTC)

Key → Value is a one-to-one (injective) and onto (surjective) mapping of a set Key to a set Value. — Preceding unsigned comment added by KabukiStarship (talk • contribs) 16:42, 12 August 2019 (UTC)

I think I understand where the confusion is coming from. A Dictionary is a type of surjective map that contains a set of unique strings in the domain mapped to a set of objects or the empty set in the codomain. My definition needed to get unpacked.

Here is the compile error. Examples of Collection lists, sets, multisets, trees, and graphs. This was copy and paste from Wikipedia. The definition says it's a Dictionary is a Collection of key-value tuples... COMPILE ERROR. Insert definition: An Associative Array is a list, sets, multisets, trees or graphs of key-value tuples... THIS DOES NOT COMPUTE! So is it a tree of key-value tuples where the key only appears once?

Update: I have found source literature from the Association for Computing Machinery that proves my case. In fact, . For example, page 208 of Erich 1982 reads "Let set be the category of sets with functions as morphisms. If S ~ I set I (the class of objects in set), we denote by sets the comma category whose objects are functions, 4 :.4 -~ S, S f'Lxed, and morphismsf:,4 --~ B are functionsf:~,/--, B such that .4 =fB (cf. Figure 1). Morphism composition is written from left to right, that is, xfg instead of the conventional g(f(x))."

We're not big on credentials here on WP, but since you asked, I have a Ph.D. in computer science from Harvard.

It is possible that some author in the context of some particular ADT formalism defines things the way you say, but it is not the generally accepted definition. --Macrakis (talk) 20:11, 12 August 2019 (UTC)

Thank you, friend. Here is my dilemma. I'm writing an ASCII Data Specification, which is a concrete specification of ADT in contiguous memory-optimized for CPU cache performance and stack-to-heap operation. I need to find the formal mathematical definition of an associative array and other ADT so I can implement the Algebra for the ADT so I can get an ISO specification. A collection as an ADT is defined as a set that can be implemented as a concrete data type. The ASCII Data Specification starts out with an ASCII Map, which is a bijective map of one Plain-old-data type to another POD type, as in a map in set theory. An ASCII Map is not an associative array, nor will it ever be. In order to create an Associative Array, we use a mechanism that facilitates the creation of either a Dictionary or an Associative List. List in computer science allows duplicate entries while an array does. An Ascii List is a Type-Value tuple Array. We can make an array of strings called an ASCII Loom with an ASCII Map of most off, or we can make an ASCII Table, which is a bijective associative array that uses an ASCII Map to map to either an offset to the Value, or if it's negative then it's an index in the collisions pile. We can create an Associative List called an ASCII Book that uses an ASCII Loom for fastest push-back performance, then later convert it to an ASCII Table so you can use a hashtable after you've pushed all the Values back. All of these data types are ADTs. When you implement them you see that you need to have an Algebra in order to define what can and can't be in the collection on the target platform to create a collection. All of these data types have well-established definitions. Who's definition of a map is wrong? Is a C++ map just a map, or is it a map<Char,T> where they map strings to type T. It's not just called a map, and we have conflicting definitions. The only way to settle this is to cite the original source and provide the math proof so none of us can argue with it. — Preceding unsigned comment added by KabukiStarship (talk • contribs) 18:01, 13 August 2019 (UTC)

Sorry, your post makes no sense, uses a lot of non-standard terminology, and in any case isn't appropriate for a Wikipedia Talk page (WP:TALK, WP:NOTFORUM). Please find some other forum to discuss your project. --Macrakis (talk) 22:53, 13 August 2019 (UTC)

That's what I said! Incoherent. What a relief to see I'm not alone. I tried my best to stop the incoherence from creeping into the article. 185.213.154.172 (talk) 00:42, 14 August 2019 (UTC)

It's not incoherent if you are a computer scientist. A map is not a dictionary, a dictionary is a type of map; there is nothing incoherent about that; a shape is not a circle, and a circle is a shape but when you reverse the order of the words you completely alter its meaning and make it incoherent. The Wiki currently reads a "dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection." When you define something you're supposed to start out with "a dictionary is a...", in which case you would say it's a type of map. An object that "contains a collection unique key-value tuples" is quite a bit different than a map of Key-Value tuples.

The reason I need the algebra for the ASCII Data Specifcaiton is that I am able to prove using many methods, such as Design by Contract, that an ADT meets the ADT specification, and this should be in Wiki because it's part of the Computer Science of an Associate array, which is a type of map, not a map. There is an algebra that I can use a Unit test framework that allows me to prove mathematically that the ADT performs the functions. This then allows me to get standardized for use in aerospace technology. I cite sources, others have only voiced opinions. You can't just voice an opinion, you have to prove things and cite sources like I have.

If the map is a component that exists in the List, Array of Strings, Associative List, Associative Array, that means the Associative Array is not a map; I can factor the Algebra out. When the C++ Standards Committee named it map they meant a math map of a string to type T, they never intended to call a dictionary a map, where is the source of this false information? Cite who originally started calling it a map and you'll see it's a secondary source, not a primary source, and C++ is NOT considered a primary source Computer Science terminology. The map is a set in the domain with mappings, not bindings into the codomain set; if I'm right about that the wiki is wrong. The Values are the codomain; prove me wrong don't just voice an opnion. I didn't make this up, it's well-established math terminology. A collection, on the other hand, is defined on Wikipedia as:

"In computer science, a collection or container is a grouping of some variable number of data items (possibly zero) that have some shared significance to the problem being solved and need to be operated upon together in some controlled fashion."

This definition differs greatly from the Dale Walker 1996 definition that "class of objects whose logical behavior is defined by a set of values and a set of operations". So what is the set of values and what is the set of operations? This is from Wikipedia. The Wiki for ADT says:

"In computer science, an abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations."

A Collection by definition isn't a mathematical model for an associative array, that model would call it a type of map and refer to it as mapping as everyone else in math does. A tree is a type of Collection, and you can make a dictionary out of it, but the sets aren't the same, the tree is a parent-child_left-child_right-key-value 5-tuple, not a key-value 2-tuple, and the tree is then a morphism of the map, which maps it a map, not a collection of key-value tuples. That makes the definition on Wikipedia incoherent. I did author the world's fastest integer-to-string algorithm, the Puff Algoihrm, and the fastest pointer alignment algorithm (Google Puff Algoihrm and look in the wiki), I have some street cred in Computer Science with discrete math.

Even computer scientists can sometimes make their point concisely rather than leaving huge impenetrable walls of text. Doing so might help you be more successful at making your point (whatever it is). —David Eppstein (talk) 21:45, 14 August 2019 (UTC)

This has to be one of the funniest things I've read so far this year. Well done! 185.213.154.172 (talk) 11:23, 15 August 2019 (UTC)

@KabukiStarship: How exactly do you know that I'm not a computer scientist? Why else do you think I would be interested in associative arrays? How do you know that I'm not Donald Knuth? I'm not going to answer your questioning of my credentials, since I value my privacy, and your not worth it. Unprovoked, you insulted Stavros and his exceedingly polite countering of your ramblings with: "You are 100% wrong and I'm going to have to call out your credentials. I actually write ADT specifications." Then when you found out he has a Ph.D. in computer science from Harvard, you ask for his help with your personal project like this is a forum for your entitled personal use. Then when the Ph.D. called your comment incoherent (i.e. that "your post makes no sense"), you attack the credentials of the next editor. Competence is required, not fancy titles nor formal education. Self awareness of ones competency level is part of such competence: "the ability to understand their own abilities and competencies, and avoid editing in areas where their lack of skill and/or knowledge causes them to create significant errors for others to clean up." You've contributed nothing constructive to Wikipedia so far (I've checked your entire edit history). Please stop wasting everyones time with your incoherent ramblings and edits. You don't even sign or indent your comments. 185.213.154.172 (talk) 11:21, 15 August 2019 (UTC)

"I have some street cred in Computer Science with discrete math". Citation needed. 185.213.154.172 (talk) 11:34, 15 August 2019 (UTC)

You urged me too google "Puff Algoihrm". So I did. Associating yourself with Cale Jamison McCollough from Eugene, Oregon (archived), isn't helping your case. Let's just say that your claims to "the world's fastest integer-to-string algorithm" and "the fastest pointer alignment algorithm" really needs multiple reliable sources, if I'm to believe you. Your flex backfired, in a spectacular fashion. Please stop questioning other editor's credentials, in your obvious delusions of grandeur. 185.213.154.171 (talk) 13:43, 15 August 2019 (UTC)

I can lie about having a Ph.D. too, but the fact is that I did optimize out more than half of the division instructions and I did reduce the number of instructions of the pointer alignment algoihrm to 3 instructions using discrete math and I did cite proof and you did cite my name. I'm the only one here who has any credentials writing ADT specifications. Yes or no questions: Do not respond unless you address each point and cite the point:

1. Is a map implementation of the concrete implementation of the Abstract Data Type called a Dictionary? (hint: Yes)

2. Is an ADT a mathematical model for a data type? (hint: yes)

3. Is a map a mathematical model? (hint: yes)

4. Can I define a dictionary as a map of unique keys int the domain to values in the domain? (hint: yes)

5. Is it proper to define a map as a map of unique keys int the domain to values in the domain? (hint: no)

6. Is a concrete implementation of an ADT called a dictionary the name of the ADT called a dictionary? (hint: no) — Preceding unsigned comment added by KabukiStarship (talk • contribs) 23:46, 16 August 2019 (UTC)

A map is a concrete implementation of the ADT called a dictionary. A normal Array in C++, where the domain is integer indexes starting at 0, the model for that is a map... that makes it scientifically inaccurate. I want to see names and degrees. I'm the only one with any research innovations in this field here. Cite who first started calling it a map else it's false. — Preceding unsigned comment added by KabukiStarship (talk • contribs) 23:43, 16 August 2019 (UTC)

Also answer these:

6. Is a collection of type-value tuples with no mappings from the key to the value a map? (hint: no)

7. Is mapping the proper math term for the math model called a map? (hint: yes)

8. If it's called a mapping then is it a map? (hint: yes)

9. Is the name of a Concrete implementation of an ADT (i.e. map) the same thing as the ADT? (hint: no)

Thus we must conclude that not every doctor is correct about everything, and the world is a better place when we all use the proper scientific terms to describe a math model (like an ADT). I do write ADT Specifications thank you very much, but I'm not a doctor and I am looking for help. So I have a right to be on record with my science. — Preceding unsigned comment added by KabukiStarship (talk • contribs) 00:18, 17 August 2019 (UTC)

Here is all the proof we need here, it doesn't matter about pull, math geeks UNITE! The C++14 Standard Section 23.4.4 defines a "map is an associative container that supports unique keys (contains at most one of each key value) and provides for fast retrieval of values of another type T based on the keys. The map class supports bidirectional iterators."

The C++ Standard defines a concrete implementation of the dictionary ADT and the ASCII Data Spec defines the memory layout for a POD-to-POD map that we then use to create a Concrete implementation of the dictionary ADT, and soon it will have the Axioms to verify conformance to the ADT spec, and thus they are both concrete implementations and neither is the ADT known as a dictionary. I apologize for being rude and for the wall of text, but it is a verifiably true and worthy debate.

@KabukiStarship: There is currently a discussion at Wikipedia:Administrators' noticeboard/Incidents regarding an issue with which you may have been involved. 185.213.154.172 (talk) 17:54, 18 August 2019 (UTC)

Lisp

How is a value accessed in Lisp? --Hirzel

Simple answer: For a hash table, (gethash key table). For an alist, (cdr (assoc key alist)).

Complex answer: gethash actually returns two values. (Functions can do that in Lisp -- and no, it isn't the same as returning a pair or list of two elements as a value. If you don't ask for the second value, it is discarded.) The first is the value of the key in the table, or NIL if there is not one. The second is a boolean, T if the key was in the table, and NIL if it was not. This is so you can tell a NIL that was a hash value from a NIL that indicates failure.

Example:

(multiple-value-bind (result success)
   (gethash 'moose *some-hash-table*)
   (if success
      (print result)
      (print "Not found.")))

That will print "Not found" if there wasn't a key moose in the hash table *some-hash-table*. --FOo 22:38, 16 July 2003 (UTC)

---

It is not correct to say that Lisp uses alists for associative arrays. Common Lisp has a native, typed, hash table type which is the closest match to other languages' dictionaries or hashes. Alists are simply a shape of list for which there are some associative-like operations; they're used where a hash table would be too much overhead or complexity, not as a replacement for more general associative arrays. --FOo 16:16, 16 July 2003 (UTC)

My changes

I've done some pretty severe reorganization of this page. As usual I wanted to separate the theoretical stuff from the language-specific stuff. I also added a lot more about data structures used to implement associative arrays and the relative tradeoffs, and some links to the STL pages about the abstract data type and their hash table/red-black tree map implementations. Added a little note about Lua also. I hope my splitting apart and editing of the associative list section pleased the one person above, and didn't anger anyone. I'd appreciate any feedback on my changes.

Derrick Coetzee 03:01, 25 November 2003 (UTC)

---

To 62.134.120.20, if you read this, I feel like many of the links you added were either:

• highly ambiguous (like "time")
• misleading, incomplete, or pointing to unrelated topics (as in "real time")
• incorrect, referring to an article which does exist by the wrong name
• redundant, referring to an article recently referred to again
• rarely used phrases which only happened to occur in the text

While I encourage effective cross-linking of material, bad cross-linking frustrates and obscures. Please exercise more discretion in the future when adding links. I refer you to some of Wikipedia's policy on links:

http://en2.wikipedia.org/wiki/Wikipedia:Make_only_links_where_relevant

Derrick Coetzee 08:28, 6 December 2003 (UTC)

for key in phonebook

I note that someone change the Python example loop to:

for name in phonebook:

instead of:

for key in phonebook

I deliberately choose key to emphasize that iterating over the phonebook dict iterates over all its keys. — Preceding unsigned comment added by Paddy3118 (talk • contribs) 15:22, 17 April 2006 (UTC)