Associative Array : PHP/C vs Flex/Flash

Question

In PHP an Associative Array keeps its order.

// this will keep its order in PHP
a['kiwis']
a['bananas']
a['potatoes']
a['peaches']

However in Flex it doesn't with a perfectly valid explanation. I really can't remember how C treats this problem but I am more leaned to believe it works like php as the Array has it's space pre-reserved in memory and we can just walk the memory. Am I right?

The real question here is why. Why does C/PHP interpretation of this varies from Flash/Flex and what is the main reason Adobe has made Flash work this way.

Thank you.

Answer 1

There isn't a C implementation, you roll your own as needed, or choose from a pre-existing one. As such, a given C implementation may be ordered or unordered.

As to why, the reason is that the advantages are different. Ordered allows you (obviously enough) to depend on that ordering. However, it's wasteful when you don't need that ordering.

Different people will consider the advantage of ordering more or less important than the advantage of not ordering.

The greatest flexibility comes from not ordering, as if you also have some sort of ordered structure (list, linked list, vector would all do) then you can easily create an ordered hashmap out of that (not the optimal solution, but it is easy, so you can't complain you didn't have one given to you). This makes it the obvious choice in something intended, from the early in its design, to be general purpose.

On the other hand, the disadvantage of ordering is generally only in terms of performance, so it's the obvious choice for something intended to give relatively wide-ranging support with a small number of types for a new developer to learn.

The march of history sometimes makes these decisions optimal and sometimes sub-optimal, in ways that no developer can really plan for.

Answer 2

For PHP arrays: These beasts are unique constructs and are somehow complicated, an overview is given in a slashdot response from Kendall Hopkins (scroll down to his answer):

Ken: The PHP array is a chained hash table (lookup of O(c) and O(n) on key collisions) that allows for int and string keys. It uses 2 different hashing algorithms to fit the two types into the same hash key space. Also each value stored in the hash is linked to the value stored before it and the value stored after (linked list). It also has a temporary pointer which is used to hold the current item so the hash can be iterated.

In C/C++, there is, as has been said, no "associative array" in the core lanuage. It has a map (ordered) in the STL, as will be in the new standard library (hash_map, unordered_map) and there was a gnu_hash_map (unordered) on some implementations (which was very good imho).

Furthermore, the "order" of elements in an "ordered" C/C++ map is usually not the "insertion order" (as in PHP), it's the "key sort order" or "string hash value sort order".

To answer your question: your view of equivalence of PHP and C/C++ associative arrays does not hold, in PHP, they made a design decision in order to provide maximum comfort under a single interface (and failed or succeeded, whatever). In C/C++, there are many different implementations (with advantages and tradeoffs) available.

Regards

rbo