Search of Dictionary Keys python

Question

I want to know how I could perform some kind of index on keys from a python dictionary. The dictionary holds approx. 400,000 items, so I am trying to avoid a linear search.

Basically, I am trying to find if the userinput is inside any of the dict keys.

for keys in dict:
    if userinput in keys:
        DoSomething()
        break

That would be an example of what I am trying to do. Is there a way to search in a more direct way, without a loop ? or what would be a more efficient way.

Clarification: The userinput is not exactly what the key will be, eg userinput could be log, whereas the key is logfile

Edit: any list/cache creation, pre-processing or organisation that can be done prior to searching is acceptable. The only thing that needs to be quick is the search for the key.

Answer 1

If you only need to find keys that start with a prefix then you can use a trie. More complex data structures exist for finding keys that contain a substring anywhere within them, but they take up a lot more space to store so it's a space-time trade-off.