# Time complexity of checking whether a string exists in a HashSet

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.

• You always have to read the string, yes, at least once May 8 at 14:33
• So the complexity is technically O(m), right? May 8 at 14:34
• 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. May 16 at 15:10

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