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?

Suemayah Eldursi
  • 969
  • 4
  • 14
  • 36
  • 1
    you can see the source code here: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashSet.java – ΦXocę 웃 Пepeúpa ツ Apr 05 '17 at 15:03
  • Possible duplicate of [HashSet.contains performance](http://stackoverflow.com/questions/25247854/hashset-contains-performance) – Ashraful Islam Apr 05 '17 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 05 '17 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 05 '17 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. – Eric Duminil Apr 05 '17 at 15:06
  • The "fingerprint", to be clear, is the `equals` comparison. – Lew Bloch Apr 05 '17 at 18:00

1 Answers1

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.

Eugene
  • 117,005
  • 15
  • 201
  • 306
  • 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. – Suemayah Eldursi Apr 06 '17 at 08:45