I understand the linear solution to this problem. However, the hash table find() method time complexity would be O(n) in the worst case. Thus, how would you guarantee that it's still O(n) for this problem? I know that there is rare cases the find() method would reach O(n), but it happens.

Am I missing something here please?