Right, O(n). O(1), hah, I wish! Yes, there is the caveat of constant k, but in practice this is usually implied for integer keys e.g., the int32 integers used

Right, O(n). O(1), hah, I wish! Yes, there is the caveat of constant k, but in practice this is usually implied for integer keys e.g., the int32 integers used in the OP. If the keys become arbitrarily long, hash tables also become O(n log k) since you have to hash and compare log k bits of key state.