4 ms·
It looks like the result only matters in the case where the hash table is close to full. But couldn't one just deal with this case by making the table size 10%
by dooglius 2y ago
It looks like the result only matters in the case where the hash table is close to full. But couldn't one just deal with this case by making the table size 10% bigger? (Or, if it is resizeable, resizing earlier)
- nhumrich 2y agoYes, which is what most real world hash tables do. They resize themselves once hash collision is too probable.
- xxs 2y agoIn reality 75% is the standard fill factor for linear probe that also exhibits the best locality (if the table gets too full it just allocated double (or x) the memory, and copies the existing entries). Most non-linear probe tables (e.g. cookoo) suffer due to the fact RAM is not 'random' at all.