Embed Notice
HTML Code
Corresponding Notice
- Embed this notice@pry
> a common argument against why a hashtable shouldn’t be included in the standard library is that there is no “one size fits all” hashtable.
hopscotches are more or less that, but people tend to use trees over hashes anyway since they're a bit more.. compact and reliable i guess? hashes are fast but you'll waste space with empty buckets and occasionally get slammed with a rehash. still, i use hopscotches i implemented in nim quite a bit :blobcatshrug:
a hopscotch is basically linear probing with a small distance limit, it stores the offset from a bucket to its native location so it can toss an entry around within that 'neighborhood' to fit more stuff in. martin ankerl has articles on it. i gave up on fixing my cuckoo implementation because hopscotches are basically the best i've read to date on hash tables.