我了解HashMap如何工作的基础知识-hm. put（obj）根据obj.hashCode值找到正确的桶来放置对象。然后在该桶中，如果另一个对象.equals（obj）则替换它，如果没有将其添加到桶中。
但是我不清楚HashMap. put和HashMap.get是如何成为常数时间O（1）的。据我所知，桶的数量应该基于哈希码，所以将100个对象放入哈希码将（大致）创建100个桶（我知道哈希码中有时会发生冲突，所以它可能小于100，但不经常）。
因此，随着添加到hashmap中的对象数量的增加，桶的数量也在增加——由于碰撞很少，这是否意味着桶的数量几乎与添加的对象数量呈线性增长，在这种情况下，HashMap. put/HashMap.get将是O（n），因为它必须在找到正确的桶之前搜索每个桶。
我错过了什么？
这是我的两分钱，朋友。像思考数组一样思考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，单个看跌或获取的工作量仍然是相同的：y=x 2：我每次做看跌或获取时只需添加两个：这是恒定的工作。
你的困惑可能是你想一次放n个值。在这种情况下，每个算式仍然是常量c。但是c乘以n就是c*n=O（n）。所以n与算式本身无关，而是你一次做了n个算式。我希望这个解释有所帮助。
哈希表不需要搜索每个存储桶，就像你不需要搜索图书馆的每个书架一样，因为你可以在索引卡中查找它的位置，你不需要搜索索引中的每个卡片，因为它们是排序的…（不确定这是否有帮助，因为我不确定人们是否还去图书馆，或者他们是否还有索引卡）
可以这样想：当您调用get（key）时，计算键的hashcode，并由此在单个（一组）操作中指向数百个桶中的一个桶，即您不必搜索所有100个桶来到达正确的桶（在这种情况下，这将是一个线性操作）
