Java HashMap如何为“get”操作执行常量时间查找O（1）？
我理解HashMap如何工作的基础知识 – hm.put（obj）根据obj.hashCode值找到放置对象的正确存储桶。 然后在该桶内如果另一个对象.equals（obj）然后替换它，如果没有将它添加到桶中。
但我不清楚HashMap.put和HashMap.get如何可以是常数时间O（1）。 根据我的理解，桶的数量应该基于哈希码，因此将100个对象放入哈希映射将（大致）创建100个桶（我知道有时会在哈希码中发生冲突，所以它可能少于100但不是经常）。
因此，随着添加到散列映射的对象数量的增加，桶的数量也增加 – 并且因为冲突很少，所以这并不意味着桶的数量几乎与添加的对象数量线性增长，在这种情况下是HashMap。 put / HashMap.get将是O（n），因为它必须在找到正确的桶之前搜索每个桶。
我错过了什么？
这是我的两分钱，朋友。 以您对arrays的看法来考虑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）。 但是，这项工作的努力程度与您拥有的数据点数无关。 如果我需要输入999或123，单个put或get的工作量仍然相同：y = x + 2：我每次执行put或get时只需要添加两个：这是常量工作。
您的困惑可能是您希望一次输入n个值。 那么在这种情况下每次放置仍然是恒定的c 。 但是c乘以n是c*n = O（n）。 所以n与put本身无关，而是你将n全部放在一起。 我希望这个解释有所帮助。
哈希表不需要搜索每个桶，就像你不需要搜索库中的每个架子一样，因为你可以在索引卡中查找它的位置，而你不需要搜索每个卡中的每个卡。索引，因为它们已排序…（不确定是否有帮助，因为我不确定人们是否仍然去图书馆或他们是否还有索引卡）
可以这样想：当你调用get(key) ，会计算密钥的哈希码，从中可以在一个（一组）操作中指向数百个中的一个桶，即你没有搜索所有100来到达正确的桶（在这种情况下，这将是一个线性操作）