Java HashMap 如何为 "get" 操作执行恒定时间查找 O(1)？
How is it possible for Java HashMap to perform constant time lookup O(1) for "get" operations?
我了解 HashMap 工作原理的基础知识 - hm.put(obj) 根据 obj.hashCode 值找到正确的存储桶来放置对象。然后在该桶中如果另一个对象 .equals(obj) 则替换它，如果不将其添加到桶中。
但我不清楚 HashMap.put 和 HashMap.get 如何成为常数时间 O(1)。据我了解，桶的数量应该基于哈希码，所以将 100 个对象放入哈希图中将（大致）创建 100 个桶（我知道哈希码有时会发生冲突，因此它可能小于 100 但不是经常）。
因此，随着添加到 hashmap 的对象数量的增加，桶的数量也会增加 - 由于碰撞很少见，这并不意味着桶的数量几乎与添加的对象数量呈线性增长，在这种情况下，HashMap.put/HashMap.get 将是 O(n)，因为它必须在找到正确的桶之前搜索每个桶。
我错过了什么？
哈希 table 不需要搜索每个桶，就像你不需要搜索图书馆的每个书架一样，因为你可以在 index cards 中查找它的位置，而且您不需要搜索索引中的每张卡片，因为它们已排序...（不确定这是否有帮助，因为我不确定人们是否仍然去图书馆或者他们是否仍然有索引卡片）
这样想：当您调用 get(key) 时，将计算密钥的哈希码，并由此指向数百个中的 one 个存储桶单个（一组）操作，即您不必搜索所有 100 个以到达正确的桶（在这种情况下，这将是一个线性操作）
这是我的两分钱，朋友。像看待数组一样看待 HashMap。其实就是一个数组。如果我给你索引 11，你不必遍历数组来找到索引 11 处的对象。你只需直接去那里。这就是 HashMap 的工作原理：诀窍是使索引与值相同——本质上。
这就是散列码的用武之地。让我们看一下您的散列函数是单位乘数（即 1）的简单情况。那么如果你有 0 到 99 的值，并且你想将它们存储在一个数组中，那么它们将分别存储在索引 0 到 99 中。所以 put 和 get 显然是 O(1)，因为在数组中获取和放置东西是 O(1)。现在让我们想象一个不那么简单的散列函数，比如 y = x+2。所以在这种情况下，值 0 到 99 将存储在索引 2 到 101 中。这里给定一个值，比如 11，您必须计算哈希值以找到它或放置它（哈希值是 11+2 =13）。好吧，哈希函数正在做一些工作来计算给定值的正确索引（在我们的例子中 y = x+2= 11+2=13）。但是这项工作的工作量与您拥有多少数据点无关。如果我需要 put 999 或 123，单个 put 或 get 的工作量仍然是相同的： y= x+2：我每次做 put 或 get 时只需要加两个：这是持续的工作。
您的困惑可能是您想一次放入 n 个值。那么在那种情况下，每个 put 仍然是常数 c。但是 c 乘以 n 是 c*n=O(n)。所以 n 与看跌期权本身无关，而是你同时进行 n 看跌期权。我希望这个解释能有所帮助。
我了解 HashMap 工作原理的基础知识 - hm.put(obj) 根据 obj.hashCode 值找到正确的存储桶来放置对象。然后在该桶中如果另一个对象 .equals(obj) 则替换它，如果不将其添加到桶中。
但我不清楚 HashMap.put 和 HashMap.get 如何成为常数时间 O(1)。据我了解，桶的数量应该基于哈希码，所以将 100 个对象放入哈希图中将（大致）创建 100 个桶（我知道哈希码有时会发生冲突，因此它可能小于 100 但不是经常）。
因此，随着添加到 hashmap 的对象数量的增加，桶的数量也会增加 - 由于碰撞很少见，这并不意味着桶的数量几乎与添加的对象数量呈线性增长，在这种情况下，HashMap.put/HashMap.get 将是 O(n)，因为它必须在找到正确的桶之前搜索每个桶。
我错过了什么？
哈希 table 不需要搜索每个桶，就像你不需要搜索图书馆的每个书架一样，因为你可以在 index cards 中查找它的位置，而且您不需要搜索索引中的每张卡片，因为它们已排序...（不确定这是否有帮助，因为我不确定人们是否仍然去图书馆或者他们是否仍然有索引卡片）
这样想：当您调用 get(key) 时，将计算密钥的哈希码，并由此指向数百个中的 one 个存储桶单个（一组）操作，即您不必搜索所有 100 个以到达正确的桶（在这种情况下，这将是一个线性操作）
这是我的两分钱，朋友。像看待数组一样看待 HashMap。其实就是一个数组。如果我给你索引 11，你不必遍历数组来找到索引 11 处的对象。你只需直接去那里。这就是 HashMap 的工作原理：诀窍是使索引与值相同——本质上。
这就是散列码的用武之地。让我们看一下您的散列函数是单位乘数（即 1）的简单情况。那么如果你有 0 到 99 的值，并且你想将它们存储在一个数组中，那么它们将分别存储在索引 0 到 99 中。所以 put 和 get 显然是 O(1)，因为在数组中获取和放置东西是 O(1)。现在让我们想象一个不那么简单的散列函数，比如 y = x+2。所以在这种情况下，值 0 到 99 将存储在索引 2 到 101 中。这里给定一个值，比如 11，您必须计算哈希值以找到它或放置它（哈希值是 11+2 =13）。好吧，哈希函数正在做一些工作来计算给定值的正确索引（在我们的例子中 y = x+2= 11+2=13）。但是这项工作的工作量与您拥有多少数据点无关。如果我需要 put 999 或 123，单个 put 或 get 的工作量仍然是相同的： y= x+2：我每次做 put 或 get 时只需要加两个：这是持续的工作。
您的困惑可能是您想一次放入 n 个值。那么在那种情况下，每个 put 仍然是常数 c。但是 c 乘以 n 是 c*n=O(n)。所以 n 与看跌期权本身无关，而是你同时进行 n 看跌期权。我希望这个解释能有所帮助。