[Pharo-users] Dictionary removeKey: very low performance

Richard O'Keefe raoknz at gmail.com
Tue Feb 11 15:00:40 EST 2020


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



More information about the Pharo-users mailing list