Java Random access Map

I'm looking for a opensource library that has an implementation of a random access map. I need a map that maintains its hash index but also indexes the values in insertion order like LinkedHashmap except you don't have to iterate through it to find eg. element 2. Something like this:

Map m = new ArrayMap();
m.put("0", "v0");
m.put("1", "v1");
m.put("2", "v2");
m.put("3", "v3");

assertEquals("v2", m.get("2"));
assertEquals("v2", m.getAtIndex(2));

The idea is that both types of lookups must be fast.

A quick google didn't find anything, I didn't see it in Guava or commons collections (I may开发者_开发百科 have overlooked it). I don't really have the time to implement it properly right now.

If your Map can be immutable, you can do this:

ImmutableMap<String, String> map = ...
String v2 = map.entrySet().asList().get(2).getValue();

asList() on the entrySet() for a regular ImmutableMap just uses the map's own array of entries directly, so it's random access and fast.

If your map is static or if it's just updated ocasionally you could use the values() method of the LinkedHashMap which provides the list of values of the map as a Collection<T>. Then you can convert the set to an array with toArray(T[] a) and you will have constant access to the elements, of course this will waste some memory to store the additional references but you are asking two specific good complexities so a memory trade-off is necessary. This will be fine if you don't need to get values while you add them in a mixed way.

The only different way would be to implement a LinkedHashMap by yourself by using an array instead that a linked list to store insertion order, but you will have to care about doubling the capacity of the arraylist when needed to keep performance enough fine.

You want to look up values two different ways. The simplest/fastest way to do this is to maintain two collections, one Map and one ArrayList.

private final Map<String, String> map;
private final List<String> list;

public void put(String key, String value) {
   map.put(key,value);
   list.add(value);
}

public String get(String key) {
   return map.get(key);
}

public String get(int index) {
   return list.get(index);
}

I think that LinkedHashMap is exactly what you need.

You can use it as map:

map.get("v2");

and as list:

new ArrayList(map.values().values()).get(2);

If you want to can write your own 5 lines long class that implements this logic.