使用正则表达式查找哈希表/字典/地图

我试图弄清楚是否有一种合理有效的方法在字典中执行查找(或者哈希,或地图,或者你喜欢的语言所谓的任何语言),其中键是正则表达式,字符串是查找字符串的钥匙套.例如(在Python语法中):

>>> regex_dict = { re.compile(r'foo.') : 12, re.compile(r'^FileN.*$') : 35 }
>>> regex_dict['food']
12
>>> regex_dict['foot in my mouth']
12
>>> regex_dict['FileNotFoundException: file.x does not exist']
35

(显然上面的例子不能用Python编写,但这是我希望能够做的事情.)

我可以想到一种天真的方式来实现它,我在其中迭代字典中的所有键并尝试将传入的字符串与它们相匹配,但随后我丢失了哈希映射的O(1)查找时间,而是有O(n),其中n是我字典中的键数.这可能是一个大问题,因为我希望这个词典变得非常大,我需要一遍又一遍地搜索它(实际上我需要为我在文本文件中读取的每一行迭代它,并且文件大小可以达到几百兆字节).

有没有办法实现这一点,而不是诉诸O(n)效率？

或者,如果您知道在数据库中完成此类查找的方法,那也会很棒.

(任何编程语言都很好 - 我正在使用Python,但我对这里的数据结构和算法更感兴趣.)

有人指出不止一场比赛是可能的,这是绝对正确的.理想情况下,在这种情况下,我想返回一个包含所有匹配项的列表或元组.不过,我会为第一场比赛做好准备.

在这种情况下,我看不出O(1)是可能的; 不过,我会满足于低于O(n)的任何东西.此外,底层数据结构可以是任何东西,但我想要的基本行为是我上面写的:查找字符串,并返回与正则表达式键匹配的值.