Glitch in Java Collections (No descendingMap in LinkedHashMap)

Discussion in 'Java' started by Jan Burse, Oct 4, 2012.

  1. Jan Burse

    Jan Burse Guest

    Dear All,

    I just wonder whether I have overlooked something.
    But could it be that LinkedHashMap is lacking the
    following API:

    Map<K,V> descendingMap();

    So I can only iterate from oldest to youngest, and
    not the other direction?

    Although under the hood it uses a double linked list,
    and a reverse iterator would be simple.

    Also the whole matter seems to be complicated, since
    the other collections have descendingMap() in an
    Interface NavigableMap, which extends SortedMap.

    But SortedMap map assumes a compartor, whereby the
    sorting in LinkedHashMap is implicit.

    Is there some shortcut to arrive at a reverse iterator
    of LinkedHashMap?

    (Troll disclaimer: No I have no SSCCE (Short, Self
    Contained, Correct (Compilable), Example). This is
    a conceptual question.)

    Bye
    Jan Burse, Oct 4, 2012
    #1
    1. Advertising

  2. On 04.10.2012 14:09, Jan Burse wrote:
    > Dear All,
    >
    > I just wonder whether I have overlooked something.
    > But could it be that LinkedHashMap is lacking the
    > following API:
    >
    > Map<K,V> descendingMap();
    >
    > So I can only iterate from oldest to youngest, and
    > not the other direction?


    I guess they omitted it because the purpose is to provide a Map which
    always returns elements in insertion order (and not reverse insertion
    order).

    > Although under the hood it uses a double linked list,
    > and a reverse iterator would be simple.
    >
    > Also the whole matter seems to be complicated, since
    > the other collections have descendingMap() in an
    > Interface NavigableMap, which extends SortedMap.


    There you see why it's not in LinkedHashMap: it's neither a NavigableMap
    nor a SortedMap.

    > But SortedMap map assumes a compartor, whereby the
    > sorting in LinkedHashMap is implicit.


    There is no sorting going on - you just get insertion order.

    Cheers

    robert

    --
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
    Robert Klemme, Oct 4, 2012
    #2
    1. Advertising

  3. Jan Burse

    Lew Guest

    Robert Klemme wrote:
    > Jan Burse wrote:
    >> I just wonder whether I have overlooked something.
    >> But could it be that LinkedHashMap is lacking the
    >> following API:

    >
    >> Map<K,V> descendingMap();


    It's also lacking 'ascendingMap()'

    >> So I can only iterate from oldest to youngest, and
    >> not the other direction?

    >
    > I guess they omitted it because the purpose is to provide a Map which
    > always returns elements in insertion order (and not reverse insertion
    > order).
    >
    >> Although under the hood it uses a double linked list,
    >> and a reverse iterator would be simple.
    >>
    >> Also the whole matter seems to be complicated, since
    >> the other collections have descendingMap() in an
    >> Interface NavigableMap, which extends SortedMap.

    >
    > There you see why it's not in LinkedHashMap: it's neither a NavigableMap
    > nor a SortedMap.
    >
    >> But SortedMap map assumes a compartor, whereby the
    >> sorting in LinkedHashMap is implicit.

    >
    > There is no sorting going on - you just get insertion order.


    You get insertion order how?

    The interesting thing about this class is that it has no public methods that reveal
    the order.

    So what difference does the order make?

    I can guess, but the docs don't confirm, that iterators off the keyset or entryset would
    respect the order, but the documentation for the 'keySet()' and 'entrySet()' methods doesn't
    promise this.

    It's useful for subclasses, from what the documentation hints, but to the public?

    --
    Lew
    Lew, Oct 4, 2012
    #3
  4. Jan Burse

    Jan Burse Guest

    Lew schrieb:
    > You get insertion order how?


    The class LinkedHashMap provides two orders. It has a constructor:

    /**
    ...
    * @param accessOrder the ordering mode - <tt>true</tt> for
    * access-order, <tt>false</tt> for insertion-order
    ...
    */
    public LinkedHashMap(int initialCapacity,
    float loadFactor,
    boolean accessOrder)

    I am only interested in the case accessOrder = false. As you see
    the doc mentions itself the term "insertion-order".

    I would refine it to "first-insert-order". Since the implementation
    is such that only the first put() counts concerning the order.

    put 2, 1, 1, 2
    Gives you the order 2, 1

    Bye
    Jan Burse, Oct 4, 2012
    #4
  5. On 04.10.2012 23:43, Lew wrote:
    > Robert Klemme wrote:
    >> Jan Burse wrote:


    >>> But SortedMap map assumes a compartor, whereby the
    >>> sorting in LinkedHashMap is implicit.

    >>
    >> There is no sorting going on - you just get insertion order.

    >
    > You get insertion order how?


    First paragraph of JavaDoc:

    Hash table and linked list implementation of the Map interface, with
    predictable iteration order. This implementation differs from HashMap in
    that it maintains a doubly-linked list running through all of its
    entries. This linked list defines the iteration ordering, which is
    normally the order in which keys were inserted into the map
    (insertion-order). Note that insertion order is not affected if a key is
    re-inserted into the map.

    > The interesting thing about this class is that it has no public methods that reveal
    > the order.


    Why would they need to?

    > So what difference does the order make?


    There are some use cases described in the class JavaDoc.

    > I can guess, but the docs don't confirm, that iterators off the keyset or entryset would
    > respect the order, but the documentation for the 'keySet()' and 'entrySet()' methods doesn't
    > promise this.


    You do not have to guess - logical reasoning is enough. The only way to
    iterate through a Map is via entrySet(), keySet() and values(). What
    other methods could make use of the order if not these?

    > It's useful for subclasses, from what the documentation hints, but to the public?


    It seems you could create a LRU Map with this, right. Other uses are
    described in the class doc as mentioned above.

    Kind regards

    robert



    --
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
    Robert Klemme, Oct 5, 2012
    #5
  6. Jan Burse

    Lew Guest

    Robert Klemme wrote:
    > Lew wrote:
    >> Robert Klemme wrote:
    >>> Jan Burse wrote:

    > > You get insertion order how?

    >
    > First paragraph of JavaDoc:
    >
    > Hash table and linked list implementation of the Map interface, with
    > predictable iteration order. This implementation differs from HashMap in
    > that it maintains a doubly-linked list running through all of its
    > entries. This linked list defines the iteration ordering, which is
    > normally the order in which keys were inserted into the map
    > (insertion-order). Note that insertion order is not affected if a key is
    > re-inserted into the map.


    That says how you put the order, not how you get the order.

    >> The interesting thing about this class is that it has no public methods that reveal
    >> the order.

    >
    > Why would they need to?


    If the ordered state is not observable, what difference does it make?

    >> So what difference does the order make?

    >
    > There are some use cases described in the class JavaDoc.


    It doesn't explain how you reveal the order, only how you put it into another structure.

    >> I can guess, but the docs don't confirm, that iterators off the keyset or entryset would
    >> respect the order, but the documentation for the 'keySet()' and 'entrySet()' methods doesn't
    >> promise this.

    >
    >
    > You do not have to guess - logical reasoning is enough. The only way to
    > iterate through a Map is via entrySet(), keySet() and values(). What
    > other methods could make use of the order if not these?


    But these methods do not promise to return the data in any particular order, particularly
    they do not promise to return the data in the order stored. In fact, they promise not to,
    necessarily. From Set#iterator(): "The elements are returned in no particular order
    (unless this set is an instance of some class that provides a guarantee)."

    The Map makes the guarantee, and one has to infer the underlying Set will therefore
    make that guarantee, but when one copies the Map into another Map implementation,
    even that implicit promise is removed. Furthermore, why do they not state that the Set
    implementation iterator's order is guaranteed? It seems there's a hole in the docs.

    >> It's useful for subclasses, from what the documentation hints, but to the public?

    >
    > It seems you could create a LRU Map with this, right. Other uses are
    > described in the class doc as mentioned above.


    Right, that LRU Map would be a subclass, as I said.

    --
    Lew
    Lew, Oct 5, 2012
    #6
  7. Jan Burse

    Jan Burse Guest

    Lew schrieb:
    >> There are some use cases described in the class JavaDoc.

    > It doesn't explain how you reveal the order,


    Java doc that only shows public entries does indeed not
    help, since the magic happens in a package local method.

    From HashMap:

    // Subclass overrides these to alter behavior of views' iterator()
    method
    Iterator<K> newKeyIterator() {
    return new KeyIterator();
    }
    Iterator<V> newValueIterator() {
    return new ValueIterator();
    }
    Iterator<Map.Entry<K,V>> newEntryIterator() {
    return new EntryIterator();
    }

    From LinkedHashMap:

    // These Overrides alter the behavior of superclass view iterator()
    methods
    Iterator<K> newKeyIterator() { return new KeyIterator(); }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new
    EntryIterator(); }
    Jan Burse, Oct 5, 2012
    #7
  8. Jan Burse

    Daniel Pitts Guest

    On 10/5/12 11:05 AM, Lew wrote:
    > Robert Klemme wrote:
    >> Lew wrote:
    >>> Robert Klemme wrote:
    >>>> Jan Burse wrote:
    >>> You get insertion order how?

    >>
    >> First paragraph of JavaDoc:
    >>
    >> Hash table and linked list implementation of the Map interface, with
    >> predictable iteration order. This implementation differs from HashMap in
    >> that it maintains a doubly-linked list running through all of its
    >> entries. This linked list defines the iteration ordering, which is
    >> normally the order in which keys were inserted into the map
    >> (insertion-order). Note that insertion order is not affected if a key is
    >> re-inserted into the map.

    >
    > That says how you put the order, not how you get the order.


    What are you talking about Lew?
    The JavaDoc says specifically "with predictable iteration order.".

    This indicates that the iteration order is the same as the order in
    which items are "put", baring key collisions.
    >
    >>> The interesting thing about this class is that it has no public methods that reveal
    >>> the order.

    >>
    >> Why would they need to?

    >
    > If the ordered state is not observable, what difference does it make?

    The ordered state is observable through iteration. The OP was only
    asking for reverse iterator, which isn't part of what he can get. I
    wouldn't call that a glitch, just a feature request.
    >
    >>> So what difference does the order make?

    >>
    >> There are some use cases described in the class JavaDoc.

    >
    > It doesn't explain how you reveal the order, only how you put it into another structure.


    Iteration is how you reveal the order.
    Daniel Pitts, Oct 5, 2012
    #8
  9. Jan Burse

    Lew Guest

    On Friday, October 5, 2012 12:06:18 PM UTC-7, Daniel Pitts wrote:
    > Iteration is how you reveal the order.


    Iteration of what?

    Again, my concern is that 'Set' doesn't promise predictable iteration order, in fact,
    exactly the opposite. The only iterators available for a 'Map' are through its 'Set'-
    returning methods, which result in a collection that promises not to have a predictable
    iteration order.

    So I ask one more time - in what way is that guaranteed iteration order revealed?

    I understand that the only way is through those iterators, but the Javadocs have a hole
    in them about that.

    --
    Lew
    Lew, Oct 5, 2012
    #9
  10. Jan Burse

    Jan Burse Guest

    Lew schrieb:
    > Again, my concern is that 'Set' doesn't promise predictable iteration order, in fact,
    > exactly the opposite. The only iterators available for a 'Map' are through its 'Set'-
    > returning methods, which result in a collection that promises not to have a predictable
    > iteration order.


    Well that is not fully correct. When you get a keySet, entrySet or
    valueSet, you indeed get an object that is derived from the class
    Set. And this class in itself has indeed no guarantee.

    The key for understanding what guarantees are around, is looking at
    the interface which provides the keySet, entrySet or valueSet. For
    example when the entrySet comes from SortedMap, then we have the
    following javadoc:

    public interface SortedMap<K,V> extends Map<K,V> {

    /**
    * Returns a {@link Set} view of the mappings contained in this map.
    * The set's iterator returns the entries in ascending key order.
    ...
    */
    Set<Map.Entry<K, V>> entrySet();

    Do you see the mention of ascending key order above?

    But LinkedHashMap does not implement this interface as I mentioned
    in my initial post. And HashMap, the super class, has no guarantee.
    So this is probably a Java glitch.

    But I was not aspiring in detecting this glitch. I am more interested
    in the reverse iterator. Any route to get at a reverse iterator?

    Bye
    Jan Burse, Oct 5, 2012
    #10
  11. Jan Burse

    Jan Burse Guest

    Jan Burse schrieb:
    > Well that is not fully correct. When you get a keySet, entrySet or
    > valueSet, you indeed get an object that is derived from the class
    > Set. And this class in itself has indeed no guarantee.


    Corr.:
    keySet or entrySet.
    Jan Burse, Oct 5, 2012
    #11
  12. Jan Burse

    Jan Burse Guest

    Jan Burse schrieb:
    > But I was not aspiring in detecting this glitch.


    My post implies that I would fix this glitch by
    introducing a new interface such as:

    public interface ImplicitlySortedMap<K,V> {
    }

    But its not clear where to squeeze in this interface.
    Basically I think the main glitch is to locate the
    following method in NavigableMap:

    public interface NavigableMap<K,V> {
    NavigableMap<K,V> descendingMap();
    }

    So I would place it in the new interface,
    instead of in NavigableMap:

    public interface ImplicitlySortedMap<K,V> {
    ImplicitlySortedMap<K,V> descendingMap();
    }

    And then squeezethe the new interface into the interface
    hierarchie after Map and before SortedMap:

    public interface ImplicitlySortedMap<K,V> extends Map<K,V> {
    }
    public interface SortedMap<K,V> extends ImplicitlySortedMap<K,V> {
    }

    Bye
    Jan Burse, Oct 5, 2012
    #12
  13. Jan Burse

    Daniel Pitts Guest

    On 10/5/12 1:04 PM, Lew wrote:
    > On Friday, October 5, 2012 12:06:18 PM UTC-7, Daniel Pitts wrote:
    >> Iteration is how you reveal the order.

    >
    > Iteration of what?

    Anything that is a view into this map.
    >
    > Again, my concern is that 'Set' doesn't promise predictable iteration order, in fact,
    > exactly the opposite. The only iterators available for a 'Map' are through its 'Set'-
    > returning methods, which result in a collection that promises not to have a predictable
    > iteration order.

    The intent is pretty clear to me. It is predictable if the Set (or
    Collection for the values() method) comes from a LinkedHashSet.
    >
    > So I ask one more time - in what way is that guaranteed iteration order revealed?

    By definition of this class, both in documentation and implementation.

    > I understand that the only way is through those iterators, but the Javadocs have a hole
    > in them about that.

    Perhaps they do, but the intent is more than clear, as is the
    implementation. Perhaps the JavaDoc could have been more explicit, but
    that isn't the point.

    Any iteration over the contents of LinkedHashMap has a guaranteed order.
    Daniel Pitts, Oct 5, 2012
    #13
  14. Jan Burse <> wrote:
    > Lew schrieb:
    >> Again, my concern is that 'Set' doesn't promise predictable
    >> iteration order, in fact, exactly the opposite.
    >> The only iterators available for a 'Map' are through its 'Set'-
    >> returning methods, which result in a collection that promises
    >> not to have a predictable iteration order.


    > Well that is not fully correct. When you get a keySet, entrySet or
    > valueSet, you indeed get an object that is derived from the class
    > Set. And this class in itself has indeed no guarantee.


    (snip)

    > But LinkedHashMap does not implement this interface as I mentioned
    > in my initial post. And HashMap, the super class, has no guarantee.
    > So this is probably a Java glitch.


    > But I was not aspiring in detecting this glitch. I am more interested
    > in the reverse iterator. Any route to get at a reverse iterator?


    There are some problems in PracticeIt that require one to reverse
    the order of something. Especially in the section on stacks.
    Write a loop that takes objects and pushes them onto a stack.
    Then remove them from the stack in the appropriate order.

    Usually two lines instead of one.

    http://webster.cs.washington.edu:8080/practiceit/

    -- glen
    glen herrmannsfeldt, Oct 6, 2012
    #14
  15. Jan Burse

    Jan Burse Guest

    glen herrmannsfeldt schrieb:
    >> But I was not aspiring in detecting this glitch. I am more interested
    >> >in the reverse iterator. Any route to get at a reverse iterator?

    > Write a loop that takes objects and pushes them onto a stack.
    > Then remove them from the stack in the appropriate order.


    The idea would of course be to have an iterator and not
    do a copy of the LinkedHashMap. Copying the LinkedHashMap
    could be a last resort, but for larger LinkedHashMaps and
    frequent iteration this is not an option.

    Bye
    Jan Burse, Oct 6, 2012
    #15
  16. Jan Burse

    Jan Burse Guest

    Jan Burse schrieb:
    > glen herrmannsfeldt schrieb:
    >>> But I was not aspiring in detecting this glitch. I am more interested
    >>> >in the reverse iterator. Any route to get at a reverse iterator?

    >> Write a loop that takes objects and pushes them onto a stack.
    >> Then remove them from the stack in the appropriate order.

    >
    > The idea would of course be to have an iterator and not
    > do a copy of the LinkedHashMap. Copying the LinkedHashMap
    > could be a last resort, but for larger LinkedHashMaps and
    > frequent iteration this is not an option.
    >
    > Bye
    >


    On the other hand.

    One could hold a parallel structure to the LinkedHashMap,
    and already fill this parallel structure during put(). And
    then use this parallel structure for the reverse iteration.

    For example instead:

    put(key, value);

    One could do:

    if (put(key, value)==null)
    list.add(key);

    And then use the list in reverse order to get a
    keySet reverse iterator.

    Bye
    Jan Burse, Oct 6, 2012
    #16
  17. On 05.10.2012 20:05, Lew wrote:
    > Robert Klemme wrote:
    >> Lew wrote:
    >>> Robert Klemme wrote:


    >>> So what difference does the order make?

    >>
    >> There are some use cases described in the class JavaDoc.

    >
    > It doesn't explain how you reveal the order, only how you put it into another structure.


    Lew, I'm sorry, but I think you're overly picky here.

    >>> I can guess, but the docs don't confirm, that iterators off the keyset or entryset would
    >>> respect the order, but the documentation for the 'keySet()' and 'entrySet()' methods doesn't
    >>> promise this.

    >>
    >>
    >> You do not have to guess - logical reasoning is enough. The only way to
    >> iterate through a Map is via entrySet(), keySet() and values(). What
    >> other methods could make use of the order if not these?

    >
    > But these methods do not promise to return the data in any particular order, particularly
    > they do not promise to return the data in the order stored. In fact, they promise not to,
    > necessarily. From Set#iterator(): "The elements are returned in no particular order
    > (unless this set is an instance of some class that provides a guarantee)."


    Well, the entrySet() obtained for LHM does provide this guarantee. Even
    though it's not explicitly stated in comments for methods entrySet(),
    keySet() and values() because they are inherited the class level comment
    makes it clear that the ordering observed during iteration will usually
    be insertion order. I would conceded that the fact that you can also
    have access order if invoking one specific constructor is a not made
    explicit enough in the class JavaDoc.

    > The Map makes the guarantee, and one has to infer the underlying Set will therefore
    > make that guarantee, but when one copies the Map into another Map implementation,
    > even that implicit promise is removed. Furthermore, why do they not state that the Set
    > implementation iterator's order is guaranteed? It seems there's a hole in the docs.


    I think that clearly derives from the class comment because there is no
    other way to iterate a Map than through the three dependent collections
    (which usually include this comment in their accessor methods: "The
    collection is backed by the map, so changes to the map are reflected in
    the collection, and vice-versa.").

    >>> It's useful for subclasses, from what the documentation hints, but to the public?

    >>
    >> It seems you could create a LRU Map with this, right. Other uses are
    >> described in the class doc as mentioned above.

    >
    > Right, that LRU Map would be a subclass, as I said.


    And?

    Regards

    robert

    --
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
    Robert Klemme, Oct 6, 2012
    #17
  18. Jan Burse

    Jim Janney Guest

    Jan Burse <> writes:

    > Dear All,
    >
    > I just wonder whether I have overlooked something.
    > But could it be that LinkedHashMap is lacking the
    > following API:
    >
    > Map<K,V> descendingMap();
    >
    > So I can only iterate from oldest to youngest, and
    > not the other direction?
    >
    > Although under the hood it uses a double linked list,
    > and a reverse iterator would be simple.
    >
    > Also the whole matter seems to be complicated, since
    > the other collections have descendingMap() in an
    > Interface NavigableMap, which extends SortedMap.
    >
    > But SortedMap map assumes a compartor, whereby the
    > sorting in LinkedHashMap is implicit.
    >
    > Is there some shortcut to arrive at a reverse iterator
    > of LinkedHashMap?
    >
    > (Troll disclaimer: No I have no SSCCE (Short, Self
    > Contained, Correct (Compilable), Example). This is
    > a conceptual question.)
    >
    > Bye


    You haven't overlooked anything. The ability is not there and I don't
    see any simple way to add it without package access to java.util.
    LinkedHashMap is a bit of an oddity in the collections framework, but
    it's useful enough that I don't mind.

    If I really needed that functionality I'd probably try maintaining my
    own access-order list in parallel to the map.

    --
    Jim Janney
    Jim Janney, Oct 9, 2012
    #18
  19. Jan Burse

    Jim Janney Guest

    Jim Janney <> writes:

    > Jan Burse <> writes:
    >
    >> Dear All,
    >>
    >> I just wonder whether I have overlooked something.
    >> But could it be that LinkedHashMap is lacking the
    >> following API:
    >>
    >> Map<K,V> descendingMap();
    >>
    >> So I can only iterate from oldest to youngest, and
    >> not the other direction?
    >>
    >> Although under the hood it uses a double linked list,
    >> and a reverse iterator would be simple.
    >>
    >> Also the whole matter seems to be complicated, since
    >> the other collections have descendingMap() in an
    >> Interface NavigableMap, which extends SortedMap.
    >>
    >> But SortedMap map assumes a compartor, whereby the
    >> sorting in LinkedHashMap is implicit.
    >>
    >> Is there some shortcut to arrive at a reverse iterator
    >> of LinkedHashMap?
    >>
    >> (Troll disclaimer: No I have no SSCCE (Short, Self
    >> Contained, Correct (Compilable), Example). This is
    >> a conceptual question.)
    >>
    >> Bye

    >
    > You haven't overlooked anything. The ability is not there and I don't
    > see any simple way to add it without package access to java.util.
    > LinkedHashMap is a bit of an oddity in the collections framework, but
    > it's useful enough that I don't mind.
    >
    > If I really needed that functionality I'd probably try maintaining my
    > own access-order list in parallel to the map.


    Oops, stupid me. The other way is to define a comparator based on
    insertion order, and then use a SortedMap.

    --
    Jim Janney
    Jim Janney, Oct 10, 2012
    #19
  20. Jan Burse

    Eric Sosman Guest

    On 10/10/2012 11:00 AM, Jim Janney wrote:
    > Jim Janney <> writes:
    >
    >> Jan Burse <> writes:
    >> [...]
    >> If I really needed that functionality I'd probably try maintaining my
    >> own access-order list in parallel to the map.

    >
    > Oops, stupid me. The other way is to define a comparator based on
    > insertion order, and then use a SortedMap.


    Defining the comparator might be something of a struggle,
    especially if the same object instance could be referred to by
    two different LinkedHashMaps.

    --
    Eric Sosman
    d
    Eric Sosman, Oct 10, 2012
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Doug Poland
    Replies:
    9
    Views:
    722
    VisionSet
    Sep 27, 2003
  2. Andrej Litowka

    Can't read a value in a LinkedHashMap

    Andrej Litowka, Nov 20, 2003, in forum: Java
    Replies:
    1
    Views:
    2,698
    John C. Bollinger
    Nov 20, 2003
  3. Markus Innerebner
    Replies:
    1
    Views:
    581
    Markus Innerebner
    May 29, 2004
  4. Markus Innerebner

    direkt Access in a LinkedHashMap

    Markus Innerebner, Jun 28, 2004, in forum: Java
    Replies:
    3
    Views:
    552
    Michael Borgwardt
    Jun 28, 2004
  5. mutex
    Replies:
    0
    Views:
    206
    mutex
    Jul 27, 2003
Loading...

Share This Page