0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I’m voting to close this question because this has nothing to do with Cryptogrpahy.SE. It talk about complexity of of hash tables where a hash function is used. Better to be asked at CS. Update: This is what you are looking for! How are hash tables O(1) taking into account hashing speed? $\endgroup$
    – kelalaka
    Mar 23, 2021 at 10:27

1 Answer 1

Reset to default
5
$\begingroup$

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 "hashing takes time $O(1)$" is true for fixed/bounded length inputs, but as you say this is misleading.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Addition: $\mathcal O(n)$ time is when $n$ is the length of the input, and the hash fixed and sequential. That's also the cost. With a hash tree, we can get the time, but not the cost, down to $\mathcal O(\log n)$. When $n$ is the security parameter (typically the hash output width), the best (secure) constructions I know have cost $\mathcal O(n\log n)$. $\endgroup$
    – fgrieu ♦
    Mar 23, 2021 at 14:43
  • $\begingroup$ And CS is bit different approaches for those: cs.cornell.edu/courses/cs3110/2014fa/lectures/13/lec13.html $\endgroup$
    – kelalaka
    Mar 23, 2021 at 18:03
  • $\begingroup$ The misleading thing is more a property of Big-O notation in general. Since cryptographic hashes have a maximum secure input length (based on the birthday bound on their internal state size) and Big-O only measures asymptotic behavior as the input length goes to infinity, all fixed or bounded-length input functions are $O(1)$. The low-order terms vary, but Big-O discards those. There are a number of such instances where it's inappropriate for cryptographic algorithms or usages. $\endgroup$
    – SAI Peregrinus
    Mar 23, 2021 at 22:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.