5

I need a data structure that provides key-value mappings, like a Map, but that also allows me to fetch the key based on an (int) index (e.g. myKey = myDS.get(index)), without having to iterate over the data structure to get the key at the desired index.

I thought of using LinkedHashMap, but I don't see a way to get the key at a given index. Am I missing something in LinkedHashMap? Or is there another data structure I can use?

EDIT:
This is not a duplicate. The correct answer to the other question is to use some sort of SortedMap; however, that is not the correct answer to this question, since I'd like to be able to retrieve an Entry from the data structure via an Integer index, which is not supported in any Java library.

Steve P.
  • 14,489
  • 8
  • 42
  • 72
Kanishka Gupta
  • 217
  • 2
  • 6
  • 17
  • 1
    Do you need any specific ordering? That is -- do you need any coherent mapping from indices to keys? – ruakh Aug 11 '13 at 03:10
  • I just need ordering to be preserve, like if i entered element element first time, it should always be available at index 0, for second element index should be 1 and so on... – Kanishka Gupta Aug 11 '13 at 03:15
  • please refer to this answer on stackoverflow http://stackoverflow.com/a/663396/611077 – Jatin Sehgal Aug 11 '13 at 03:17
  • @ruakh: My question is very different from the one you suggested. In the suggested question, that person is getting the `values` from the `list` based on index of `map`, whereas i need to get `key` from the `map` based on index and this `key` is not a list. Also, i am open for any data structure suggestion, but in suggested question workaround is asked when `map` is used... So i these two questions are very different from each other – Kanishka Gupta Aug 11 '13 at 03:20
  • 1
    @KanishkaGupta: I think you've confused me with [arknave](http://stackoverflow.com/users/1544606/arknave). All I asked is whether you need any specific ordering. – ruakh Aug 11 '13 at 03:27
  • @HovercraftFullOfEels This satisfy key-value property but when it comes to fetching key based on index of key, then i am not sure how to proceed. Could you please share information how will i find key when an integer index is given to me – Kanishka Gupta Aug 11 '13 at 03:27
  • @ruakh Ohh sorry!! that's mistake from my side and i apologize. Yes that comment was for aknave – Kanishka Gupta Aug 11 '13 at 03:30
  • Do you need to support removal? – jacobm Aug 11 '13 at 03:47
  • I need to clear the data structure, and refill it. So i think instead of using remove() of particular element i will be needing to clear() or i will make myDS = null; – Kanishka Gupta Aug 11 '13 at 03:50
  • @KanishkaGupta My answer should eliminate your confusion **and** provide you with the required data structure. – Steve P. Aug 11 '13 at 04:36

5 Answers5

6

LinkedHashMap provides a hash table/doubly linked list implementation of the Map interface. Since it extends HashMap, it's still backed by an array, but there is also a doubly-linked list of Entry objects to ensure that the iteration order is predictable.

So, basically what it means is that when you iterate through the map like so:

for (Map.Entry<keyType,valueType>> entry : linkedHashMap.entrySet())
{
   System.out.println("Key: " + entry.getKey().toString() + 
                     " Value: " + entry.getValue.toString());
}

it will print in the order that you added the keys, as opposed to a non-linked Map, which will not print in insertion order. You cannot access the elements of the array like you want to, because the array that backs the hash is not in order. Only the doubly linked list is ordered.

Solution:

What you are looking for is a LinkedMap from Apache Commons.

Community
  • 1
  • 1
Steve P.
  • 14,489
  • 8
  • 42
  • 72
  • @Neel Yes, it's a cool data structure. Not really sure why Java doesn't have something comparable. – Steve P. Aug 11 '13 at 04:43
  • Only 2 questions come to my mind: 1. What if I am not allowed to use a third party library like the commons API's? 2. Why do I need a single data structure to do both to begin with? – Neel Aug 11 '13 at 04:44
  • Probably because Java does not want to clutter ts util API's to accommodate every use case possible while it actually provides for few of the most fundamental ones :) – Neel Aug 11 '13 at 04:45
  • @Neel Yeah, that's probably true...(1) You could write your own, that's what my roommate had to do for a project that he was working on. (2) Is a much more complicated answer. This isn't what you're looking for, but basically if you want to be able to reap the benefits of a `HashMap`, while also reaping the benefits of an array. The reason he needed it was very complex. Off the top of my head, I can't think of a simple reason, but I'm sure many exist. Sorry for the crappy (2) answer. – Steve P. Aug 11 '13 at 04:47
