LinkedHashMap - get latest key?

[Andreas Leitgeb]

Given a LinkedHashMap instance, what would be a
reasonable way to obtain the latest added key?

The specific definition of "reasonable" being:
- no separate keeping track of key-sequence
- it should be a O(1) operation, and not
have to iterate all keys.

Unlike TreeMap, the LinkedHashMap doesn't implement
NavigableMap.

If nothing else helps, I'll need to switch to a LinkedList,
and thereby sell the "O(1)" of searching for an Object (by
key) in exchange for a "O(1)" of obtaining the last Object.

It just seems odd to me, that a LinkedHashMap doesn't
have such a nobrainer getter, or, that a LinkedHashMap
isn't also a NavigableMap with the natural ordering
induced by position.

 

[Jeff Higgins]

Given a LinkedHashMap instance, what would be a
reasonable way to obtain the latest added key?

The specific definition of "reasonable" being:
- no separate keeping track of key-sequence
- it should be a O(1) operation, and not
have to iterate all keys.

Unlike TreeMap, the LinkedHashMap doesn't implement
NavigableMap.

If nothing else helps, I'll need to switch to a LinkedList,
and thereby sell the "O(1)" of searching for an Object (by
key) in exchange for a "O(1)" of obtaining the last Object.

It just seems odd to me, that a LinkedHashMap doesn't
have such a nobrainer getter, or, that a LinkedHashMap
isn't also a NavigableMap with the natural ordering
induced by position.

?
Collections.max(myMap.entrySet())

 

[Jeff Higgins]

?
Collections.max(myMap.entrySet())

Oops.
myMap.entrySet().toArray()

 

[Jeff Higgins]

Oops.
myMap.entrySet().toArray()

Or:
<http://commons.apache.org/proper/co...ections4/map/AbstractOrderedMapDecorator.html>

 

[Jeff Higgins]

Or:
<http://commons.apache.org/proper/co...ections4/map/AbstractOrderedMapDecorator.html>

Or:
<http://commons.apache.org/proper/co...pache/commons/collections4/map/LinkedMap.html>

 

[Andreas Leitgeb]

The items in my case have no ordering. Only "order" is insertion order.
Also, it's not O(1)

is still not O(1)

Or:
<http://commons.apache.org/proper/co...pache/commons/collections4/map/LinkedMap.html>

It's not the first time I see some (imho)shameful omission of JSL "fixed"
in some commons.apache.org class. In my case, however, I now just give up
the Hashing and use LinkedList instead. Searching for an item happens rarely
enough in my case to not be worth pulling in another library-dependency.

Thanks still for the pointer; If performance of searching was relevant,
then I'd gladly use apache's LinkedMap.

 

[Kevin McMurtrie]

Given a LinkedHashMap instance, what would be a
reasonable way to obtain the latest added key?

The specific definition of "reasonable" being:
- no separate keeping track of key-sequence
- it should be a O(1) operation, and not
have to iterate all keys.

Unlike TreeMap, the LinkedHashMap doesn't implement
NavigableMap.

If nothing else helps, I'll need to switch to a LinkedList,
and thereby sell the "O(1)" of searching for an Object (by
key) in exchange for a "O(1)" of obtaining the last Object.

It just seems odd to me, that a LinkedHashMap doesn't
have such a nobrainer getter, or, that a LinkedHashMap
isn't also a NavigableMap with the natural ordering
induced by position.

You can look at the LinkedHashMap source code and see that it only
tracks the head of the map. The methods you'd override to fix that are
package scope. It can't quickly return the last element.

LinkedHashMap serves only three uses:

1) De-dupe or index ordered key-value pairs
2) Find oldest item for LRU or FIFO caching
3) Constant time per element iteration

Fortunately, hash maps aren't rocket science. You can write your own or
download one. AbstractMap can help.

 

[Andreas Leitgeb]

If you don't have to remove objects from the map, or you can live with
remove being O( n ) when it's the latest added element that's removed,
you can just subclass LinkedHashMap like below. (Warning: the code
hasn't been tested, just written. Caveat emptor.)

Most of the operations (add,remove,find&raise) on that structure will
be dwarfed by other stuff happening alongside, except for "accessing
the top-object", for which ideally no CPU-cycle should be wasted at all.

Based on this requirement, I already dumped the Hashing. Size "n"
is not very large in my case (probably below 10 most of the times),
and linearly searching an element (typically to raise it to top) just
doesn't matter here. The same short linear search for the last element,
however, did matter.

Thanks anyway for your code contribution. It would have solved my
problem, but my code (without hashing) became simpler, which is
now even preferrable to search-speed for me.

 

[Volker Borchert]

Based on this requirement, I already dumped the Hashing. Size "n"
is not very large in my case (probably below 10 most of the times),

I got bitten by that same "most of the times". In some - rare but not
sufficiently so - cases on the production system, n did grow to nearly
10000, causing linear search to bring the whole application to a crawl.

 

[Andreas Leitgeb]

I got bitten by that same "most of the times". In some - rare but not
sufficiently so - cases on the production system, n did grow to nearly
10000, causing linear search to bring the whole application to a crawl.

Thanks for the warning, but in my case, that "n" is bounded.

It isn't that but it is essentially as if it were bounded by
enum sizes. Theoretically there could be an enum of 10000
elements, but that just doesn't ever happen