My Dictionary and Set implementations (neither of which inherits from the other) grow but do not shrink. It's easy enough to do, I just have not bothered because I have a significant redesign that improves space and time that needs finishing. I've used the marking-deleted-entries technique in the past. I'd prefer not to do it again. On Tue, 11 Feb 2020 at 07:31, Kasper Ãsterbye <kasper.osterbye@gmail.com> wrote:
Hi RIchard,
On 9 February 2020 at 17.54.30, Richard O'Keefe (raoknz@gmail.com) wrote:
My library uses separate chaining (https://en.wikipedia.org/wiki/Hash_table#Separate_chaining) which makes deletion simple and fast and allows 'null' keys.
Does your implementation use a fixed number of buckets, or do they grow (and shrink)?
I had been wondering about doing an open addressing with items marked as deleted to see how it would perform.
Aka "Another technique for removal is simply to mark the slot as deleted. However this eventually requires rebuilding the table simply to remove deleted records.â from https://en.wikipedia.org/wiki/Open_addressing.
Best,
Kasper