You should not be using n for the number of bits and n for the size of the input.
It may take longer to multiply 128 bit data structures than 64 bit data structures, but it is constant with respect to the size of the hash table.
It may take longer to multiply 128 bit data structures than 64 bit data structures, but it is constant with respect to the size of the hash table.
That's all somewhat theoretical sure, but the point is to challenge your assumptions. (People do use vectorization, right now.)
You're assuming that people are not aware that multiplication is not always a constant-time operation. That assumption generally doesn't hold among people with any sort of academic CS background. Multiplication algorithms - and the fact that they were typically O(N) in number of bits - were covered in my intro machine architectures course.
In practice, there are many, many other things that can negatively impact hash table performance in a much bigger way. Like cache misses - one cache miss costs far more than an integer multiplication. Or interpreter overhead from using, say, Ruby instead of C (bad example, since Ruby's hashtables are implemented in C, but the general point holds). Or the difference between -O0 and -O3. Or how early versions of Java Hashtables would often devolve into linked lists because the hash function only looked at the first 8 characters of a string.
"You're assuming that people are not aware that multiplication is not always a constant-time operation."
I made no such assumption. But I suggest people consider the case of vectorization where, all of a sudden, it may matter quite a bit.
Exactly. That is the whole key to complexity analysis.
Otherwise you end up drowning in details without getting more meaningful answers.
You're analyzing the hash table algorithm, not the hashing algorithm used to produce the keys.
I don't see that I ever did use it for a number of bits. I said, to have n numbers with distinct values, you need O(log n) bits in each number. n is not a number of bits.