3

I want to search efficiently for an object in a HashSet that I have.

I would like to know if the contains() method which is defined on java collections uses binary search or not? Or should I write my own binary search algorithm?

6
  • 1
    you can see the source code here: grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… Apr 5, 2017 at 15:03
  • Possible duplicate of HashSet.contains performance Apr 5, 2017 at 15:03
  • 4
    "HashSet" and "binary search" won't fit together. Reason: binary search requires a sorted (and thus ordered) collection while hash sets are unordered by definition.
    – Thomas
    Apr 5, 2017 at 15:03
  • 1
    "This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets."
    – Zircon
    Apr 5, 2017 at 15:04
  • HashSet isn't ordered, so you'll have trouble running a binary-search. The way contains() works : it calculates the "fingerprint" of the contains() argument. It then checks if it knows this fingerprint. Done. Apr 5, 2017 at 15:06

1 Answer 1

4

The general search complexity in a HashSet is O(1) - meaning it is constant. Writing your own? Better then this?

You absolutely can look at the sources, understand that a HashSet is actually a HashMap internally; that it uses buckets and LinkedNodes and TreeNodes; understand how these work, etc etc. Or trust the implementation that is good and focus on other stuff; unless you honestly have a requirement for something faster.

1
  • Hi, thanks for the info. I find what you have said useful. I am using hashsets to store some objects retrieved from a database. Sometimes I want to check if a certain object is within the set. From what you have mentioned, the contains() method should suit my purposes. Apr 6, 2017 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.