Collections question

[Pawanpreet Singh]

Which class offer a constant time performance for the basic operation - add(), remove(), contains() and size() ?
* 1. TreeSet
* 2. HashSet
* 3. BitSet
* 4. None of these.
could anybody help me to solve this?

[Jacky Zhang]

2. HashSet

Don't know about BitSet as far as SCJP 5 is concerned.

[Adrian Engler]

There is a class java.util.BitSet, but it does not have add(), remove() and contains() methods, so 3. cannot be the correct answer (and as far as SCJP 5 is concerned, I don't think it's covered, either).

The time needed for adding an element to a TreeSet is not constant, but grows logarithmically (i.e. quite moderately) with the size of the set because of the effort needed to put it at the correct position in the sorted treeset.

As was mentioned, the correct answer is 2 (HashSet). But the fact that the HashSet class "offers" constant time access does not mean that access to the elements every concrete HashSet will be constant when the set grows. What is decisive is whether a good hashcode is used - what is constant is calculating the hashcode. If many non-equal elements have identical hashcodes (which is inefficient, but not illegal and not disallowed by the hashcode contract), after calculating the hashcode, still a lot of searching will be needed. Since hashcodes are not guaranteed to be unique, the promise of constant time access is not absolute, but with a good hashcode (e.g. in Java with Strings or wrapper classes), it is so close to constant that for practical purposes it can be regarded as constant.