-2

我正在研究 Java 集合性能特征、Big O 表示法和复杂性等。有一个真实的部分我无法理解，这就是为什么 HashMap 和其他哈希容器被认为是 O(1)，这应该意味着在 1,000 个条目表中通过键查找条目的时间应该与 1,000,000 个条目表的时间大致相同。

假设您有 HashMap myHashMap，存储有名字 + 姓氏的键。如果调用 myHashMap.get("FredFlinstone")，它如何能立即找到 Fred Flinstone 的 Person 对象？它怎么可能不必遍历存储在 HashMap 中的一组键来找到指向对象的指针？如果 HashMap 中有 1,000,000 个条目，则键列表也将是 1,000,000 长（假设没有冲突），即使它已排序，它也必须比 1.000 的列表花费更多的时间。那么 get() 或 containsKey() 时间如何不随 n 而变化呢？

注意：我认为我的问题会在Is a Java hashmap really O(1) 中得到回答？但答案并没有真正解决这一点。我的问题也与碰撞无关。

4

3 回答 3

4

“我的问题也与碰撞无关。” - 实际上是间接的。没有碰撞= O(1)...

在最坏的情况下（病态的情况），会有一个N挂着物品的桶，那么它会是O(N)

于 2013-09-30T01:49:30.323 回答
1

计算给定键的哈希函数需要恒定的时间。查找是否有存储到该键的值是随机访问操作 - 哈希映射由数组支持。唯一的问题是确保具有相同值（哈希冲突）的不同键不会经常发生。如果它在 n 中发生一次，那么在平均情况下就足够了。

于 2013-09-30T01:52:05.050 回答
1

让我们看一个非常简单的哈希映射和哈希函数示例。为简单起见，假设您的哈希映射有 10 个桶，并且它使用整数作为键。出于本示例的目的，我们将使用以下哈希函数：

public int hash(int key) {
  return key % 10;
}

现在，当我们想在映射中存储一个条目时，我们对键进行哈希处理，得到一个 0-9 之间的整数，然后将该条目放入相应的存储桶中。然后，当我们需要查找一个键时，我们只需要计算它的哈希值，我们就可以准确地知道它在（或将在）哪个桶中，而无需查看任何其他桶。

于 2013-09-30T02:01:57.697 回答