Java中HashSet.contains()的时间复杂度表现是什么? [英] What is the time complexity performance of HashSet.contains() in Java?

问题描述

我很想认为 HashSet.contains(Object) 方法在恒定时间内执行.它只是获取对象的哈希码，然后在哈希表中查找.

I'm tempted to think that the HashSet.contains(Object) method performs in constant time. It simply gets the hash code of an object and then looks it up in a hash table.

首先，有人可以确认一下这是否属实吗?

First, could someone please confirm whether this is true?

第二，如果它是真的，是否有冲突的风险，其中两个对象可能具有相同的哈希码，因此 HashSet 认为它有两个，而它只有一个?

Second, if it is true, is there any risk of collisions, where two objects might have the same hash code and thus the HashSet thinks it has both when it only has one?

推荐答案

它在 O(1) 预期时间内运行，就像任何哈希表一样(假设哈希函数是体面的).它由 HashMap 支持，其中键是对象.

It runs in O(1) expected time, as any hash table (assuming the hash function is decent). It is backed by a HashMap where the key is the Object.

两个对象可能具有相同的哈希码，但 HashSet 不会认为它们是相同的，除非这些对象的 equals 方法表明它们相同(即返回真).

Two objects might have the same hash code, but the HashSet wouldn't think they are identical, unless the equals method for these objects says they are the same (i.e. returns true).

contains 方法调用(间接)HashMap 的getEntry，其中 key 是您要使用的 Object想知道它是否在 HashSet 中.

The contains method calls (indirectly) getEntry of HashMap, where key is the Object for which you wish to know if it's in the HashSet.

如下所示，两个对象可以存储在 HashMap/HashSet 中，即使它们的键被哈希函数映射到相同的值.该方法遍历所有具有相同哈希值的键，并对每个键执行 equals 以找到匹配的键.

As you can see below, two objects can be stored in the HashMap/HashSet even if their key is mapped to the same value by the hash function. The method iterates over all keys that have the same hash value, and performs equals on each one to find the matching key.

final Entry<K,V> getEntry(Object key) {
         int hash = (key == null) ? 0 : hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];
              e != null;
              e = e.next) {
             Object k;
             if (e.hash == hash &&
                 ((k = e.key) == key || (key != null && key.equals(k))))
                 return e;
         }
         return null;
     }

这篇关于Java中HashSet.contains()的时间复杂度表现是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！