Associative array key order

Ary Borenszweig ary at esperanto.org.ar
Wed Jul 31 08:51:25 PDT 2013


On 7/31/13 12:05 PM, bearophile wrote:
> Daniel Kozak:
>
>>  is there a way for AA to behave same as PHP?
>
> D associative arrays are based on hashing, so they do not keep the order
> of the items. This is true in Python too. The Python standard library
> has a hash-based ordered dict that keeps the insertion order of the
> keys. There is no such data structure in Phobos.

However in Ruby 1.9 they are ordered.

You only need to store in each bucket entry a pointer to the next 
bucket. Then traversing the hash is super fast (just follow the links) 
while preserving insertion order. Accessing by key still uses the 
buckets and entries (if that's how AAs are implemented in D).

I don't think adding a pointer to each bucket entry hurts performance 
that much, and having traversal by insertion order is pretty common (in 
my opinion).

To see a sample code for this:

https://github.com/manastech/crystal/blob/master/std/hash.cr#L28


More information about the Digitalmars-d-learn mailing list