Python字典键。“复杂”的
快速提问主要满足我对这个话题的好奇心。
我正在编写一些带有SQlite数据库后端的大型python程序，并且将来会处理大量记录，因此，我需要尽可能地优化。
对于一些功能，我正在字典中搜索关键字。我一直在使用“ in”关键字进行原型设计，并计划稍后返回并优化这些搜索，因为我知道“
in”关键字通常为O（n）（因为这仅表示python遍历整个列表并进行比较每个元素）。但是，由于python
dict基本上只是一个哈希映射，因此python解释器足够聪明来解释：
if(key in dict.keys()):
...code...
至：
if(dict[key] != None):
...code...
它基本上是相同的操作，但顶部为O（n），底部为O（1）。
对我来说，在代码中使用底部版本很容易，但是后来我很好奇并以为我会问。
-
首先，
key in d.keys()保证为您提供与key in ddict相同的值d。而且，
in对dict或操作（从3.x中dict_keys调用）返回的对象的操作 不是 O（N），而是O（1）。keys()__没有真正的“优化”。只是使用哈希是在
__contains__哈希表上实现的明显方法，就像它是实现的明显方法一样__getitem__。
您可能会问这在哪里得到保证。
好吧，不是。映射类型将
dict基本上定义为的哈希表实现collections.abc.Mapping。没有什么可以阻止某人创建Mapping的哈希表实现的，但是仍然可以提供O（N）搜索。但是，要实现如此糟糕的实现将是额外的工作，那么为什么要这么做呢？如果您确实需要自己证明它，则可以测试您关心的每个实现（使用探查器，或者通过将某种类型与自定义一起使用，
__hash__并__eq__记录调用，或者…），或者阅读源代码。
在2.x中，您不想调用
keys，因为它会生成一个list密钥，而不是一个KeysView。您可以使用iterkeys，但可能会生成迭代器或其他不是O（1）的东西。因此，只需将dict本身用作序列即可。即使在3.x中，也不需要调用
keys，因为没有必要。迭代adict，检查其__contains__，并且通常将其视为序列 总是
等同于对其键执行相同的操作，那么为什么要打扰呢？（当然，构建琐碎的宏KeyView并进行访问将使您的运行时间增加几纳秒，并为程序增加一些击键。）（尚不清楚
d.keys()/d.iterkeys()和d2.x中使用序列运算是否等效。除了性能问题外，它们在每个CPython，Jython，IronPython和PyPy实现中
均 等效，但是似乎在任何地方都没有说明。 3.x中的方式。这并不重要；只需使用key in d。）
在进行此操作时，请注意以下几点：
if(dict[key] != None):……将无法正常工作。如果
key不在中dict，则将引发KeyError而不返回None。另外，您永远不要
None使用==或进行检查!=。经常使用is。您可以使用
try-或更简单地说，执行doif dict.get(key, None) is not None。但是同样，没有理由这样做。此外，这将无法处理None完全有效的物品。在这种情况下，您需要执行sentinel = object(); if dict.get(key, sentinel) is not sentinel:。
因此，正确的写法是：
if key in d:
更普遍地说，这是不正确的：
我知道关键字“ in”通常为O（n）（因为这仅表示python遍历整个列表并比较每个元素
in与大多数其他运算符一样，该运算符仅是对__contains__方法的调用（或等效于内置的C / Java / .NET /
RPython）。list通过迭代列表并比较每个元素来实现它；dict通过散列值并查找散列来实现它；blist.blist通过走B +
Tree来实现它；因此，它可以是O（n），O（1），O（log n）或完全不同的东西。
