• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Paul Clapham
  • Ron McLeod
Sheriffs:
  • Jeanne Boyarsky
  • Liutauras Vilda
Saloon Keepers:
  • Tim Holloway
  • Carey Brown
  • Roland Mueller
  • Piet Souris
Bartenders:

Collections question

 
Ranch Hand
Posts: 264
Eclipse IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
2. HashSet

Don't know about BitSet as far as SCJP 5 is concerned.
 
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic