HashSet.contains性能

Question

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

首先,有人可以确认这是否属实？

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

Answer 1

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

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

该contains方法调用(间接)getEntry的HashMap,其中关键是Object要为其知道,如果它在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) {
             Object k;
             if (e.hash == hash &&
                 ((k = e.key) == key || (key != null && key.equals(k))))
                 return e;
         }
         return null;
     }

Answer 2

contains的最坏情况性能是Java 8的O(log n)和Java 7的O(n),但是平均情况更接近O(1).这是因为hashset由hashmap支持,因此具有与hashmap lookup相同的效率(即HashMap.get(...)).散列映射中的实际映射是常量时间(O(1)),但是处理冲突的需要带来了记录n的成本.也就是说,散列到相同数组索引的多个元素必须存储在辅助数据结构(也称为存储桶)中,并且正是此存储桶确定最坏情况的性能.在Java中,hahsmap colission-handling是使用自平衡树实现的.

自平衡树保证所有操作的O(log n),因此,hashmap(和hashset)中的插入和查找的总成本为O(1)+ O(log n)= O(log n).在Java 8中引入了自平衡树用于冲突处理的使用,作为对链接的改进(直到java 7使用),它使用链表,并且具有用于查找和插入的最坏情况O(n) (因为它需要遍历列表).请注意,链接将有恒定的插入时间(而不是查找),因为元素可以添加到O(1)中的链接列表中,但是在链接列表中强制设置属性(没有重复)因此,在插入的情况下,它也需要遍历链表,以确保该元素在列表/存储桶中不存在,并且我们最终使用O(n)进行插入和查找.

参考文献:

此类实现Set接口,由哈希表(实际上是HashMap实例)支持. https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

包含大量碰撞键的存储桶将在达到特定阈值后将其条目存储在平衡树中而不是链接列表中.(https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8)