aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Collections question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Collections question" Watch "Collections question" New topic
Author

Collections question

Pawanpreet Singh
Ranch Hand

Joined: Jun 12, 2005
Posts: 264

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
Greenhorn

Joined: Sep 17, 2006
Posts: 18
2. HashSet

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

Joined: Sep 18, 2006
Posts: 29
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.


SCJP 5.0 (93%), SCWCD (98%), SCJD (377/400), SCBCD (100%)
 
 
subject: Collections question