What is the time complexity performance of HashSet.contains() in Java?

by

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

More Related Contents:

  1. What are the reasons why Map.get(Object key) is not (fully) generic
  2. Sorting an ArrayList of objects using a custom sorting order
  3. Why should the interface for a Java class be preferred?
  4. Sorting a collection of objects [duplicate]
  5. How to remove duplicates from a list?
  6. How to convert a Map to List in Java?
  7. Big-O summary for Java Collections Framework implementations? [closed]
  8. How to make a new List in Java
  9. Lambda expression to convert array/List of String to array/List of Integers
  10. Combine multiple Collections into a single logical Collection?
  11. Why we can’t do List mylist = ArrayList(); [duplicate]
  12. Map.clear() vs new Map : Which one will be better? [duplicate]
  13. Java – generate Random range of specific numbers without duplication of those numbers – how to?
  14. Iterating through a list in reverse order in java
  15. How to Serialize a list in java?
  16. Collections.emptyList() vs. new instance
  17. How to iterate over a PriorityQueue?
  18. How to sort a Collection?
  19. Java Stream: divide into two lists by boolean predicate
  20. Is there a no-duplicate List implementation out there?
  21. Rule of thumb for choosing an implementation of a Java Collection?
  22. Arrays.asList give UnsupportedOperationException [duplicate]
  23. Difference between Java Enumeration and Iterator
  24. How to create ArrayList (ArrayList) from array (int[]) in Java
  25. Is there an insertion order preserving Set that also implements List?
  26. When should I return the Interface and when the concrete class?
  27. Storing different types of elements in a List in Java
  28. Are they any decent on-disk implementations of Java’s Map?
  29. Hashmap implementation to count the occurrences of each character
  30. Perform operation on n random distinct elements from Collection using Streams API

Leave a Comment