3 ms·
I mean "Hash-set with Linked List" vs "Hash-set with linear probing". I realize I was getting lazy with my typing, so lemme try to be more clear this time. Has
by dragontamer 6y ago
I mean "Hash-set with Linked List" vs "Hash-set with linear probing". I realize I was getting lazy with my typing, so lemme try to be more clear this time.
Hash-set with Linked List is O(1) all cases.
Hash-set with linear-probing is O(n) worst-case insertion. But happens to be faster in practice with circa 2020-style CPUs (especially with Robin Hood insertion)
Assume the load-factor to be 90%+, so that we actually get a reasonable difference between the two strategies. We have a situation where O(n) is better than O(1).