检查 HashSet 中是否存在字符串的时间复杂度 Java

Question

简而言之，我很困惑检查HashSet中是否存在String的时间复杂度是O(1)还是O(m)，m是被检查的最长字符串的长度。

我了解到要放置字符串的桶是由字符串的 hashCode() 方法确定的，该方法对 HashSet 的大小取模。所以这意味着为了找出一个字符串是否存在于一个HashSet中，需要计算hashCode。

在 String class 的 hashCode 方法中，我可以看到您必须遍历整个字符串才能计算出该值。但我也看到有一个缓存这个值的选项。

这就是我困惑的地方。字符串的哈希码是否在创建字符串期间被缓存？还是我们显式调用hashcode方法时缓存了？对 hashCode 方法的隐式调用（如检查 String 是否存在于 Set 中的情况）是否也缓存值？

HashSet 中字符串的第一次存在性检查的时间复杂度是多少？

谢谢。

编辑：因为我似乎没有很好地解释我的要求：我不是在谈论如果发生链接（如果存在哈希冲突就会发生）/或调整哈希集大小时的时间复杂度。现在假设哈希集中没有冲突。因此每个桶的大小最大为 1。在这种情况下，如果我检查哈希集中是否存在字符串，它会花费 O(1) 时间还是 O(m) 时间（因为字符串可以有 O (m) 个字符在最坏情况下计算哈希码需要遍历整个字符串)

Answer 1

计算给定 hashCode 的时间取决于算法以及是否需要在每次调用时计算。 Integer 不进行任何计算，因为 hashCode 是 int 值。字符串将是 O(n)，其中 n 是字符数。

这是 Latin1 个字符串的 hashCode 算法。

public static int hashCode(byte[] value) {
        int h = 0;
        for (byte v : value) {
            h = 31 * h + (v & 0xff);
        }
        return h;
    }

但是，字符串的哈希码只计算一次，因为字符串是不可变的。因此对 String 的 hashCode 调用将 return 缓存值。

Answer 2

如果您要检查的字符串是 new 字符串，则必须计算其 hashCode 以找到其存储桶，因此 hashCode 计算的 O(m) 和O(1) 用于存在性检查，所以 O(m).

如果String对象已经存在于Set中（或者它的hashCode已经计算出来），检查它是O(1)，因为它的hashCode被缓存了。

检查 HashSet 中是否存在字符串的时间复杂度 Java

Time Complexity of checking whether a string is present in a HashSet Java

java

string

hashmap

hashset