[Pharo-users] Dictionary removeKey: very low performance

Kasper Østerbye kasper.osterbye at gmail.com
Mon Feb 10 13:31:05 EST 2020


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
<https://en.wikipedia.org/wiki/Open_addressing>.

Best,

Kasper
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-users_lists.pharo.org/attachments/20200210/0e85fbef/attachment.html>


More information about the Pharo-users mailing list