Python 的 dict 不会随着 key 的增加而变慢吗？ 第1页

其实也没有那么的不合常理，毕竟前边加了一个限定条件「和list比较」。

所谓不会随着key的增加而变慢，是指相对list而言。实际上还是会变慢的，因为key增加之后，碰撞几率就会增加，有碰撞之后就不是O（1）复杂度。——在最糟糕的情况下，所有的key全都发生碰撞，这个hash表就退化成一个list。

换句话说，在最理想情况下，dict的key不发生任何碰撞，查找时间不受影响是O（1），在最坏情况下，dict的key永远发生碰撞，查找时间算法复杂度与list等同。

至于「需要占用大量内存」就更合乎常理了吧？毕竟提升时间效率往往就需要牺牲空间效率。这很合理不是么。

你问的问题其实很有价值。这是很多初学数据结构的人的困扰，因为它没逻辑。凭什么我多大的数据量，访问速度都是一样的？这根本不符合常理。

很多人会告诉你，这是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的增加而减慢的。

这里有两个层面的考虑，第一个是从算法理论上，第二个是从系统实现上。

算法理论研究的其实是在计算性框架下的一些独特的概念，算法时间复杂度并不等价于一个算法要用多长时间，空间复杂度也并不等价于要用多少储存空间。它是以一套独特的方式去在更抽象更general更理想的层面去单纯的评估算法本身而已。所以对于hashmap来说，算法复杂度确实是O(1)，这是计算理论里给出的衡量。

而算法复杂度的估量在实际实现上的时间消耗是相对匹配的，因为算法复杂度并不受硬件速度的影响，它用单次运行的概念去抽象出了硬件性能。然而，这种抽象是无法剔除计算机架构带来的影响的，最主要的是缓存模式的影响。因为在计算理论里的计算机都是理想的，储存是无限的，所以不需要缓存这种东西。现实中为了成本和性能的平衡考虑，有缓存和虚拟内存等机制来分配使用不同性能级别的资源。这就会造成算法在实际系统上的表现不一定会按照算法复杂度完全匹配。比较典型的例子是排序中归并排序的算法复杂度比快速排序要低，但是实际的表现是不一定这样的，这还要考虑到缓存利用率。

那么回到这个问题上，一，对算法的衡量来说，hashmap这种东西的查找算法复杂度确实是O(1)。二，O(1)并不等于实际的运行时间。三，算法会受实际的系统架构的影响导致不同的速度。四，哈希的方式会影响到实际碰撞的可能，每次碰撞都相当于脱离了hashmap的理想情况。五，所以实际上dict的增长肯定会影响到速度。六，但是比较起n的增长来，这个速度的影响可以近似看作不受影响。