2
$\begingroup$

From what I know hash sets generally have complexity of $O(1)$ (unless the hash function is bad, but let's just ignore that for this question). However, sets need to either read the full data so as to make a hash function that's guaranteed to return a unique result for every input or they need to make a comparison to make sure the data is the same otherwise. Doesn't that mean that the complexity for strings should be $O(m)$, where $m$ is the length of the string, at least if we accept that these strings can get arbitrarily large? Is there something I do not understand?

The reason I'm asking is because I solved a problem with a trie and the provided solution was solved with a set (that was the only difference), but it assumed that arbitrarily large strings can be found to exist or to not exist in a set in $O(1)$ time. The problem is to find which words in a set of words can be formed using other words in the set (words can be used multiple times) — for example in "a", "bc", "cd", "acd", "abcd", only "acd" can be formed using other words, though I don't think the specific problems matters much.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You always have to read the string, yes, at least once $\endgroup$
    – John Kemeny
    Commented May 8, 2021 at 14:33
  • $\begingroup$ So the complexity is technically O(m), right? $\endgroup$
    – asharpharp
    Commented May 8, 2021 at 14:34
  • $\begingroup$ GD: Not to get a hash code, you can easily extract say 100 characters out of a million for hashing. But if the hash code is in the table, and the strings have same length, you need to compare until you find a difference, and if the string is in the table, you’ll have to read all characters. $\endgroup$
    – gnasher729
    Commented May 16, 2021 at 15:10

1 Answer 1

Reset to default
3
$\begingroup$

You are right in that to check membership (or to retrieve) using a hash function, you also need to check that the retrieved element is equal to the element in question. For a string, you should assume that this takes time linear in the length.

Hence checking membership in a hash set is indeed expected $O(m)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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