简而言之，我很困惑检查 HashSet 中是否存在字符串的时间复杂度是 O(1) 还是 O(m)，m 是要检查的最长字符串的长度。
据我了解，要放置字符串的存储桶是由字符串的 hashCode() 方法对 HashSet 的大小取模来确定的。所以这意味着为了查明某个字符串是否存在于 HashSet 中，需要计算 hashCode。
在String类的hashCode方法中，我可以看到你必须迭代整个字符串才能计算这个值。但我也看到有一个缓存该值的选项。
这就是我困惑的地方。在创建字符串的过程中，字符串的哈希码是否会被缓存？或者当我们显式调用hashcode方法时它会被缓存吗？对 hashCode 方法的隐式调用(如检查 Set 中是否存在 String 的情况)是否也会缓存该值？
HashSet 中字符串第一次存在性检查的时间复杂度是多少？
谢谢。
编辑:因为我似乎没有很好地解释我要问的内容: 我不是在谈论如果发生链接(如果存在哈希冲突就会发生)/或者调整哈希集大小时的时间复杂度。现在假设哈希集中不存在冲突。因此每个桶的大小最大为 1。在这种情况下，如果我检查哈希集中是否存在字符串，是否需要 O(1) 时间或 O(m) 时间(因为字符串可以有 O (m) 最坏情况下的字符，计算哈希码需要遍历整个字符串)
最佳答案
如果您要检查的字符串是一个新字符串，则必须计算其 hashCode 才能找到其存储桶，因此 hashCode 计算的复杂度为 O(m)，计算的 hashCode 的复杂度为 O(1)存在性检查，所以 O(m)。
如果 String 对象已经存在于 Set 中(或者它的 hashCode 已经计算出来)，则检查它的复杂度是 O(1)，因为它的 hashCode 已被缓存。
关于java - 检查字符串是否存在于 HashSet Java 中的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68422044/