Understanding Dict

General Usage
1

Hi everyone.

I am coming from python background. In python, dictionary keys cannot be mutable because it is based on hash table. However, keys in Dict in julia do not need to be immutable. I wonder how this is achieved?

2

mutating keys in a way that changes the hash is undefined.

3

Translation: Python protects the user from him/herself. Julia lets you shoot yourself in the foot. :smiley: (Basically, if a programmer uses a mutable as a key in a Dict, she needs to know to not mutate it in a way that changes the hash, as @yuyichao pointed out.)

Cheers!

Kevin

1 Like
4

Then why this works?

julia> d = Dict()
Dict{Any,Any} with 0 entries

julia> a = [1, 2, 3]
3-element Array{Int64,1}:
 1
 2
 3

julia> d[a] = "test"
"test"

julia> a[1] = 4
4

julia> d
Dict{Any,Any} with 1 entry:
  [4, 2, 3] => "test"

Hash of an array is not related to its content?

5

Here is your test case with one additional instruction to show that d is actually broken:

julia> d = Dict()
Dict{Any,Any} with 0 entries

julia> a = [1,2,3]
3-element Array{Int64,1}:
 1
 2
 3

julia> d[a] = "test"
"test"

julia> a[1] = 4
4

julia> d
Dict{Any,Any} with 1 entry:
  [4, 2, 3] => "test"

julia> d[a]
ERROR: KeyError: key [4, 2, 3] not found
Stacktrace:
 [1] getindex(::Dict{Any,Any}, ::Array{Int64,1}) at .\dict.jl:474
6

It “works” because the table is maintaned and allows Base.show to function, but other things break because d will be in an inconsistent state. Try eg d[a].

Also, there is a distinction between “not guaranteed to work” and “guaranteed to break”. The latter was not implied.

7

Right, and that’s what undefined means. The language/compiler/whatever can do whatever it want after something undefined happens. It can pretend things still works or it can crash randomly or it can silently fix itself later.

8

Thank you.

I have another question though: Are keys of ObjectIdDict guaranteed not to be garbage collected?

9

Anything you can access as an object in julia will not be garbage collected. This certainly include keys of ObjectIdDict but not when you get a pointer to the object by pointer_from_objref.

10

This isn’t true of Python. It will certainly also let you define invalid hash functions with the same undefined (and generally memory-safe) behaviors as Julia.