This week's book giveaway is in the Other Languages forum.
We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!
See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Collections question

 
Pawanpreet Singh
Ranch Hand
Posts: 264
Eclipse IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
2. HashSet

Don't know about BitSet as far as SCJP 5 is concerned.
 
Adrian Engler
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic