How is ordered a Dictionary in Pharo?

Question

Let's say we have a loop that enters Associations to a Dictionary in a clear order:

| d |

d := Dictionary new: 10.

1 to: 10 do: [ :i |
    d add: i -> (i + 9 printStringBase: 20)
].

d

When I evaluate this code I get a Dictionary in a "twisted" order:

9 -> I
5 -> E
1 -> A
10 ->J
6 -> F
2 -> B
7 -> G
3 -> C
8 -> H
4 -> D

Each time a Dictionary with the same entry data is created it have the same order, so I assume it is a feature not a bug ..?

I use Pharo v9.0.21.

Answer 1

In addition to this other answer is is worth explaining the apparent disorder shown in the question.

Firstly observe that Dictionary new: 10 will create a new instance of Dictionary with capacity for a prime number p of associations greater than 10. Say 11, 13, 17, whatever.

Secondly, for every association added, the dictionary will compute the hash value of the key and deduce the location from its remainder modulo p.

Since all keys occurring in the example are instances of SmallInteger, their hashes will be themselves(*). And since these are smaller than p, they will equal the modulo and hence be stored in the slots derived from their values in some implementation-dependent way.

Finally, the printing method is free to enumerate the associations in any order.

---

(*) While this is true in some dialects, I've checked in Pharo and this is not true, 3 hash is not 3 etc. which explains the "twisting" in the case of Pharo.

Answer 2

A Dictionary is not an ordered collection. Instead it is a keyed collection, keeping key-value pairs.

There is an OrderPreservingDictionary for you to use: https://github.com/pharo-contributions/OrderPreservingDictionary

Answer 3

For completeness of the answer there is such thing as ordered Dictionary.

At Smalltalk/X the #OrderedDictionary is defined as:

Dictionary subclass:#OrderedDictionary
        instanceVariableNames:'order'
        classVariableNames:''
        poolDictionaries:''
        category:'Collections-Sequenceable'

"/     I am a subclass of Dictionary whose elements (associations) are ordered in a
"/     similar fashion to OrderedCollection.
"/     That is, while being filled via #at:put: messages (or similar Dictionary protocol),
"/     the order in which associations are added, is remembered and accessible via the #atIndex:
"/     or #order messages. 
"/     Therefore, this combines fast access via hashing with a defined order when enumerating.
"/     
"/     [instance variables:]
"/         order <OrderedCollection>       Ordered collection of keys reflecting the order of
"/                                         associations in the dictionary.
"/ 
"/     [complexity:]
"/         access by index: O(1)
"/         access by key: O(1)
"/         searching: O(n)
"/         insertion: mostly O(1)
"/         removal: mostly O(N) (because order will have O(n) behavior)
"/         
"/     [author:]
"/         Ifor Wyn Williams 
"/         Changed by: exept