python - Python 快速包含方法

Question

如果我在 Python 中有一个字典，那么搜索一个不存在的键的时间复杂度是多少？

d = {}
if key not in d:
   print "Key not found!"

是否in对键数组进行线性搜索？

是否有为特定字符串搜索数据结构的 O(1) 实现？有效地为一种contains()方法。

Answer 1

它必须O(1)为字典摊销，因为最终in操作员只是执行成员资格查找，not并没有额外的开销。在字典的情况下，请查看此答案以获取有关运算符时间复杂度的更多详细信息。in

Answer 2

它的 O(1) 字典被实现为哈希表，并且在哈希表查找中

Answer 3

字典通常是O(1) 的查找。

拥有一个为其哈希返回常量的类是完全可以接受的，但这会使字典查找降级为线性。

例如。

class dumbint(int):
    def __hash__(self):
        return 0

$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(100)}' 'dumbint(-1) in d'
100000 loops, best of 3: 3.64 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(1000)}' 'dumbint(-1) in d'
10000 loops, best of 3: 31.7 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(10000)}' 'dumbint(-1) in d'
1000 loops, best of 3: 803 usec per loop

字符串具有良好的散列函数，因此您将获得 O(1) 查找精确匹配。在键中搜索子字符串是一个困难得多的问题。