Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #27936 > unrolled thread

LinkedHashMap - get latest key?

Back to article view | Back to comp.lang.java.programmer

Contents

  LinkedHashMap - get latest key? Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-04-02 14:44 +0000
    Re: LinkedHashMap - get latest key? Jeff Higgins <jeff@invalid.invalid> - 2014-04-02 12:06 -0400
      Re: LinkedHashMap - get latest key? Jeff Higgins <jeff@invalid.invalid> - 2014-04-02 12:44 -0400
        Re: LinkedHashMap - get latest key? Jeff Higgins <jeff@invalid.invalid> - 2014-04-02 13:13 -0400
          Re: LinkedHashMap - get latest key? Jeff Higgins <jeff@invalid.invalid> - 2014-04-02 13:19 -0400
            Re: LinkedHashMap - get latest key? Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-04-02 21:58 +0000
    Re: LinkedHashMap - get latest key? Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2014-04-16 21:33 -0700
    Re: LinkedHashMap - get latest key? leif.roar@invalid.com (Leif Roar Moldskred) - 2014-04-17 03:32 -0500
      Re: LinkedHashMap - get latest key? Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-04-19 12:51 +0000
        Re: LinkedHashMap - get latest key? v_borchert@despammed.com (Volker Borchert) - 2014-04-21 20:38 +0000
          Re: LinkedHashMap - get latest key? Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> - 2014-04-25 09:18 +0000

#27936 — LinkedHashMap - get latest key?

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.

[toc] | [next] | [standalone]

#27937

On 04/02/2014 10:44 AM, Andreas Leitgeb wrote:
> 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())

[toc] | [prev] | [next] | [standalone]

#27938

On 04/02/2014 12:06 PM, Jeff Higgins wrote:
> ?
> Collections.max(myMap.entrySet())
Oops.
myMap.entrySet().toArray()

[toc] | [prev] | [next] | [standalone]

#27939

On 04/02/2014 12:44 PM, Jeff Higgins wrote:
> On 04/02/2014 12:06 PM, Jeff Higgins wrote:
>> ?
>> Collections.max(myMap.entrySet())
> Oops.
> myMap.entrySet().toArray()
Or:
<http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/map/AbstractOrderedMapDecorator.html>

[toc] | [prev] | [next] | [standalone]

#27940

On 04/02/2014 01:13 PM, Jeff Higgins wrote:
> On 04/02/2014 12:44 PM, Jeff Higgins wrote:
>> On 04/02/2014 12:06 PM, Jeff Higgins wrote:
>>> ?
>>> Collections.max(myMap.entrySet())
>> Oops.
>> myMap.entrySet().toArray()
> Or:
> <http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/map/AbstractOrderedMapDecorator.html>
>
Or:
<http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/map/LinkedMap.html>

[toc] | [prev] | [next] | [standalone]

#27941

Jeff Higgins <jeff@invalid.invalid> wrote:
> On 04/02/2014 01:13 PM, Jeff Higgins wrote:
>> On 04/02/2014 12:44 PM, Jeff Higgins wrote:
>>> On 04/02/2014 12:06 PM, Jeff Higgins wrote:
>>>> Collections.max(myMap.entrySet())

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

>>> Oops.
>>> myMap.entrySet().toArray()

is still not O(1)

>> Or:
>> <http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/map/AbstractOrderedMapDecorator.html>
> Or:
><http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/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.

[toc] | [prev] | [next] | [standalone]

#28114

In article <slrnljo8ia.rhr.avl@login.logic.tuwien.ac.at>,
 Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> wrote:

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

[toc] | [prev] | [next] | [standalone]

#28116

Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> wrote:
> 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.
>

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

If you frequently pop the most recently added element from the map,
though, this approach is useless.

public class LinkedHashMapHack<K, V> extends LinkedHashMap<K, V> {

	private K mostRecentKey;
	private V mostRecentValue;
	
	public Map.Entry<K, V> getMostRecentEntry( Object key ) {
		Map.Entry<K, V> mostRecentEntry = new AbstractMap.SimpleImmutableEntry<>( mostRecentKey, mostRecentValue );
		return mostRecentEntry;
	}
	
	@Override
	public void clear() {
		super.clear();
		mostRecentKey = null;
		mostRecentValue = null;
	}
	
	@Override
	public V put( K key, V value ) {
		V previousAtKey = super.put( key, value );
		mostRecentKey = key;
		mostRecentValue = value;
		return previousAtKey;
	}
	
	@Override 
	public V remove( Object key ) {
		V removed = super.remove( key );
		
		if( size() == 0 ) {
			mostRecentKey = null;
			mostRecentValue = null;			
		} else if( key.equals( mostRecentKey ) ) {
			findNewMostRecentKeyAndValue();
		} 
		
		return removed;
	}

	private void findNewMostRecentKeyAndValue() {
		Map.Entry<K, V> lastEntry = null;
		for( Map.Entry<K, V> entry : super.entrySet() ) {
			lastEntry = entry;
		}
		
		mostRecentKey = lastEntry.getKey();
		mostRecentValue = lastEntry.getValue();
	}
  } 

-- 
Leif Roar Moldskred

[toc] | [prev] | [next] | [standalone]

#28135

Leif Roar Moldskred <leif.roar@invalid.com> wrote:
> Andreas Leitgeb <avl@auth.logic.tuwien.ac.at> wrote:
>> 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.
> 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.

[toc] | [prev] | [next] | [standalone]

#28169

Andreas Leitgeb wrote:

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

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [next] | [standalone]

#28225

Volker Borchert <v_borchert@despammed.com> wrote:
> Andreas Leitgeb wrote:
>> 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.

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web