RFC: Fix rehash check - Githubissues

JuliaCollections / OrderedCollections.jl

Julia implementation of associative containers that preserve insertion order

MIT License

92 stars 38 forks source link

Open kmsquire opened 3 years ago

kmsquire commented 3 years ago

We should(?) rehash when 3/4 of the slots have been deleted, not when 3/4 of the keys have been deleted. The previous logic caused us to rehash when, e.g., there were 5 keys and we deleted 4. The new logic requires at least 12 removals before a size-based rehash occurs.

The main bug with the previous logic was when the number of keys was less than 4, we would always rehash. See below for an alternative fix.

It's arguable what the best strategy is...

Either fix below fixes #65.

eulerkochy commented 3 years ago

Well, I'm in for this change, given that for general use cases(e.g batch deletion followed by batch insertion), this will be quite useful.