This is the
talk page for discussing improvements to the
Associative array article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1Auto-archiving period: 730 days |
This
level-5 vital article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
The Augmented map article was blanked on 2024-01-16 and that title now redirects to Associative array. The contents of the former article are available in the redirect's history; for the discussion at that location, see the redirect's talk page. |
Someone should describe how to insert elements into a hash table. — Preceding unsigned comment added by 71.141.127.226 ( talk) 22:39, 10 September 2006 (UTC)
So far as I can tell, Wikipedia has decided/ordained that the canonical name for the abstract data type dictionary/map/associative array is "associative array". In my opinion, this decision should be revisited. Has this been discussed before, and if so, can someone point me to it?
In any case, here's the list of pros and cons I see for the current term:
pros:
cons:
I propose that we rename this article to "Map (computer science)" and redirect "Associative Array" to that.
Just to list the alternatives, right off the bat we can say that "Hashtable" is not quite right, because it implies a particular implementation of the abstract data type.
The next runner up is "Dictionary (computer science)", which I think is a very strong candidate, since it seems to see the most use in programming language standard libraries (check the list of terms used in language standard libraries in the article). However, I don't think it sees much use in the computer science field, and while I personally prefer the name "dictionary" in my own discussions, I feel like "map" more correctly refers to the abstract data type and less to the specific task of mapping string keys to values.
How do other people feel about this?
Rkleckner ( talk) 18:16, 14 April 2010 (UTC)
-- Piotr Jurkiewicz ( talk) 17:15, 3 June 2016 (UTC)
ins(x,y)
. AFAICT this isn't a normative use of the term, but it actually agrees with Kepler's usage.Criteria | Map (computer science) | Dictionary (data structure) | Associative array |
---|---|---|---|
Recognizability | Medium (would be Low except for C++) | High | Medium |
Naturalness | Medium | High | Low |
Precision | Low | High | Medium |
Concision | 22 | 27 | 17 |
Consistency | Low | Medium | Low |
The result of the move request was: ( non-admin closure) NO CONSENSUS User:力 (powera, π, ν) 23:46, 5 February 2022 (UTC)
There is quite a bit of discussion here, but nothing resembling consensus for any particular move -- and the discussion is too broad for a re-list to solve this. This should be discussed on a WikiProject before there is a re-nomination, but no prejudice against a re-nomination in March. User:力 (powera, π, ν) 23:46, 5 February 2022 (UTC)
– See my reasoning above for renaming associative array to dictionary. As for the rest, I think that leaving out "abstract" is more WP:CONCISE. Also, the word "abstract" adds confusion when the concrete data structure / syntax in many languages is also called list, set, etc. and this concrete implementation is discussed in the article, e.g. the list in Set_(abstract_data_type)#Language_support Mathnerd314159 ( talk) 23:59, 26 January 2022 (UTC)
I tend to support this but it may not work well for stack
s... I suggest we pursue global RFC for this. I also would like to refer you to
Abstract data type article to get sense of rationale behind titles. Courtesy pinging @
TuukkaH:. He had pretty good summary on differences here:
Talk:Data type#Topic of this article.
AXONOV
(talk)
⚑
09:27, 27 January 2022 (UTC)
I disagree with the rename of Tree (data structure) to Tree (data type). The terms "tree data structure" and "tree data type" denote different notions. The difference is described in Tree_(data_structure)#Data_type_versus_data_structure and Rose_tree#Tree_data_type. The latter page states the following relationship between the terms:
Moreover, the page also provides a diagrammatization of the difference between a "tree data structure" and a "tree data value". Hundblue ( talk) 17:14, 30 January 2022 (UTC)
I think the 3 terms denote distinct notions.
d1 = {"a":5}
d2 = {"a":5}
Consider the JavaScript / Ruby / Python code shown in the box on the right in which dictionaries d1
and d2
are created. (The respective terminology for "dictionary" is "object" / "hash" / "dict".) The following is satisfied:
d1
and d2
are not the same, since applying d1["a"] = 7
will affect only d1
.
d1
and d2
have the same value. In Ruby and Python, this can be verified by the value comparison operator ==
(i.e., in these two languages, d1 == d2
evaluates to true
or True
).
The dictionaries d1
and d2
are not data types - instead, they are instances of a single built-in dictionary type (named respectively Object
/ Hash
/
dict
– "the dictionary").
Conclusion: Instead of the rename Associative array → Dictionary (data type) (which I disagree with) I suggest Dictionary (data structure). -- Hundblue ( talk) 22:31, 1 February 2022 (UTC)
I find it questionable whether the article (in the current state) is mostly about the (API-defined) data type. There is a #Properties subsection that provides an adaptation of the "Formal Definition" from [13]. (Interestingly, the page is subtitled "(data structure)".) The definition does not state explicitly if multiple empty dictionaries are possible, but since there is a magical new operation which "creates a new empty dictionary" one can perhaps infer that there are (infinitely?) many empty dictionaries. Assuming that, there is a problem with the equality sign (=) in the definition. Is new() = new() satisfied (as suggested by the remove(k, new()) = new() condition)? Is insert(k, v, D) the same dictionary as insert(k, v, remove(k, D))?
In my opinion, a more rigorous alternative to the above can be obtained by the following definition:
Alternatively, one can first define a dictionary context 𝒞 = (X, K, V) and then define a 𝒞-dictionary to be a pair (x, R) with the same constraints as above. The set (denote it 𝒟) of all 𝒞-dictionaries makes up for a "dictionary type". This set 𝒟 is not itself a dictionary. One can define "API" operations:
The operations remove and insert preserve "identity" (only the map is changed, not the node) like corresponding operations in JavaScript / Ruby / Python.
Note that there is a distinction between a dictionary (an element of 𝒟) and a node (an element of X). That is, in the JavaScript / Ruby / Python code d1 = {"a":5}
, d1
is not a dictionary but a node. After the insert operation d1["a"] = 7
, the d1
node is the same like before the operation. What has been changed is the associated map (the R-component). That is, in JavaScript / Ruby / Python, there is a global association of nodes to finite maps. Such association can be expressed as a set 𝒜 of source-name-target triples, see
Nested dictionary.
The above text should document that at least in the JavaScript / Ruby / Python environments, there is a single common abstraction of the dictionary concept. In this abstraction, a dictionary is a mathematical structure, just like e.g. lattice in order theory. Thus, there is a reason to combine the words "dictionary" and "structure". The additional term "data" might be used for disambiguation. But I understand that the whole term "dictionary data structure" might already have established another meaning(s) - that of "implementation" structures of the dictionary concept. For this reason, I suggest to keep the current page name Associative array - which is neutral w.r.t. data-structure vs. data-type issues.
I disagree with the rename Dictionary (data type) since it incorrectly suggests that the page provides a valid definition of the term "dictionary data type". It presently does not. -- Hundblue ( talk) 13:31, 2 February 2022 (UTC)
As for the notion of an
instance, the "things" I am talking about are (direct) instances of Object
/ Hash
/ dict
in JavaSript / Ruby / Python, respectively. (There are even introspection methods or operators instanceof
/instance_of?
/isinstance
that support the term "instance".) These instances are accordingly termed objects / hashes / dictionaries. Let us use the Python term uniformly a call these objects dictionaries. As already has been demonstrated above, there is a common syntax and common characteristics of dictionaries in JavaScript/Ruby/Python. In particular:
x = {}; y = {}
, both x
and y
are empty dictionaries, but x
is not the same dictionary as y
.
x = {}; x["a"] = x
is allowed. After executing this code, x
is still a dictionary – it does not cease to be an instance of Object
/Hash
/dict
.
Now the problem with the "dictionary data type" term is that the page (named Associative array at present) does not provide a definition (or description) of such a data type (especially when viewed as a set of "instances") so that dictionaries from JavaScript/Ruby/Python would be compliant with such a definition. That is, there is no valid definition of "dictionary data type" such that dictionaries from these 3 languages would appear to be instances of that data type, in particular w.r.t. (1) and (2). -- Hundblue ( talk) 23:08, 5 February 2022 (UTC)
(From above) This should be discussed on a WikiProject before there is a re-nomination
: I started a talk page for renaming this page on
Wikipedia talk:WikiProject Computer science#Rename Associative array -> Dictionary (abstract data type)
This is the
talk page for discussing improvements to the
Associative array article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1Auto-archiving period: 730 days |
This
level-5 vital article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
The Augmented map article was blanked on 2024-01-16 and that title now redirects to Associative array. The contents of the former article are available in the redirect's history; for the discussion at that location, see the redirect's talk page. |
Someone should describe how to insert elements into a hash table. — Preceding unsigned comment added by 71.141.127.226 ( talk) 22:39, 10 September 2006 (UTC)
So far as I can tell, Wikipedia has decided/ordained that the canonical name for the abstract data type dictionary/map/associative array is "associative array". In my opinion, this decision should be revisited. Has this been discussed before, and if so, can someone point me to it?
In any case, here's the list of pros and cons I see for the current term:
pros:
cons:
I propose that we rename this article to "Map (computer science)" and redirect "Associative Array" to that.
Just to list the alternatives, right off the bat we can say that "Hashtable" is not quite right, because it implies a particular implementation of the abstract data type.
The next runner up is "Dictionary (computer science)", which I think is a very strong candidate, since it seems to see the most use in programming language standard libraries (check the list of terms used in language standard libraries in the article). However, I don't think it sees much use in the computer science field, and while I personally prefer the name "dictionary" in my own discussions, I feel like "map" more correctly refers to the abstract data type and less to the specific task of mapping string keys to values.
How do other people feel about this?
Rkleckner ( talk) 18:16, 14 April 2010 (UTC)
-- Piotr Jurkiewicz ( talk) 17:15, 3 June 2016 (UTC)
ins(x,y)
. AFAICT this isn't a normative use of the term, but it actually agrees with Kepler's usage.Criteria | Map (computer science) | Dictionary (data structure) | Associative array |
---|---|---|---|
Recognizability | Medium (would be Low except for C++) | High | Medium |
Naturalness | Medium | High | Low |
Precision | Low | High | Medium |
Concision | 22 | 27 | 17 |
Consistency | Low | Medium | Low |
The result of the move request was: ( non-admin closure) NO CONSENSUS User:力 (powera, π, ν) 23:46, 5 February 2022 (UTC)
There is quite a bit of discussion here, but nothing resembling consensus for any particular move -- and the discussion is too broad for a re-list to solve this. This should be discussed on a WikiProject before there is a re-nomination, but no prejudice against a re-nomination in March. User:力 (powera, π, ν) 23:46, 5 February 2022 (UTC)
– See my reasoning above for renaming associative array to dictionary. As for the rest, I think that leaving out "abstract" is more WP:CONCISE. Also, the word "abstract" adds confusion when the concrete data structure / syntax in many languages is also called list, set, etc. and this concrete implementation is discussed in the article, e.g. the list in Set_(abstract_data_type)#Language_support Mathnerd314159 ( talk) 23:59, 26 January 2022 (UTC)
I tend to support this but it may not work well for stack
s... I suggest we pursue global RFC for this. I also would like to refer you to
Abstract data type article to get sense of rationale behind titles. Courtesy pinging @
TuukkaH:. He had pretty good summary on differences here:
Talk:Data type#Topic of this article.
AXONOV
(talk)
⚑
09:27, 27 January 2022 (UTC)
I disagree with the rename of Tree (data structure) to Tree (data type). The terms "tree data structure" and "tree data type" denote different notions. The difference is described in Tree_(data_structure)#Data_type_versus_data_structure and Rose_tree#Tree_data_type. The latter page states the following relationship between the terms:
Moreover, the page also provides a diagrammatization of the difference between a "tree data structure" and a "tree data value". Hundblue ( talk) 17:14, 30 January 2022 (UTC)
I think the 3 terms denote distinct notions.
d1 = {"a":5}
d2 = {"a":5}
Consider the JavaScript / Ruby / Python code shown in the box on the right in which dictionaries d1
and d2
are created. (The respective terminology for "dictionary" is "object" / "hash" / "dict".) The following is satisfied:
d1
and d2
are not the same, since applying d1["a"] = 7
will affect only d1
.
d1
and d2
have the same value. In Ruby and Python, this can be verified by the value comparison operator ==
(i.e., in these two languages, d1 == d2
evaluates to true
or True
).
The dictionaries d1
and d2
are not data types - instead, they are instances of a single built-in dictionary type (named respectively Object
/ Hash
/
dict
– "the dictionary").
Conclusion: Instead of the rename Associative array → Dictionary (data type) (which I disagree with) I suggest Dictionary (data structure). -- Hundblue ( talk) 22:31, 1 February 2022 (UTC)
I find it questionable whether the article (in the current state) is mostly about the (API-defined) data type. There is a #Properties subsection that provides an adaptation of the "Formal Definition" from [13]. (Interestingly, the page is subtitled "(data structure)".) The definition does not state explicitly if multiple empty dictionaries are possible, but since there is a magical new operation which "creates a new empty dictionary" one can perhaps infer that there are (infinitely?) many empty dictionaries. Assuming that, there is a problem with the equality sign (=) in the definition. Is new() = new() satisfied (as suggested by the remove(k, new()) = new() condition)? Is insert(k, v, D) the same dictionary as insert(k, v, remove(k, D))?
In my opinion, a more rigorous alternative to the above can be obtained by the following definition:
Alternatively, one can first define a dictionary context 𝒞 = (X, K, V) and then define a 𝒞-dictionary to be a pair (x, R) with the same constraints as above. The set (denote it 𝒟) of all 𝒞-dictionaries makes up for a "dictionary type". This set 𝒟 is not itself a dictionary. One can define "API" operations:
The operations remove and insert preserve "identity" (only the map is changed, not the node) like corresponding operations in JavaScript / Ruby / Python.
Note that there is a distinction between a dictionary (an element of 𝒟) and a node (an element of X). That is, in the JavaScript / Ruby / Python code d1 = {"a":5}
, d1
is not a dictionary but a node. After the insert operation d1["a"] = 7
, the d1
node is the same like before the operation. What has been changed is the associated map (the R-component). That is, in JavaScript / Ruby / Python, there is a global association of nodes to finite maps. Such association can be expressed as a set 𝒜 of source-name-target triples, see
Nested dictionary.
The above text should document that at least in the JavaScript / Ruby / Python environments, there is a single common abstraction of the dictionary concept. In this abstraction, a dictionary is a mathematical structure, just like e.g. lattice in order theory. Thus, there is a reason to combine the words "dictionary" and "structure". The additional term "data" might be used for disambiguation. But I understand that the whole term "dictionary data structure" might already have established another meaning(s) - that of "implementation" structures of the dictionary concept. For this reason, I suggest to keep the current page name Associative array - which is neutral w.r.t. data-structure vs. data-type issues.
I disagree with the rename Dictionary (data type) since it incorrectly suggests that the page provides a valid definition of the term "dictionary data type". It presently does not. -- Hundblue ( talk) 13:31, 2 February 2022 (UTC)
As for the notion of an
instance, the "things" I am talking about are (direct) instances of Object
/ Hash
/ dict
in JavaSript / Ruby / Python, respectively. (There are even introspection methods or operators instanceof
/instance_of?
/isinstance
that support the term "instance".) These instances are accordingly termed objects / hashes / dictionaries. Let us use the Python term uniformly a call these objects dictionaries. As already has been demonstrated above, there is a common syntax and common characteristics of dictionaries in JavaScript/Ruby/Python. In particular:
x = {}; y = {}
, both x
and y
are empty dictionaries, but x
is not the same dictionary as y
.
x = {}; x["a"] = x
is allowed. After executing this code, x
is still a dictionary – it does not cease to be an instance of Object
/Hash
/dict
.
Now the problem with the "dictionary data type" term is that the page (named Associative array at present) does not provide a definition (or description) of such a data type (especially when viewed as a set of "instances") so that dictionaries from JavaScript/Ruby/Python would be compliant with such a definition. That is, there is no valid definition of "dictionary data type" such that dictionaries from these 3 languages would appear to be instances of that data type, in particular w.r.t. (1) and (2). -- Hundblue ( talk) 23:08, 5 February 2022 (UTC)
(From above) This should be discussed on a WikiProject before there is a re-nomination
: I started a talk page for renaming this page on
Wikipedia talk:WikiProject Computer science#Rename Associative array -> Dictionary (abstract data type)