2

我读了声明：

HashSet 为基本操作（添加、删除、包含和大小）提供恒定的时间性能。

这里的“包含”是真的吗？虽然将存储桶列入候选名单是一种持续时间的表现 - 不是在存储桶 ao(n) 操作中找到元素吗？

我误解了什么吗？

4

6 回答 6

2

正如文件所说，

此类为基本操作（添加、删除、包含和大小）提供恒定的时间性能，假设哈希函数将元素正确地分散在桶中

检查上面的假设部分。如果所有元素最终都在一个桶中，则包含为 o(n)，这将是世界上最差的哈希函数之一的结果。HashSet 内部使用 HashMap。

于 2013-03-29T05:39:20.860 回答
2

n in o(n) 代表散列中的元素数，而不是桶中的元素数。并且由于桶内的元素数量不会随着集合的大小线性增长并且是有限的，因此可能需要一个恒定的最大时间。并且恒定时间不会影响符号。至少如果你有一个完美的散列函数，这完全是另一个问题。

于 2013-03-29T05:44:58.763 回答
0

HashSet使用 hasing 函数来定位元素。在其中进行评估是 O(1)。

例如，如果我们有一个用于存储员工姓名的哈希表，我们将使用该函数作为其中 ASCII 字符的总和：

f(name) = sum(ascii chars)

f('ahmed') = 'a' + 'h' + 'm' + 'e' + 'd' = 97 + 104 + 109 + 101 + 100 = 511。所以，'ahmed' 将存储在位置511. 但是，之前的哈希函数非常糟糕，并且在使用产生相同总和的名称进行评估时会导致很多冲突。因此，找到一个好的散列函数是散列表实现中非常关键的目标。

有关详细信息，请参阅哈希表数据结构。

于 2013-03-29T05:29:30.283 回答
0

是的finding the elements within the bucket a o(n) operation。
contains运算性能为 O(n)。它等于目标对象与内部的所有其他对象HashSet。

于 2013-03-29T05:35:37.110 回答
0

顾名思义HashSet是通过hasing技术实现的。所以这意味着找到一个对象的复杂度是 O(1)。这就是为什么contains需要 O(1) 时间的原因。但在最坏的情况下，如果所有对象都放在同一个桶中，那么复杂度将是 O(n)。

如果此集合包含指定的元素，则返回 true。更正式地说，当且仅当此集合包含满足 (o==null ? e==null : o.equals(e)) 的元素 e 时才返回 true。

public boolean contains(Object o) {
    return map.containsKey(o);
}

上面是 HashSet 类的 contains 方法。请注意，它使用地图来存储对象。

于 2013-03-29T05:47:35.927 回答
0

是不是在桶 ao(n) 操作中找到元素？

这真的取决于。如果哈希冲突太多以至于算法必须遍历每个值并检索您感兴趣的值，那么在最坏的情况下时间是 o(n)。但是，它根本就不是一个好的散列函数。一个好的散列函数在其范围内平均分布分配的散列。

如果您一直返回相同hashCode的内容，也可能发生这种情况，这也不是一个好兆头。无论集合的基数如何，这都会为您提供相同的哈希值。

于 2013-03-29T05:52:59.390 回答