2

AFAIK, there is no single data structure that will do this. There is certainly not one in the standard Java collection suite.

Also LinkedHashMap is not the solution because you cannot efficiently index a LinkedHashMap.

If you want to do index-based lookup as well as keep-based lookup, solution needs to be a combination of two data structures.

  • A Map<Key, Value> and an ArrayList<Value> is the simpler approach, but it has a couple of problems: - Insertion and deletion of values from the ArrayList is expensive, unless you are inserting / deleting at the tail end of the list. - Insertion and deletion makes the list positions unstable,.

  • If you want stable indexes and scalable insertion and deletion, then you need a Map<Key, Value> and a Map<Integer, Value> ... and a way to manage (i.e. recycle) the index values.

The Apache Commons LinkedMap class is a possible solution, except that it suffers from the problem that index values are not stable in the face of insertions and deletions.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • There is in the Apache Commons library, see my answer. No java library exists to my knowledge, though. Interesting idea with the two `Maps`. – Steve P. Aug 11 '13 at 04:49
  • Based on the [source](http://grepcode.com/file/repo1.maven.org/maven2/commons-collections/commons-collections/3.2.1/org/apache/commons/collections/map/AbstractLinkedMap.java#AbstractLinkedMap.addEntry%28org.apache.commons.collections.map.AbstractHashedMap.HashEntry%2Cint%29), I don't see why the index values are not stable in the face of insertions and deletions. Could you please explain? – Steve P. Aug 11 '13 at 06:13
1

How about using:

Map<String, String> map = new LinkedHashMap<String, String>();
List<Entry<String, String>> mapAsList = new ArrayList<Map.Entry<String,String>>(map.entrySet());

 mapAsList.get(index);
rocketboy
  • 9,573
  • 2
  • 34
  • 36
  • I am not sure how it will work. It seems bit complex, but i will need to check what Entry<> actually does. – Kanishka Gupta Aug 11 '13 at 03:32
  • An [Entry](http://docs.oracle.com/javase/7/docs/api/java/util/Map.Entry.html) is a composition of – rocketboy Aug 11 '13 at 03:40
  • I think get() expects the `key` and i am unable to get point how can i make `key` work as `index` for map and how List data structure here is helping me, since i am operating on calling get() on map and not operating on List – Kanishka Gupta Aug 11 '13 at 03:45
  • @KanishkaGupta See my answer, it may help to solve your confusion. – Steve P. Aug 11 '13 at 04:31
0

I do not believe there is a collection for this; collections are either based on the idea that you want to know exactly where an element is (lists) or that you want quick access based on some key or criteria (maps); doing both would be very resource-intensive to maintain.

Of course, you can make something like this, as rocketboy's answer suggests, but I'm guessing it's not really possible to make efficient.

Marconius
  • 683
  • 1
  • 5
  • 13
0

There is no direct DS in the standard Java Collections API to provide a indexed map. However, the following should let you achieve the result:

// An ordered map
Map<K, V> map = new LinkedHashMap<K, V>();
// To create indexed list, copy the references into an ArrayList (backed by an array)
List<Entry<K, V>> indexedList = new ArrayList<Map.Entry<K, V>>(map.entrySet());
// Get the i'th term
<Map.Entry<K,V>> entry = indexedList.get(index);
K key = entry.getKey();
V value = entry.getValue();

You might still want to retain the concerns of data persistence in the map separate from the retrieval.

Update: Or use LinkedMap from Apache Commons as suggested by Steve.

Neel
  • 2,100
  • 5
  • 24
  • 47