• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Danchisholms: Collections question

 
Ranch Hand
Posts: 1710
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Arrow Marked options are correct! Please eleborate the correct options.
My main concern is over constant time performance.

Modified post:
Sorry A,F,H are the correct answer!

Regards,
cmbhatt
[ April 17, 2007: Message edited by: Chandra Bhatt ]
 
Ranch Hand
Posts: 2412
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Are you sure that e and h are correct?
 
Ranch Hand
Posts: 206
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think this is becuase the Hashtable,HashMap and LinkedHashMap all have one thing common.

The hashCode and equals functions are used to find a key.Given a key value the time taken to compute the hashCode would be the same for any key value.

In case of add, it computes the hashCode of the key to be added and lands up in a say bucket, does equals comparision with the keys in the bucket , replaces oldkey's value with newkey's value the same key is found and adds key if no key is found..

In case of contains it computes the hashCode of the key to be searched and lands up in a bucket, does equals comparision with the keys in the bucket and the input key and returns true or false.

In case of remove too, it computes the hashCode of the key to be searched and lands up in a bucket, does equals comparision with the keys in the bucket and the input key and removes the key value if found.

So all in all the hash computing time is constant, landing up in a bucket time is constant, the doing equals comparision within a bucket might vary depending on how efficient the hash algorithm is but generally
the time for all this operations can be considered constant.
 
Ranch Hand
Posts: 1274
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi ranchers,


how I understand this question:

first feature (key/value pairs)
The only collections that provide keys are maps. Maps are collections that have "map" in their name. Hashtable is also a map, but has no "map" in its name because of historical reasons.
So we can strike out all wrong answers and only
LinkedHashMap
TreeMap
HashMap
Hashtable (old synchronized version of HashMap)
remain.


second feature (Duplicate entries replace old)
true for all maps, cause duplicate keys "override" old key value pairs.


third feature (constant-time performance for add...)
TreeMap is ordered. Every time you add something, the tree has to be ordered again. And the time to do this depends if you add in the middle or at the tail. IE it depends if you add an "N" or a "Z", simply speaking.
Re-Ordering also takes place when you remove(), so we can strike TreeMap out two times.
LinkedHashMap
HashMap
Hashtable
remain.


About LinkedHashMap:
It is not ordered, just sorted (by entry time). Every time you add a pair it is just glued to the tail, should be time constant.



Bu.
 
Chandra Bhatt
Ranch Hand
Posts: 1710
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks a lot Burkhard,

Ramification of answering was great. I got it step by step as you described.
It can help me to find answers of the similar questions.


For you:

Regards,
cmbhatt
 
reply
    Bookmark Topic Watch Topic
  • New Topic