How fast is hashing and is it always regarded as an O(1) operation? I've wondered how hashing can be such a fast operation. It's so fast that nobody talks about it in terms of performance and complexity.
I know that in terms of big O notation, you can drop all the constants and just speak in terms of the variables. I know that in hash lookup, if you know the key, it is O(1). This makes sense to me. What didn't make sense was to get the message digest, you have to actually run the hash function, and nobody talks about this. What if the file or document is super large, the complete works of William Shakespeare. Does that take 1000x as long to hash as a one page document? I assume the hash functions have to run through every single bit of the data one by one, so doesn't that factor into time complexity? Maybe it doesn't have to run through every bit. Maybe it runs through every 8 bits or 32 bits or whatever a word size is in a system. I know bitwise operations are significantly faster and I know the SHA algorithms make use of them, but still, when people say hashtable lookup is O(1), I'm amazed at how the hashing itself can always be considered as nothing, regardless of file size, as it seems that the entire data would have to be traversed through.
You are right. A hash function applied to $n$ bits of input will typically take $O(n)$ work to evaluate. It is important for a hash function to use every single bit of input as part of the calculation or collisions become very, very easy.
The &quot;hashing takes time $O(1)$&quot; is true for fixed/bounded length inputs, but as you say this is misleading.