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.oster...@gmail.com> wrote: > > Hi RIchard, > > On 9 February 2020 at 17.54.30, Richard O'Keefe (rao...@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 > > >
