3 ms·
>The simplest (but not optimal) way to do this is to just take the next one that isn't used yet. The linear probe is by far the most efficient way to build a h
by xxs 2y ago
>The simplest (but not optimal) way to do this is to just take the next one that isn't used yet.
The linear probe is by far the most efficient way to build a hashtable on any modern hardware, nothing is near close. Everything else leads to cache trashing on misses. For the nearly full table - that's a mistake - table should not go above a specific fill factor, e.g. the notorious 75% for large tables.
- yxhuvud 2y agoThe problem with the linear probe is that it creates long runs of collisions, thereby forcing you to avoid that by having a lower fill factor.
- xxs 2y ago>that it creates long runs of collisions Yes, of course. In practice it still outperforms pretty much anything else. The lower fill factor is still cheaper (memory footprint) than having buckets and indirection.