dictionarycollectionssmalltalkpharo

How is ordered a Dictionary in Pharo?


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.


Solution

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