为什么通过键 O(1) 访问字典的元素，即使哈希函数可能不是 O(1)？
Why is accessing an element of a dictionary by key O(1) even though the hash function may not be O(1)?
我知道如何通过密钥访问您的 collection。然而，哈希函数本身有很多幕后操作，不是吗？
假设你有一个非常高效的哈希函数，它仍然可能需要很多操作。
这可以解释一下吗？
O(1) 并不意味着即时。 O(1) 表示常数 ，不考虑数据的大小 。哈希函数需要一定的时间，但该时间量与集合的大小无关。
这意味着无论您的 collection 大小如何，检索其任何成员所花费的时间几乎相同。
所以换句话说，有 5 个成员的字典可以说访问其中一个成员需要大约 0.002 毫秒，而有 25 个成员的字典应该采取类似的东西。 Big O 意味着算法复杂度超过 collection 大小而不是实际执行的语句或函数
the HashFunc itself has a lot of operations behind the scenes
确实如此。但是，这些操作的数量取决于 key 的大小，而不取决于 hash table 的大小插入密钥：计算哈希函数的操作次数对于具有十个或一万个条目的 table 中的密钥是相同的。
这就是为什么哈希函数的调用通常被认为是 O(1)。这适用于固定大小的键（整数值和固定长度的字符串）。它还为具有实际上限的可变大小键提供了一个不错的近似值。
不过，一般来说，哈希 table 的访问时间是 O(k)，其中 k 是哈希键大小的上限。
如果 dictionary/map 实现为 HashMap，它的 最佳情况复杂度 为 O(1)，因为我最好用它如果没有键冲突，则需要准确计算用于检索的键元素的哈希码。
一个 hash-map 可能有一个 worst-case runtime complexity of O(n) if you have a lot of key冲突或非常糟糕的哈希函数，因为在这种情况下，它会退化为对保存数据的整个数组进行线性扫描。
此外，O(1)并不意味着立即，它意味着它有一个恒定的数量。因此，为字典选择正确的实现也可能取决于集合中元素的数量，因为如果只有几个条目，函数的恒定成本会非常高。
这就是为什么 dictionaryies/maps 针对不同的场景实施不同的原因。对于 Java 有多种不同的实现，C++ 使用 red/black-trees 等。您根据数据数量和它们的 best/average/worst-case 运行时效率来选择它们。
来自文档：
Retrieving a value by using its key is very fast, close to O(1), because the T:System.Collections.Generic.Dictionary`2 class is implemented as a hash table.
所以它可以是 O(1)，但可能更慢。
在这里您可以找到另一个关于哈希表性能的线程：Hash table - why is it faster than arrays?
请参阅post What does "O(1) access time" mean?
哈希函数中的操作次数无关紧要，只要它对集合中的每个元素花费相同（恒定）的时间即可。例如，访问包含 2 个元素的集合中的一个元素需要 0.001 毫秒，但访问包含 2,000,000,000 个元素的集合中的一个元素也需要 0.001 毫秒。虽然哈希函数可以包含数百个if语句和多次计算。
理论上它仍然是 O(n)，因为在最坏的情况下，您的所有数据最终可能具有相同的哈希值并捆绑在一起，在这种情况下您必须线性地遍历所有数据。
一旦您考虑到越来越大的词典占用更多内存这一事实，在缓存层次结构中进一步下降并最终导致磁盘上的交换速度变慢 space，很难说它是真正的 O (1).字典的性能会随着它变大而变慢，可能会给出 O(log N) 时间复杂度。不相信我？自己尝试一下 1、100、1000、10000 等等字典元素，最多说 1000 亿，并测量实际查找一个元素需要多长时间。
但是，如果您简化假设系统中的所有内存都是随机存取内存，并且可以在恒定时间内访问，那么您可以声称字典是 O(1)。这种假设很常见，尽管对于任何具有磁盘交换 space 的机器来说都不是真的，并且在任何情况下考虑到不同级别的 CPU 缓存仍然非常值得商榷。
我们知道哈希函数需要 O(1) 来通过键访问值...所以这并不意味着它只需要 1 步就可以得到值，它意味着常数时间“t”，其中“t”不依赖于数据结构的大小（例如：-python dict()).
我知道如何通过密钥访问您的 collection。然而，哈希函数本身有很多幕后操作，不是吗？
假设你有一个非常高效的哈希函数，它仍然可能需要很多操作。
这可以解释一下吗？
O(1) 并不意味着即时。 O(1) 表示常数 ，不考虑数据的大小 。哈希函数需要一定的时间，但该时间量与集合的大小无关。
这意味着无论您的 collection 大小如何，检索其任何成员所花费的时间几乎相同。
所以换句话说，有 5 个成员的字典可以说访问其中一个成员需要大约 0.002 毫秒，而有 25 个成员的字典应该采取类似的东西。 Big O 意味着算法复杂度超过 collection 大小而不是实际执行的语句或函数
the
HashFuncitself has a lot of operations behind the scenes
确实如此。但是，这些操作的数量取决于 key 的大小，而不取决于 hash table 的大小插入密钥：计算哈希函数的操作次数对于具有十个或一万个条目的 table 中的密钥是相同的。
这就是为什么哈希函数的调用通常被认为是 O(1)。这适用于固定大小的键（整数值和固定长度的字符串）。它还为具有实际上限的可变大小键提供了一个不错的近似值。
不过，一般来说，哈希 table 的访问时间是 O(k)，其中 k 是哈希键大小的上限。
如果 dictionary/map 实现为 HashMap，它的 最佳情况复杂度 为 O(1)，因为我最好用它如果没有键冲突，则需要准确计算用于检索的键元素的哈希码。
一个 hash-map 可能有一个 worst-case runtime complexity of O(n) if you have a lot of key冲突或非常糟糕的哈希函数，因为在这种情况下，它会退化为对保存数据的整个数组进行线性扫描。
此外，O(1)并不意味着立即，它意味着它有一个恒定的数量。因此，为字典选择正确的实现也可能取决于集合中元素的数量，因为如果只有几个条目，函数的恒定成本会非常高。
这就是为什么 dictionaryies/maps 针对不同的场景实施不同的原因。对于 Java 有多种不同的实现，C++ 使用 red/black-trees 等。您根据数据数量和它们的 best/average/worst-case 运行时效率来选择它们。
来自文档：
Retrieving a value by using its key is very fast, close to O(1), because the T:System.Collections.Generic.Dictionary`2 class is implemented as a hash table.
所以它可以是 O(1)，但可能更慢。 在这里您可以找到另一个关于哈希表性能的线程：Hash table - why is it faster than arrays?
请参阅post What does "O(1) access time" mean?
哈希函数中的操作次数无关紧要，只要它对集合中的每个元素花费相同（恒定）的时间即可。例如，访问包含 2 个元素的集合中的一个元素需要 0.001 毫秒，但访问包含 2,000,000,000 个元素的集合中的一个元素也需要 0.001 毫秒。虽然哈希函数可以包含数百个if语句和多次计算。
理论上它仍然是 O(n)，因为在最坏的情况下，您的所有数据最终可能具有相同的哈希值并捆绑在一起，在这种情况下您必须线性地遍历所有数据。
一旦您考虑到越来越大的词典占用更多内存这一事实，在缓存层次结构中进一步下降并最终导致磁盘上的交换速度变慢 space，很难说它是真正的 O (1).字典的性能会随着它变大而变慢，可能会给出 O(log N) 时间复杂度。不相信我？自己尝试一下 1、100、1000、10000 等等字典元素，最多说 1000 亿，并测量实际查找一个元素需要多长时间。
但是，如果您简化假设系统中的所有内存都是随机存取内存，并且可以在恒定时间内访问，那么您可以声称字典是 O(1)。这种假设很常见，尽管对于任何具有磁盘交换 space 的机器来说都不是真的，并且在任何情况下考虑到不同级别的 CPU 缓存仍然非常值得商榷。
我们知道哈希函数需要 O(1) 来通过键访问值...所以这并不意味着它只需要 1 步就可以得到值，它意味着常数时间“t”，其中“t”不依赖于数据结构的大小（例如：-python dict()).