How to get position of key/value in LinkedHashMap using its key

Question

I have a LinkedHashMap (called info) that contains name/age (string/int) pairs. How can I get the position of the key/value if I input the key? For example, if my LinkedHashMap looked like this {bob=12, jeremy=42, carly=21} and I was to search jeremy, it should return 1 as its in position 1. I was hoping I can use something like info.getIndex("jeremy").

Answer 1

HashMap implementations in general are un-ordered for Iteration.

LinkedHashMap is predictablely ordered for Iteration ( insertion order ) but does not expose the List interface and a LinkedList ( which is what mirrors the key set insertion order ) does not track index position itself either, it is very in-efficient to find the index as well. The LinkedHashMap doesn't expose the reference to the internal LinkedList either.

The actual "Linked List" behavior is implementation specific. Some may actually use an instance of LinkedList some many just have Entry track a previous and next Entry and use that as its implementation. Don't assume anything without looking at the source.

The KeySet that contains the keys does not guarantee order as well because of the hashing algorithms used for placement in the backing data structure of the inherited HashMap. So you can't use that.

The only way to do this, without writing your own implementation, is to walk the Iterator which uses the mirroring LinkedList and keep a count where you are, this will be very in-efficient with large data sets.

Solution

What it sounds like you want is original insertion order index positions, you would have to mirror the keys in the KeySet in something like an ArrayList, keep it in sync with updates to the HashMap and use it for finding position. Creating a sub-class of HashMap, say IndexedHashMap and adding this ArrayList internally and adding a .getKeyIndex(<K> key) that delegates to the internal ArrayList .indexOf() is probably the best way to go about this.

This is what LinkedHashMap does but with a LinkedList mirroring the KeySet instead of an ArrayList.

Answer 2

int pos = new ArrayList<String>(info.keySet()).indexOf("jeremy")

Answer 3

I saw a suggestion from one of the duplicates of this question at

How get value from LinkedHashMap based on index not on key?

and I liked the suggestion as described as pseudo code from @schippi in the comments. I thought some working Java code might be useful to others on this approach

import java.util.ArrayList;
import java.util.LinkedHashMap;

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

    /**
     * 
     */
    private static final long serialVersionUID = 1L;

    ArrayList<K> al_Index = new ArrayList<K>();

    @Override
    public V put(K key,V val) {
        if (!super.containsKey(key)) al_Index.add(key);
        V returnValue = super.put(key,val);
        return returnValue;
    }

    public V getValueAtIndex(int i){
        return (V) super.get(al_Index.get(i));
    }

    public K getKeyAtIndex(int i) {
        return (K) al_Index.get(i);
    }

    public int getIndexOf(K key) {
        return al_Index.indexOf(key);
    }

}

Answer 4

Considering that LinkedHashMap keep the order of insertion, you can use the keySet() and List.copyOf() (since Java 10) methods like this:

List<String> keys = List.copyOf( yourLinkedHashMap.keySet() );

System.out.println( keys.indexOf("jeremy") ); // prints '1'

Answer 5

LinkedHashMap has "predictable iteration order" (javadoc). Items don't know their location, though, so you'll have to iterate the collection to get it. If you're maintaining a large map you may want to use a different structure for storage.

Edit: clarified iteration

Answer 6

You can use com.google.common.collect.LinkedListMultimap from the Google Guava library. You don't need the multimap behaviour of this class what you want is that the keys() method guarantees they are returned in insertion order and can then be used to construct a List, you can use the indexOf() to find the required index position

Answer 7

I do extract the positons of the key into a concurent map like this:

Here for a Map, someListOfComplexObject() would be entrySet() and getComplexStringKeyElem() would be getKey()

might come from

 final int[] index = {0};
 Stream<ComplexObject> t = someListOfComplexObject.stream();
 ConcurrentMap<String, List<Integer>> m = 
      t.collect(Collectors.groupingBy(
           e -> e.getComplexStringKeyElem(),
           Collectors.mapping(
                e -> index[0]++,
                Collectors.toList()
           ),
           ConcurrentSkipListMap::new));