News for hackers. Stuff that matters.

A comment on A new fast hash table in response to Google’s new fast hash table. Parent comment

Re:A new fast hash table in response to Google’s new fast ha... by ztorkelson on Tuesday May 29, 2018 @03:08PM (#17182080)
Right. When you ask "how could we support deletion of nodes", am I right to assume you mean "how could we reclaim memory of deleted nodes"?

Conventionally, a free list would be used, though admittedly that sacrifices locality which was one of the original motivating factors. To the extent that deletion is a significant component of the workload, then yeah, this doesn't help.

[ Parent | on HN ]
Re:A new fast hash table in response to Google’s new fast ha... by MaxBarraclough on Wednesday May 30, 2018 @07:16AM (#17186722)
Yes, exactly. It would of course be trivial to unlink a node without reclaiming it, but then you're leaking.

Radix trees never rotate, right? Can that be leveraged to help with locality?

[ Parent | on HN ]