Hi,
I’m doing
foo=[1]
bar=Dict(foo => 2)
push!(foo, 3)
what I was expecting from the docs is that bar[[1]] should be 2. Instead, the key is not found, and neither is (the new) foo or bar[[1,3]]. When I print bar it seems to think it does have [1,3] as a key. Is this the expected behaviour in this case? What would be an efficient way of getting the behaviour I expected?
Thanks
There is no efficient generic way of obtaining the behavior you want, in no programming language or library whatsoever. The problem is that the dictionary needs to be informed about the mutation, and the key has no way of knowing in what dictionaries it serves as key.
There could be fast APIs where you directly inform the dictionary about an intended key mutation.
Many languages don’t have your observed behavior by virtue of either forbidding mutable keys alltogether (well, duh) or by requiring that the dictionary owns the key (i.e. you cannot extract a mutable shared reference to the key, you always need to go through the dictionary to mutate it; and on insertion, you either create an implicit copy (C++ style unless you jump through std::move contortions) or hand over ownership (Rust style)).
Thanks. What I was imagining is that under the hood, Julia computes a hash for the key, and that is the actual key. Then when I mutate the key, the hash changes, but I can still access with the original hash (and therefore with the original value). At any rate, the actual behaviour is pretty strange, should one just assume that the behaviour in this case is undefined?
Just to clarify, the bahaviour I was expecting was having the value for the original key [1] defined
The problem is that probably the actual Dict implementation has to deal with hash collisions. So, after hashing the object and searching for the hash, it probably compares the key itself to all keys in that hash bucket (this is, all keys that happen to have the same hash and were stored at that Dict) and, in this process, it does not find the original value in the bucket.
Thanks, that sounds like a plausible explanation, but still I find the end result peculiar (and inconsistent with the output when printing the dict)
The problem with the output is really that you can’t see that the value and it’s hash now mismatch.
That said, you can use other kinds of Dicts. If you can keep the reference to foo alive, then an IdDict may just do what you want:
julia> foo = [1]
1-element Vector{Int64}:
1
julia> bar = IdDict(foo => 2)
IdDict{Vector{Int64}, Int64} with 1 entry:
[1] => 2
julia> bar[[1]] # does not work in IdDict
ERROR: KeyError: key [1] not found
Stacktrace:
[1] getindex(d::IdDict{Vector{Int64}, Int64}, key::Any)
@ Base .\iddict.jl:93
[2] top-level scope
@ REPL[3]:1
julia> push!(foo, 3)
2-element Vector{Int64}:
1
3
julia> bar[foo] # but this works now
2
This is one of the ways to solve it, but it seems that, in his case, he ends up mutating the array used for the key, and does not want the mutated array to be able to recover the stored value, but instead any array that compared to equality to the key vector in its original state.
My suggestion would be something like:
function my_assign(d, v, k)
if haskey(d, k)
d[k] = v
else
d[deepcopy(k)] = v
end
end
You probably can create a Dict wrapper that has this behavior. I think it is the safest, while not the most performant. The most performant alternative would be code carefully to never mutate keys, or only do so when you do not care about accessing that position in the Dict anymore.
Yes, precisely, I wanted [1] to always be the same key, no matter how it’s represented internally. I ended up not mutating the foo, and instead creating a new copy, as suggested.
Just for reference, there are dictionary representations where you can mutate the key and still find it (by the new value). OrderedCollections: LittleDict does that. On the negative side, this involves checking all keys in order until a match or no match is found, so these Dicts get really slow with too much entries.
This kinda challenges my definition of what a Dict is, but I understand that it is called this way, it appears to be a Dict externally no matter how it is implemented internally.