3 ms·

I don't think it is the same thing. Inserting into linked list assumes you have found the node to insert in. I don't remember exact details but in hash set wi

I don't think it is the same thing. Inserting into linked list assumes you have found the node to insert in. I don't remember exact details but in hash set with linear probing, the worst case happens quite rarely given the hash function is good one (which are quite sophisticated these days). It is O(1) amortized. The same applies for hash table with chaining too, that all of your keys may go to same bucket given a sufficiently bad hash function. Given the other choices, like (as far as I know) SkipList based or tree based variants, hash sets are obvious choice.

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).