为什么即使散列函数不是O（1），也可以通过键O（1）访问字典的元素？
我看你如何通过密钥访问你的collections。 但是，哈希函数本身在幕后有很多操作，不是吗？
假设你有一个非常有效的散列函数，它仍然可能需要很多操作。
这可以解释吗？
HashFunc本身在后台有很多操作
这当然是真的。 但是，这些操作的数量取决于密钥的大小，而不取决于密钥所插入的哈希表的大小：计算哈希函数的操作的数量对于具有十个有一万个条目。
这就是为什么哈希函数的调用通常被认为是O（1）。 这适用于固定大小的键（整数值和固定长度的string）。 它也提供了一个实际的上限可变大小的键的像样的近似值。
一般来说，散列表的访问时间是O（k），其中k是散列键大小的上限。
O(1)并不意味着即时。 O(1)表示常量， 不考虑数据的大小 。 哈希函数需要一定的时间，但是这个时间量不会随着集合的大小而扩展。
这意味着无论你的collections量多大，收取任何会员的时间仍然几乎相同。
换句话说，有5个成员的字典会让我们说要花费大约0.002毫秒来访问其中的一个，以及25个成员的字典应该采取类似的东西。 大O意味着algorithm复杂度超过集合大小，而不是实际的语句或执行的函数
如果一个字典/映射被实现为一个HashMap ，它的复杂度最好是O(1) ，因为我最好的情况是它需要精确地计算检索的关键元素的散列码，如果没有关键的冲突。
如果你有很多关键冲突或一个非常糟糕的散列函数， 散列映射的 运行时复杂度可能是O(n)的最坏情况 ，因为在这种情况下，散列映射会降低到保存数据的整个arrays的线性扫描。
另外， O(1)并不意味着立即 ，这意味着它有一个恒定的数额。 因此，为字典select正确的实现可能取决于集合中元素的数量，因为如果只有less量条目，那么对于函数来说具有非常高的恒定成本将会更糟糕。
这就是字典/地图针对不同场景实施不同的原因。 对于Java，有多种不同的实现，C ++使用红色/黑色树等。您根据数据的数量并根据最佳/平均/最差情况下的运行效率select它们。
从理论上讲，它仍然是O（n），因为在最糟糕的情况下，你的所有数据可能都会有相同的哈希值并被捆绑在一起，在这种情况下，你必须线性地通过所有的数据。
请看post“O（1）访问时间”是什么意思？
只要对集合中的每个元素使用相同（恒定）的时间量，散列函数中的操作数就是不相关的。 例如，访问2个元素集合中的一个元素需要0.001毫秒，而访问20亿个元素集合中的一个元素需要0.001毫秒。 尽pipe散列函数可以包含数百个if语句和多个计算。
从文档：
使用其键值检索值非常快，接近于O（1），因为T：System.Collections.Generic.Dictionary类实现为散列表。
所以它可以是O（1），但可能会更慢。 在这里你可以find另一个有关hashtable性能的线程： 哈希表 – 为什么它比数组更快？
一旦你允许越来越大的字典占用更多的内存，进一步降低caching层次并最终导致磁盘交换空间变慢，很难说它是真正的O（1）。 字典的性能会变得越来越慢，可能会导致O（log N）的时间复杂度。 不要相信我？ 用1，100，1000，10000等字典元素自己试试，达到1000亿，并测量在实践中查找元素需要多长时间。
但是，如果您简化了系统中所有内存都是随机存取内存的假设，并且可以在一段时间内访问，则可以声明该字典是O（1）。 这种假设是常见的，即使对于任何具有磁盘交换空间的机器来说都不是这样，并且在任何情况下，在CPU高速caching不同的情况下，这个假设仍然是非常有争议的。
