Dictionary with custom hash function

[tisztamo]

In a tight loop (50-100ns/cycle) I am using a dict filled with randomly generated UInt64 keys.

I think that they could be used directly in a hashmap, without hashing, so I am looking for a hashmap with a custom (here the identity) hash function.

I hope to gain 2.5ns per cycle:

julia> @btime hash(i) setup=(i=rand(UInt64))
  2.500 ns (0 allocations: 0 bytes)

I was not able to quickly find a package that allows that. Is there any?

[rfourquet]

It takes only a patch of few lines to allow Base’s Dict to handle that, here is a POC, where you’re welcome to comment
I don’t know of an package doing that, but if this PR isn’t merged soon enough, I will package it up.

[tisztamo]

Thanks, it would be great to have that in Base!

[stevengj]

@tisztamo

I was not able to quickly find a package that allows that. Is there any?

Just wrap your keys in a new type:

struct MyKey
    val::UInt
end
Base.hash(a::MyKey, h::UInt) = xor(a.val, h)
Base.(==)(a::MyKey, b::MyKey) = a.val == b.val

[tisztamo]

Thank you, it works!

I mistakenly thought this will have a performance impact, that’s why I asked for a solution here, but now I have learned to better embrace immutable structs!

[Oscar_Smith]

There’s a reason one of Julia’s unofficial mottos is “don’t pay for what you use”

[lewis]

I am sorry. This is missing a lot of steps for me:

How would the dict be defined?

mydict = Dict{MyKey, String}()
akey = MyKey(10)
mydict[akey] = "foo"

This seems restrictive. Key values need to be integers to convert to UInt. It’s actually slower than a normal dictionary.

I am looking for a simple and faster hashing algorithm for very small dicts (4-10 entries) that are accessed in a very lot loop. The values for each entry will never be changed–this is basically a lookup table. However, my lookup table is actually a dict of dicts. LittleDict proved to be slower than normal dict when nested.

Thanks.