Glitch in Java Collections (No descendingMap in LinkedHashMap)

[Jan Burse]

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

 

[Robert Klemme]

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

 

[Lew]

It's also lacking 'ascendingMap()'

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).


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


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?

 

[Jan Burse]

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

 

[Robert Klemme]

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

 

[Lew]

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.

Why would they need to?

If the ordered state is not observable, what difference does it 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.

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 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.

 

[Jan Burse]

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(); }

 

[Daniel Pitts]

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.

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.

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

Iteration is how you reveal the order.

 

[Lew]

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.

 

[Jan Burse]

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]

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]

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

 

[Daniel Pitts]

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.

 

[glen herrmannsfeldt]

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

 

[Jan Burse]

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]

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

 

[Robert Klemme]

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.

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.").

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

And?

Regards

robert

 

[Jim Janney]

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]

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.

 

[Eric Sosman]

[...]
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.