HashSet包含性能 [英] HashSet.contains performance

问题描述

我试图认为 HashSet.contains（Object）方法在常量时间执行。它只是得到一个对象的哈希码，然后在哈希表中查找。

首先，有人可以确认这是否是真的吗？

第二，如果它是真的，是否有任何碰撞的风险，其中两个对象可能有相同的哈希码，因此HashSet认为它有两个当它只有一个？

解决方案

它运行在O（1）预期的时间，作为任何哈希表（假设散列函数体面）。它由 HashMap 支持，其中键是Object。

两个对象可能具有相同的哈希码，但是HashSet不会认为它们是相同的，除非等于

包含方法调用） getEntry of HashMap ，其中key是您希望知道的对象，如果它在HashSet中。 p>



如下所示，即使HashMap / HashSet的键通过哈希函数映射到相同的值，也可以将两个对象存储在HashMap / HashSet中。该方法对具有相同散列值的所有键进行迭代，并对每个键执行 equals 以找到匹配键。

  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）{
 ; 
 if（e.hash == hash& 
（（k = e.key）== key ||（key！= null&& key.equals（k））） ）
 return e; 
} 
 return null; 
} 
  




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?

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?

解决方案

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.

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).

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.

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;
     }

这篇关于HashSet包含性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！