Associative array key order

[bearophile]

Ary Borenszweig:

> 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).

If it's a singly linked list how do you remove a key from the 
associative array keeping the list coherent? How do you know 
where is the precedent to remove an item from the linked list?
Using the 'deleted' tag on AA items is enough to skip the deleted 
items when you scan the singly linked list, but when you re-use 
that space I think you mess things up. One way to solve it is to 
never re-use locations, but this is bad if you want to add and 
remove many items.


> 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).

Python has such data structure in the standard library, and 
thanks to dynamic typing it's transparently compatible with 
associative arrays, so when you need it you have it.
I have often needed such data structure, but it's not always 
needed, I need it probably less than 5% of the times.
Python uses associative arrays all the time, they must be as fast 
as possible, so it's a good idea to not add that feature to the 
standard associative arrays. This is true for the built-in 
associative arrays too, despite they should be designed for 
flexibility first and despite D doesn't use associative arrays 
for basic language purposes, as Python does (symbol lookup for 
variables!).

I have added a small enhancement request to Bugzilla:
http://d.puremagic.com/issues/show_bug.cgi?id=10733

Bye,
bearophile