我在概念上难以理解插入和获取操作在 Java 的 Hashmap（简化为哈希表）中的分摊运行时间为 O(1) 的事实。请注意，在我的示例中，表是在最大容量下创建的，这意味着它只需要扩展一次，当满足 75% 的负载因子时。也永远不会在无效目标上调用 Get。
摊销运行时间通过 O（总成本）/操作计数计算。
对于插入，将一个元素添加到对应于哈希表中特定槽的桶中。由于总是将最新值添加到存储桶的末尾，因此该值是：
- 总成本 = 找到存储桶 + 存储桶末尾的位置，所有 O(1) 时间
- 操作数 = 找到桶 + 放在桶尾
- 因此，Amortized Running Time = (find bucket + place at bucket end)/(find bucket + place at the end), 或者 O(1)
唯一让我感到困惑的方面是添加的元素是否将表格置于其负载因子之上，并调整其大小。Java 将在这里执行哪些步骤，为什么它仍然是 O(1) 摊销运行时间？
对于 get，查找存储桶的时间是恒定的，查找匹配可能需要 1 次操作（目标是存储桶中的第一个值）到 n 次操作（所有条目都在同一个存储桶中，目标位于底部） ）。在这种情况下：
- 总成本 = 找到桶 + 在桶中找到目标的步数，都是 1 个时间单位
- 操作数 = 找到桶 + 在桶中找到目标的步骤数
- 因此，摊销运行时间=（找到桶+在桶中找到目标的步数）/（找到桶+在桶中找到目标的步数），或O（1）
这是我将摊销思维过程应用于这些操作的尝试，但由于我对这个概念还很陌生，我不确定我的逻辑是否正确，并希望得到一些关于 a) 我是否的反馈m 对或 b) 我哪里出错了。任何帮助表示赞赏。