Isn't it too implementation specific to simply claim worst-case as O(1) or O(n)? Depending on how much memory is acceptable to waste and how fast insertions should be worst-case could range from O(1) to O(n).
I would not consider a table where the data size of the hashed keys equals the data size of the unhashed keys a hash map. If you got, say, a u8 as a key, and your lookup table uses u8s for keys internally, that's not what most people would refer to as a hash table. It's simply a lookup array.
In all the usual cases, the hashed key size is way less than the unhashed key size, and you need to pay the price for collisions somewhere.
No, if you rebuild on collision you waste just a bit more memory, but get O(1) worst case look-ups. It's still a hash table and not a table that maps an entire key space. See how dynamic perfect hashing works.
There are various trade-offs, as I said, but getting O(1) worst-case look-ups is not hard. Only naive implementations could corner you into O(n) worst-case.
I'm sorry, but you don't really understand hash tables.
Read things more carefully before rushing to judgement. I'm not talking about a lookups-only scenario. Of course you can make anything O(1) as long as you arbitrarily define all the parts that aren't as external to the solution, but you're just kidding yourself in the end.
> I'm sorry, but you don't really understand hash tables.
I'm not the one who made this personal, but I'll match that allegation back to you, and I raise you one "you don't really know how to interpret what people say".
Honestly, I think implying that rebuilding the hash table is an O(1) operation is worse. :P But judging by the downvotes I'm getting on that particular comment, it seems that most people agree with you that rebuilding is indeed free. So it seems you won this argument on several fronts ;)
