java - 为什么 HashMap 中 get() 的时间复杂度为 O(1)

Question

哈希图中有恒定数量的桶（比方说b）

我们有 N 个元素并假设 N 非常大并且 N >> b

现在每个桶包含 N/b 个元素，假设我们的哈希函数是好的。

如果我们将桶中的元素存储为链表，那么在 N/b 个元素的列表中搜索仍然是 O(N)。即使我们假设每个桶中的元素存储为一棵树，在 N/b 个元素的树中搜索仍然是 O(logN)。

我知道每次负载因子达到阈值时 b 都会加倍。这是否使 b 本身成为 O(N)。如果是这种情况，则说明 O(1)。但是如果 b 不是 O(N) 那么我们如何解释地图上的 O(1) 操作呢？

这个词amortized用于描述 O(1)，我认为它是指平均情况而不是最坏情况。但即使在一般情况下，我也看不出它是 O(1)。

标签： javahashmaptime-complexity