为什么要通过键 O (1)访问字典的元素，即使哈希函数可能不是 O (1) ？

O(1)并不意味着即时。O(1)表示常数 而不考虑数据的大小。散列函数需要一定的时间，但是这个时间并不随集合的大小而变化。

这意味着无论集合的大小如何，检索其任何成员所需的时间都几乎相同。

所以换句话说，有5个成员的 Dictionary 可能需要0.002 ms 才能访问其中的一个，而有25个成员的 Dictionary 也应该需要类似的东西。大 O 意味着算法复杂度超过集合大小，而不是实际执行的语句或函数

HashFunc本身就有很多幕后操作

确实如此。然而，这些操作的数量取决于 钥匙的大小，而不是键被插入的 哈希表的大小: 计算哈希函数的操作数量对于一个有一万个或一万个条目的表中的一个键是相同的。

这就是为什么散列函数的调用通常被认为是 O (1)。这对于固定大小的键(整数值和固定长度的字符串)非常适用。它还为可变大小的键提供了一个不错的近似值，具有实际的上限。

但是，通常情况下，哈希表的访问时间是 O (k) ，其中 k是哈希键大小的上限。

如果一个 dictionary/map 实现为 HashMap，那么它的 最佳情况复杂度为 O(1)，因为在最好的情况下，如果没有键冲突，那么它需要精确地计算用于检索的键元素的散列码。

如果您有大量的键冲突或者一个非常糟糕的散列函数，那么 散列表的 最坏情况下的运行时复杂度可能为 O(n)，因为在这种情况下，它降级为对包含数据的整个数组进行线性扫描。

此外，O(1)不意味着 马上，它意味着它有一个 不变量。因此，为 dictionary 选择正确的实现可能也取决于集合中元素的数量，因为如果只有几个条目，那么函数的常数开销会更高。

这就是为什么字典/地图在不同场景下的实现是不同的。对于 Java 有多种不同的实现，C + + 使用红/黑树等。您根据数据的数量和它们的最佳/平均/最差情况运行时效率来选择它们。

来自文件:

通过使用键检索值非常快，接近 O (1) ，因为 T: System。收款。通用的。Dictionary‘2类实现为哈希表。

所以它可以是 O (1) ，但可能更慢。 在这里你可以找到另一个关于哈希表性能的主题: 哈希表——为什么它比数组更快？

请参阅后 “ O (1)访问时间”是什么意思？

哈希函数中的操作数量是无关的，只要集合中的每个元素花费相同(常数)的时间。例如，访问2个元素集合中的一个元素需要.001 ms，但是访问2,000,000,000个元素集合中的一个元素也需要.001 ms。

理论上它仍然是 O (n) ，因为在最糟糕的情况下，所有数据最终可能具有相同的散列，并且被捆绑在一起，在这种情况下，您必须线性地遍历所有数据。

一旦考虑到越来越大的字典占用更多的内存，在缓存层次结构中向下延伸，最终导致磁盘上的交换空间变慢，就很难说它是真正的 O (1)。字典的性能会随着它的变大而变慢，这可能会增加 O (logN)时间复杂度。不相信我？用1100、1000、10000等字典元素，最多可以达到1000亿，测量实际查找一个元素需要多长时间。

但是，如果假设系统中的所有内存都是随机访问内存，并且可以在固定的时间内访问，那么可以声称字典为 O (1)。这种假设很常见，尽管对于任何具有磁盘交换空间的机器来说都不是真的，而且在任何情况下，考虑到 CPU 缓存的不同级别，这种假设还是很有争议的。

我们知道哈希函数需要 O (1)按键访问值... ... 所以这并不意味着它只需要1步就能得到值，它意味着常量时间“ t”，其中“ t”不依赖于数据结构的大小(例如:-python dict ())。