Are Julia dictionaries (and sets) stable between runs?

Question

I know that, in Julia, dictionaries do not preserve the original ordering in which keys has been inserted as described here, but do dictionaries (and sets) constructed with a given insertion order preserve the arbitrary ordering they use between runs? This is relevant since it would mean that the arbitrary order can be assumed stable between runs, for example, if I run the following code the order is preserved

dictionary = Dict(1 => 77, 2 => 66, 3 => 1, 50 => 2)
print(collect(keys(dictionary)))

since at each run it always prints

[50, 2, 3, 1]

This is just to show what I mean, in general is this true for all key types (or even for integers)? in this question there is an answer by @PM 2Ring which describes that for Python sets this is not true for all types since

By default, the hash() values of str, bytes and datetime objects are “salted” with an unpredictable random value

score 5 · Accepted Answer · answered Mar 03 '23 at 22:53

5

The short answer is: you can't guarantee it, and shouldn't rely on it to be the case, especially across machines, version, etc.

Sets in particular follow very closely the mathematical definition of a set, and have no ordering.

If you need to rely on the order of keys or elements, you can use the OrderedCollections package, which used to be part of DataStructures. It has ordered versions of sets and dictionaries.

answered Mar 03 '23 at 22:53

Timothée Poisot

91
5

Thank for the answer! By across machines do you mean across 32 vs 64 bit architectures? – Tortar Mar 04 '23 at 15:53

score 2 · Answer 2 · answered Mar 04 '23 at 11:05

The official answer is as given by Timothée (see other answers). Having said that, it is easy to explore the insides of Julia (as it is mostly written in Julia) and find answers to such questions. For example by:

@edit Dict(1 => 77, 2 => 66, 3 => 1, 50 => 2)

By inspection (and example in OP) Dict does not use randomization in ordering elements at all (reasonable, as otherwise it would have to provide access to the random generator to allow consistent run replication). The order is determined by the hash function on the keys. This hash can change between implementations... unless you define your own. An example follows:

julia> struct MyInt
           v::Int
       end
julia> Base.hash(a::MyInt) = hash(a.v)

julia> Dict(MyInt(1) => 77, MyInt(2) => 66, MyInt(3) => 1, MyInt(50) => 2)
Dict{MyInt, Int64} with 4 entries:
  MyInt(50) => 2
  MyInt(2)  => 66
  MyInt(3)  => 1
  MyInt(1)  => 77

julia> dictionary = Dict(MyInt(1) => 77, MyInt(2) => 66, MyInt(3) => 1, MyInt(50) => 2)
Dict{MyInt, Int64} with 4 entries:
  MyInt(50) => 2
  MyInt(2)  => 66
  MyInt(3)  => 1
  MyInt(1)  => 77

julia> print(collect(keys(dictionary)))
MyInt[MyInt(50), MyInt(2), MyInt(3), MyInt(1)]

Now, redefining the hash function changes order. Note, that this hash function uses the original Int hash, but for stable use, one would define an explicit (hopefully good) hash (many sources on how to do so):

julia> Base.hash(a::MyInt) = hash(a.v)+0x89

julia> dictionary = Dict(MyInt(1) => 77, MyInt(2) => 66, MyInt(3) => 1, MyInt(50) => 2)
Dict{MyInt, Int64} with 4 entries:
  MyInt(3)  => 1
  MyInt(1)  => 77
  MyInt(50) => 2
  MyInt(2)  => 66

julia> print(collect(keys(dictionary)))
MyInt[MyInt(3), MyInt(1), MyInt(50), MyInt(2)]

Note the last Dict is printed in a different order.

Are Julia dictionaries (and sets) stable between runs?

2 Answers2