prefixes = SubstringDict()
for key, value in list(d.items()):
    prefixes[a + key] = value
for query in ['key1', 'key2']:
    pass
Более эффективный способ поиска значений словаря, ключи которых начинаются с одного и того же префикса.