# Dict doesn't reuse deleted slots?

**URL:** <https://discourse.julialang.org/t/dict-doesnt-reuse-deleted-slots/45335>\
**Category:** Performance\
**Created:** [August 21, 2020, 8:20pm UTC](https://discourse.julialang.org/t/dict-doesnt-reuse-deleted-slots/45335 "2020-08-21T20:20:00Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Christian\_Rorvik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christian_rorvik/32/965_2.png) [@Christian\_Rorvik](https://discourse.julialang.org/u/Christian_Rorvik)\
**Post date:** [August 21, 2020, 8:20pm UTC](https://discourse.julialang.org/t/dict-doesnt-reuse-deleted-slots/45335/1 "2020-08-21T20:20:00Z")

</div>

I’ve come upon a performance gotcha with `Dict`, wherein large amounts of insertions and deletions cause rehashing and allocations even when the load factor is stable.

I don’t know much about hash table implementations, so maybe this is a known weakness of the algorithm chosen. I did notice `ndel` is only ever increased (in `_delete!`), then used as a condition for rehashing (if more than 3/4 slots are deleted), and then reset to 0 on rehash. Does that mean deleted slots are never re-used? I thought commonly deleted slots are treated as occupied on probe, and empty for reuse on insert.

`DataStructures.RobinDict` doesn’t exhibit the same behavior.

Code for validation:

```nohighlight
using BenchmarkTools
using DataStructures

function foo(d, reps)
    for i in 1:reps
        d[i] = 1
        delete!(d, i)
    end
    nothing
end

@btime foo($(Dict{Int, Int}()), 1000)
# 24.200 μs (249 allocations: 42.80 KiB)
@btime foo($(RobinDict{Int, Int}()), 1000)
# 33.101 μs (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [December 7, 2022, 3:52pm UTC](https://discourse.julialang.org/t/dict-doesnt-reuse-deleted-slots/45335/2 "2022-12-07T15:52:16Z")

</div>

For the benefit of future readers who may stumble on this, @Christian_Rorvik recently reported the bug in Julia: [Dict doesn't reuse deleted slots · Issue #47823 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/47823), with possible fix in [decrement `h.ndel` when overwriting deleted entry by oscardssmith · Pull Request #47825 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/47825).