HashSet.contains性能
我很想要HashSet.contains（Object）方法在恒定时间内执行。 它只是获取一个对象的哈希码，然后在哈希表中查找它。
首先，有人可以确认这是否属实？
第二，如果是真的，是否存在任何冲突的风险，其中两个对象可能具有相同的哈希码，因此HashSet认为它只有两个对象时只有一个？
它在O(1)预期时间内运行，就像任何哈希表一样（假设哈希函数是正常的）。 它由HashMap支持，其中键是Object。
两个对象可能具有相同的哈希代码，但HashSet不会认为它们是相同的，除非这些对象的equals方法表明它们是相同的（即返回true）。
contains方法调用（间接） HashMap getEntry ，其中key是你希望知道它是否在HashSet的Object 。
如下所示，即使哈希函数的键被哈希函数映射到相同的值，也可以在HashMap / HashSet存储两个对象。 该方法迭代具有相同散列值的所有键，并在每个键上执行equals查找匹配键。
final Entry getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry 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; }
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）中的链接列表中，但是在链接列表的情况下，set属性（没有重复）被强加到因此，在插入的情况下，它也需要遍历链表，以确保该元素在列表/存储桶中不存在，并且我们最终使用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 ）
建议使用HashSet.get(object) ，它是null或不是HashSet.contain(object) ，因为HashSet.get(object)更快。