Yes, if you assume that your keys are going to be arbitrarily long inputs. I think it's typical that in the analysis of algorithms we often make simplifying as

Yes, if you assume that your keys are going to be arbitrarily long inputs. I think it's typical that in the analysis of algorithms we often make simplifying assumptions that we don't always spell out explicitly (and probably we should). The assumption here (which IMHO is often practically sensible) was that there is a certain fixed set of all possible keys, e.g. from a bounded set of integers. In that case, hash tables indeed have constant-time operations no matter how many elements you have. I think it's a bit similar to saying that e.g. Gauss elimination is O(n^3). This is only true for fixed-size numbers, e.g. floats or bounded integer types, not for arbitrary integers - in fact, the Gauss algorithm is incredibly bad for true, arbitrary-precision arithmetic. Nevertheless, the algorithm is incredibly useful, because the fixed-size assumption is often warranted - the most notable exceptions are probably from the realm of cryptography.