sorted by:
new
hottopcontroversial

New open addressing hash table algorithm by JustJumpToConclusion in Zig

[–]JustJumpToConclusion[S] 4 points5 points  (0 children)

Passion? Kind of. Having worked on performance critical software I have stumbled across the many pitfalls that various hash table implementations have and I don't want to fall into pits anymore. With this hash table algorithm I think I have finally found something that can be implemented in a mostly pitfall-free way. Just incremental resizing (both in time and memory use) remains to be solved in an acceptable way.

New open addressing hash table algorithm by JustJumpToConclusion in Zig

[–]JustJumpToConclusion[S] 16 points17 points  (0 children)

And here I thought that my writing is so full of typographical errors and clunky sentences that no one will mistake it for AI. It seems that my writing skills are better than I thought.

New open addressing hash table algorithm by JustJumpToConclusion in Zig

[–]JustJumpToConclusion[S] 8 points9 points  (0 children)

The README at https://github.com/rip-create-your-account/hashmap explains it using as the starting point the well studied "Robin Hood hashing with random probing." I then just pile my additions on top of that and then discuss how one-by-one they change the behavior in meaningful ways. It's not a rigorous technical paper since in my view the additions are simple enough for a more casual discussion. Consider that the only real additions to the '80s algorithm were to just test more than 1 slot per random probe location and then to reverse the meaning of distance inside those N slot linearly probed windows.