python 的 dict 会随着key的增加而变慢吗

偏执的太偏执、 2022-04-06 19:22 185阅读 0赞

很多人会告诉你，这是Hash Table，而Hash Table的访问速度是O(1)的，而对于你来说，这就和没说一样。这个答案既不算精确，也没能回答你的问题。

首先如果你真的想搞清楚这个问题的来龙去脉，你需要搞懂Hash Table到底是什么东西。Hash Table首先默认了一件事情，在电脑中，读取或者写入一个已知地址的内存需要的最大时间是固定的，和有可能写入内存的长度无关的。

举个例子，你在家有一个柜子，柜子上有一堆抽屉，你把这些抽屉分别编号为1-10。这时候我和你说，找10号抽屉，你可以立刻找到10号。我说找6号，你可以立刻找到6号。现在你的柜子扩大了，抽屉有100个，我说找56号，你还是可以立刻找到56号。你柜子又大了，变成了1000个抽屉，我说找729号，你依然可以立刻找到729号。

对于人类来说，这是不可能的。随着抽屉数量的增加，我们找对应抽屉的速度会下降。但是对于现在的计算机来说，这个假设是成立的。这是你要理解的第一点计算机和人类的不同。无论有多少抽屉，只要你说找这个号码的抽屉，不管是第一个，最后一个，还是中间任何抽屉，计算机的反应速度都一样。

好，现在假设我们有1000个抽屉，我们有4份文件。每一份文件有一个唯一且不重复的文件编码，这个编码是8位码，比如01303457。我们需要把这四份文件保存到抽屉里，并且希望下次有人来要这些文件的时候，我们可以立刻找到。

我们可以把这四份文件都放到第一个抽屉，然后人来的时候把四个文件找出来，逐一对比文件编码。这是一种线性数据结构，他的搜索速度和文件的数量是线性关系。我们有100份文件，速度大概是10份的10倍。我们管他叫O(N)。我们可以按照文件编码先把文件排序，然后都放第一个抽屉里。这样搜的时候，我们可以利用二分法来找文件。这时候我们的速度提高到了log(N)。随着文件的增加，我们的搜索时间还是在增加，但是增加的缓慢了。

然而还有一个方法。我们可以看文件的尾号，把他们放进和尾号对应的抽屉里。比如01303457号文件，我们就给他放到457号抽屉。我们可以想象，在文件比较少的时候，我们的每个抽屉很可能只有一份文件。这时候有个人来说我要01303457号文件，我们就可以直接去457号抽屉给她拿。由于我们找一个抽屉的速度时固定的，所以随着文件的增加，我们搜索文件的时间是没有增加的。

下面才是重点，也是两种逻辑产生冲突的地方。如果文件多了，肯定会有抽屉不止两个文件。最理想的情况下，在有1001份文件的时候，也会有一个抽屉有两份文件。而最差的情况，所有的文件尾号都一样，那我们不是回到了第一种方法么？

没错！你想的是完全正确的。相信自己的判断。

很多课在入门数据结构的时候会尽量回避这个地方，或者一笔带过，留下莫名其妙的学生们，背下来Hash Table的access是O(1)。而事实上这里的O(1)是有很多先决条件的。

第一，这是一个平均值，不是最差值。在Worst case下，Hash Table的access时间并非O(1)，是会随着数据的增长而增长的。也就是说，我们常理上看，虽然有着每一份来的文件编号尾号都一样的可能性，但是平均上说，他们应该是分的比较开的。而如何把文件尽量分散地对应到相应的抽屉，也是一个学问，这里不赘言（思考一下如果按照常规的文件编号方法，顺序编号，用尾数和用开头的三位会有什么不同？）。

第二，你抽屉的数量要远大于文件的数量。如果你只有10个抽屉，有100份文件，那当然会随着文件数量的增加，找文件的速度变慢。对于Hash Table也是一个道理，你准备好的内存需要远大于实际使用的内存。如果你准备迎接100个数据，你可能就要准备400个以上的空位。随着数据量的增加，为了保证你的读写速度还在O(1)，你的内存开销也会变大。换言之，一个理想Hash Table的读写速度确实是O(1)，但是占用内存是无限大（因此理想Hash Table不存在）。

回到你的问题，在我们正常写程序的时候，所用到的数据量都不算太大（相对于可支配内存），所以我们可以把dict看作一个理想Hash Table。这时候随着key的增加，它确实不会变慢（占用内存变多）。但是到了极端情况，当你的key非常非常非常多的时候（这时候要看他Hash Table的具体实现），他的速度是有可能随着key的增加而减慢的。