• 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

Question on Maps and Iterators

 
Ranch Hand
Posts: 160
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Question from Dan's exams:


Suppose that you would like to create an instance of a new Map that has an iteration order that is the same as the iteration order of an existing instance of a Map. Which concrete implementation of the Map interface should be used for the new instance?
a. TreeMap
b. HashMap
c. LinkedHashMap
d. The answer depends on the implementation of the existing instance.
e. None of the above.


I thought this would be "d" because I thought of the case where the original object is HashMap. I didn't think there would be a guarnateed iteration order to this. That's the whole point of having LinkedHashMap. Yet the answer is "c"?
 
Ranch Hand
Posts: 1392
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is what we know about the order of a HashMap.

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.


And here is what we know about the iterator of a Set, and therefore, about the iterator of the keySet of the HashMap.

Returns an iterator over the elements in this set. The elements are returned in no particular order (unless this set is an instance of some class that provides a guarantee).

Thus, any two iterations of a HashMap may produce a different order of elements, even if no elements are added or removed.
----
That said, here is what I think is the intent of the question:
----
Each time we iterate over a Map object, the elements are presented to us in some order.
Suppose we have an instance of a Map. Call it m.
Map m1 = new HashMap(m);
Map m2 = new LinkedMap(m);
Map m3 = new WeakHashMap(m);
Map m4 = new Hashtable(m);
Map m5 = new TreeMap(m);
Which new Map object will have the same order as the iteration order of m?
 
Marlene Miller
Ranch Hand
Posts: 1392
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Brian, I think this paragraph in the LinkedHashMap API, is what motivated Dan to create the question:

It can be used to produce a copy of a map that has the same order as the original, regardless of the original map's implementation:
void foo(Map m) {
Map copy = new LinkedHashMap(m);
...
}

This technique is particularly useful if a module takes a map on input, copies it, and later returns results whose order is determined by that of the copy. (Clients generally appreciate having things returned in the same order they were presented.)


If so, then c would be the correct answer.
However, a TreeMap will also produce a copy of a map that has the same order as the original, providing the original is also a TreeMap.
So, in fact, d is the correct answer, but not for the reason you offered. Although your reason is correct according to your interpretation of the question.
[ June 30, 2003: Message edited by: Marlene Miller ]
 
Brian Joseph
Ranch Hand
Posts: 160
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Marlene, I sort of figured it was my interpretation of the question. Thanks for digging into it for me and presenting all of that great info.
 
Marlene Miller
Ranch Hand
Posts: 1392
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you Brian. I am glad what I said made sense to you.
It just so happened only a day or two ago I was working on the same question in Dan's Comprehensive Exam. So it was fresh on my mind and of interest to me. It was a hard one for me. I sent Dan a question about copying a SortedMap to a TreeMap and preserving order. I wanted to share with you what I had learned.
By trying to explain to you, it reinforced what I had learned and made me understand it better. I also checked with Dan to make sure I had answered your question correctly.
I still feel uncomfortable saying the order of a HashMap is preserved. But that is the way the LinkedHashMap API thinks about it. I suppose, we know *in reality* as long as no elements are added or removed, the iteration order of a HashMap will not change.
[ July 01, 2003: Message edited by: Marlene Miller ]
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic