# How efficient is dictionary lookup in Julia?

**URL:** <https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984>\
**Category:** Performance\
**Tags:** dictionary\
**Created:** [July 30, 2019, 2:48pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984 "2019-07-30T14:48:04Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![manuelma](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/manuelma/32/19005_2.png) [@manuelma](https://discourse.julialang.org/u/manuelma)\
**Post date:** [July 30, 2019, 2:48pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984/1 "2019-07-30T14:48:04Z")

</div>

I have an application where I have to lookup keys in a dictionary several times, and depending on the particular case it could be that I lookup the same key hundreds of times. How much overhead should I expect?

In Python dictionary lookup complexity is O(1) or so I’ve heard. What about Julia?

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [July 30, 2019, 3:16pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984/2 "2019-07-30T15:16:52Z")

</div>

Its pretty efficient.

```julia
using BenchmarkTools
using Random

n=1_000_000
mydict = Dict(i=>randstring(3) for i in 1:n);

@btime mydict[rand(1:n)] # counts the random generation as well
# 117.599 ns (1 allocation: 47 bytes)
@btime mydict[433]
# 20.692 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![fborda](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fborda/32/8654_2.png) [@fborda](https://discourse.julialang.org/u/fborda)\
**Post date:** [July 30, 2019, 3:29pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984/3 "2019-07-30T15:29:17Z")

</div>

Yes, Julia Dictionaries are implemented as Hash Tables just like in Python, so it has O(1) lookup complexity (outside of cases with lots of collisions - when many keys have the same hash, which is usually handled internally as a linked list). I think it’s mostly functional languages that occasionally implements Dicts/Maps as balanced binary trees, which gives O(log n) lookup, but plays very nice with the concept of immutable data structures.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 30, 2019, 4:21pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984/4 "2019-07-30T16:21:46Z")

</div>

> [@manuelma](#):
>
> depending on the particular case it could be that I lookup the same key hundreds of times

You could write a caching wrapper.

```julia
mutable struct CachingLookup{S,T}
    last_key::S
    last_value::T
    dict::Dict{S,T}
end

CachingLookup(d::Dict) = CachingLookup(first(d)..., d)

function Base.getindex(c::CachingLookup, key)
    c.key == key && return c.last_value
    c.last_value = c.dict[key]
end

```

(this is an untested sketch, does not handle corner cases and could be made more elegant)

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [July 30, 2019, 4:56pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984/5 "2019-07-30T16:56:28Z")

</div>

Compared to python, dictionary lookup is very fast.

Compared to specialized implementations, it’s not so fast. Part of it is that hashing and equality are complicated in julia (e.g. `0x01==1` and therefore both must have the same hash). Another part is that default hashing is not very specialized:

```julia
julia> struct x
       x::Int
       end
julia> @btime hash($x(1));
  33.641 ns (0 allocations: 0 bytes)

```

This is ridiculously slow, because it involves a non-inlined runtime call to `jl_object_id`. At some point in the future it will probably get faster (someone writes an `if @generated` fallback that treats objects as blobs of memory).

---

<div class="post-metadata">

**Author:** ![manuelma](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/manuelma/32/19005_2.png) [@manuelma](https://discourse.julialang.org/u/manuelma)\
**Post date:** [July 30, 2019, 7:23pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984/6 "2019-07-30T19:23:19Z")

</div>

So if I want a fast implementation in theory I could provide my own key type and then implement a fast version of hash for it?

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [July 30, 2019, 11:32pm UTC](https://discourse.julialang.org/t/how-efficient-is-dictionary-lookup-in-julia/26984/7 "2019-07-30T23:32:24Z")

</div>

Yes, or consider using [https://github.com/andrewcooke/AutoHashEquals.jl](https://github.com/andrewcooke/AutoHashEquals.jl)