AA deterministic order ?

cym13 via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Wed Nov 25 12:44:26 PST 2015


On Wednesday, 25 November 2015 at 20:24:25 UTC, user-6431 wrote:
> I know that AA items order does not follow the additions but is 
> the order deterministic ?
>
> For example for a given set of items, will they always be 
> ordered in the same way ? (I mean whatever is the way I append 
> them to the AA).

No it's not. The way it works is that a hash of the key is 
computed and the comparison of hashes gives the position of the 
new AA element in the structure. Two keys can have the same hash: 
in case of collision the later is put to another place, so the 
order is dependant of the order of insertion.

Either way you can't and shouldn't rely on any sort of 
determinism with the order of AA keys, that's just not the way 
they work and any determinism is subject to change.

On another note if the subject proves interesting to you you may 
want to read the AA implementation ( 
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d ) and see this video which describes how it works in python (not exactly the same as in D but the spirit is there and the video is of quality anyway): https://www.youtube.com/watch?v=C4Kc8xzcA68


More information about the Digitalmars-d-learn mailing list