W hashsecie nie da się inaczej niż O(n). Musisz przeiterować po wszystkich elementach.
Natomiast są struktury dedykowane do takiego szybkiego szukania, np. drzewo trie (prefiksowe) https://pypi.python.org/pypi/marisa-trie
from marisa_trie import Trie
trie = Trie(['abc', 'cbd', 'abba'])
trie.has_keys_with_prefix('ab') # True
trie.has_keys_with_prefix('cd') # False
Ze złożonością O(1) na wielkość kontenera.
BTW na przyszłość:
s = set(['abc','cbd', 'abba'])
s = {'abc','cbd', 'abba'} # ladniejsze