search

andyferris / Dictionaries.jl

An alternative interface for dictionaries in Julia, for improved productivity and performance
Other
278 stars 28 forks source link

Reuse deleted places in value vector #65

Open mschauer opened 2 years ago

mschauer commented 2 years ago

I was just reading along and was curious if it would make sense to reuse the position in the value vector (because indices are unique) if it corresponds to a deleted index.

https://github.com/andyferris/Dictionaries.jl/blob/69183615f4322acb38ee0138aa5aa9ce2730df77/src/Indices.jl#L391

andyferris commented 2 years ago

Filling holes (except any trailing elements) would mean we violate the insertion ordering. If we knew a hole came after every non-hole (e.g. it is the last index) we could use that index, which might work well for stack-like containers?

mschauer commented 2 years ago

Ah that’s where the order comes in, thanks. But the stack like hash table: I think a symbol table with scope context has this behavior