Hacker News Reader

It's neat. I like it!

I edited my comment with some more questions, btw, likely as you were answering - apologies if that ended up confusing.

There’s no slot cycling logic. When a k,v pair at some index is deleted, and a different k,v pair has a matching hash, there’s a (small?) penalty in the hm_get logic that will eventually the right k,v pair.

I need a bit more clarification on your first question. There should be no mutation of the underlying map when it grows — we’re just allocating more room for entries and adjusting the old map’s item “ownership” — moving pointers->items around.

Nevermind — there are ways for deleting colliding items to cause other colliding items to be “forgotten”, and one solution would be to implement slot cycling on deletion

Another solution could be tombstones: When a slot gets cleared and the next slot has an item, insert a placeholder value. During linear probing, treat the placeholder as a normal item (that doesn't match); during insertion & deletion treat the placeholder as an empty slot.

Reply on news.ycombinator.com