Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

An associative array has many common similar names, hash, keymap, map, table, index.

It's a map of keys and values but I cannot find a reputable definition of the phrase which tells me whether a map has to have order to be an associative array.

  • What is a reputable definition of the term "Associative array"?
  • Is an associative array ordereded?

Personally I've always believed they have to be ordered because in JavaScript we claim Objects are not associative arrays because Objects are un-ordered maps of keys and values. However I may have been quoting that without a reference or a source.

share|improve this question
3  
Objects are not associative arrays, but not because they're unordered. –  Dan Ray Aug 30 '11 at 19:13
    
@Dan: Keep in mind that the examples was objects in Javascript, and then please give a reason. The analogy of JS objects with hash tables is frequent and I've never seen it disputed, and I wouldn't know why it would be disputed. –  delnan Aug 30 '11 at 20:18
    
@delnan JS objects only accept keys of type string. –  Raynos Aug 30 '11 at 20:26
    
@Raynos: Yes, they're not generic - so what? That's a restriction, and such restrictions exist in any static language without generics. But nobody said an associative array has to be generic or heterogenous even regarding the key types. –  delnan Aug 30 '11 at 20:32
    
An object is not an associative array because it is "objecty". It might be represented internally as an associative array, but who cares? You use the object accessor to get at that data rather than a hash key. It might be an assoc internally--or it might be hitting a database for all you know. Let it handle its internal structure. BUT that's still not what I'm saying in my comment above. I'm saying that the distinction between objects and assoc arrays ISN'T because of their unorderedness. Much more important things distinguish the two. –  Dan Ray Aug 30 '11 at 20:45
show 5 more comments

3 Answers

up vote 8 down vote accepted

The definition from wikipedia seems correct and general enough:

collection of unique keys and a collection of values, where each key is associated with one value (or set of values)

Not a word about order. That should be perfectly fine, as there are many good ways to implement data structures that are perfect associative arrays, only without the "ordered" requirement (if it was there). I've never heard someone claim a "tree map" (as some APIs call it because it internally uses a balanced binary tree) or hashtable isn't an associative array because it's ordered or not. Plus, most code doesn't care if the keys are ordered.

Personally I've always believed they have to be ordered because in JavaScript we claim Objects are not associative arrays because Objects are un-ordered maps of keys and values.

That logic ("AA must be ordered because Objects are not AA because Objects are not ordered") seems a bit circular. Who's we and why are you claiming this? Javascript objects are clearly hash tables, and hash tables are clearly associative arrays by the above and pretty much all other definitions. They're not ordered, yes, but that doesn't change the fact that they are collections mapping strings to objects.

And even if you managed to find a reputable source defining associative arrays to be ordered, there's plenty of people and text out there that doesn't go on that assumption. To be safe, you should explicitly add the "ordered" requirement when it matters and omit it whenever it doesn't matter (which is surprisingly often).

share|improve this answer
add comment

There seem to be two (2) questions, or perhaps two interpretations for your question that one could take:

  1. Do associative arrays, as they are defined in a theoretical sense imply any kind of ordering

  2. Is there an underlying ordering of the elements in an associative array implementation in language XYZ?

Since your question sports the language-agnostic tag, then one would naturally want to favor the first interpretation. And the answer to that is: no, associative arrays, by definition do not imply any sort of ordering of elements.

It is however true that in a specific implementation, the data structure used to implement the associative array functionality could have some underlying ordering of the elements, and it might also be the case that a clever programmer might take advantage of that ordering (assuming it is exposed or reachable by the programmer) in the process of writing a program.

The problem with this, however, is that such an implementation or clever trick would only be useful in the specific language, and quite possibly using a specific compiler on a specific architecture, and as such would not represent any thing that could be used for any usage of an associative array.

share|improve this answer
add comment

Some are, some aren't. Some systems of mapping key to value do depend on order- such as binary search trees. Some like hash maps aren't ordered. There's nothing inherent about association that implies ordering.

share|improve this answer
    
A binary search tree is NOT an associative array. (at least the data structure I think of as a binary search tree) –  Zeke Hansell Sep 6 '11 at 17:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.