Implementing Hash Tables in C
Open addressing or 'open bucket' hash tables always seem to be a second consideration in textbooks or blogs. I find them generally faster, and more memory efficient, and easier to implement. Instead we're always taught the closed bucket approach, often using linked list buckets of all things.In certain scenarios open addressing has worse performance, but with the right optimisations it's generally only contrived situations where it performs worse. In normal usage, open addressing has vastly superior locality, a smaller memory footprint, and less dereferencing overhead.A lot of writing and textbooks describing open addressing seem to imply that the order of walking through the table when collisions occur is really important (and it is). But the approach with best performance in practice is to just do a dumb increment through the table in-order because of caching... the penalty for that simple approach can be made up for with a good, pseudo-random hash.