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 &quot;a&quot;, &quot;bc&quot;, &quot;cd&quot;, &quot;acd&quot;, &quot;abcd&quot;, only &quot;acd&quot; can be formed using other words, though I don't think the specific problems matters much.
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)$.