Java中HashSet.contains()的时间复杂度性能如何? [英] What is the time complexity performance of HashSet.contains() in Java?

问题描述

我很容易想到

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支持，其中键是Object.

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方法说它们是相同的(即返回true).

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，其中的键是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屋！