java - Java HashMap 怎么可能对 "get"操作执行恒定时间查找 O(1)？

Question

我了解 HashMap 工作原理的基础知识 - hm.put(obj) 根据 obj.hashCode 值找到将对象放入的正确存储桶。然后在该桶中，如果另一个对象 .equals(obj) 则替换它，如果没有将其添加到桶中。

但我不清楚 HashMap.put 和 HashMap.get 是如何成为常数时间 O(1) 的。据我了解，桶的数量应该基于哈希码，所以将 100 个对象放入 HashMap 中将(大致)创建 100 个桶(我知道哈希码有时会发生冲突，因此它可能小于 100 但不是经常)。

因此，随着添加到 hashmap 中的对象数量的增加，桶的数量也会增加——并且由于碰撞很少见，这并不意味着桶的数量几乎与添加的对象数量呈线性增长，其中案例 HashMap.put/HashMap.get 将是 O(n)，因为它必须在找到正确的桶之前搜索每个桶。

我错过了什么？

Answer 1

这是我的两分钱， friend 。像看待数组一样看待 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 看跌期权。我希望这个解释能有所帮助。