How to get nth item from a TreeMap?

Question

I have a TreeMap<Date, Integer> and I want to fetch the nth item from that map. What I came up with now is this:

((Integer)myTreeMap.values().toArray()[index]).intValue();

but this feels quite clunky, not to mention what is happening on the heap or with performance?

Is there a concise way to get the nth item from a TreeMap/SortedMap ?

Maymaya

Why not use a stream on the treemap-values and skip n-1 elements and get the first of the rest? – Mitis

Unless you have a custom implementation, iterating is the only way to know which leaf node is the 'nth'. – Exclude

The default TreeMap implementation does not support that. It uses an internal java.util.TreeMap.Values type to keep the values that does not add support for index-based access. Similarly for the key Set. They do make it easy though to get values for keys above/below thresholds, maybe you can try to use that instead of n-th value? – Vet

Answer 1

Edit: an alternative is

final Optional<T> first =
        treeMap.values()
               .stream()
               .skip(index - 1)
               .findFirst();

if (first.isPresent()) {
    final T value = first.get();
}

What about

final List<T> values = new ArrayList<>(myTreeMap.values());
final T value = values.get(index);

T is just a generic type in place of your Map value type.
index is your nth element.

As pointed out, that's inefficient for large maps, as internally the ArrayList constructor the toArray method is called

public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

Oogenesis

This is very inefficient if the map is large... you instantiate a full list of all values just to get a single value that could be really close to the "head". – Vet

@Vet the same is valid for the Stream version, using Collect.toList, I think. – Oogenesis

Not at all. The stream version does not require collect over the full collection (it does not even require collect, that answer needs improvements). – Vet

@Vet Yeah, but you have to use findFirst after skipping. Using Collectors.toList you need the full list. – Oogenesis

Answer 2

We can try using a stream here. In the snippet below, we create a sorted map with five entries. Then, we create a stream, skipping the first 3 elements, and using findFirst to capture the first element.

Map<Integer, String> myTreeMap = new TreeMap<>();
myTreeMap.put(1, "one");
myTreeMap.put(2, "two");
myTreeMap.put(3, "three");
myTreeMap.put(4, "four");
myTreeMap.put(5, "five");
String fourth = myTreeMap.entrySet().stream()
   .skip(3)
   .map(map -> map.getValue()).findFirst().get();
System.out.println("fourth value in map is: " + fourth);

Partake

Why stream over the entryset when you could use the values and only need them? – Mitis

Just do treeMap.values().stream().skip(5).findFirst().orElse(-1) – Vet

@Mitis the map probably internally maintains its data as Entrys; calling values() would force it to first fully resolve those to create that collection. So it depends on the implementation, but chances are higher that this is more efficient. – Dunston

@Dunston no, I checked, both calls "getFirstEntry()", and both use an Iterator starting from there – Oogenesis

Answer 3

You can use steam and skip n-1 elements and take the first as below: tmap.entrySet().stream().skip(n-1).findFirst();. Details with data set examples:

TreeMap<Date, Integer> tmap = new TreeMap<Date, Integer>();
tmap.put(new Date(2014, 1, 1), 0);
tmap.put(new Date(2015, 1, 1), 1);
tmap.put(new Date(2016, 1, 1), 2);
tmap.put(new Date(2017, 1, 1), 3);
tmap.put(new Date(2018, 1,1 ), 4);

System.out.println(tmap);

// Let's find the nth elements i.e n = 3;
int n = 3;
System.out.println(" " + n + " elements: ");
System.out.println(tmap.entrySet().stream().skip(n-1).findFirst());

Output as follow:

{Sun Feb 01 00:00:00 IST 3914=0, Mon Feb 01 00:00:00 IST 3915=1, Tue Feb 01 00:00:00 IST 3916=2, Thu Feb 01 00:00:00 IST 3917=3, Fri Feb 01 00:00:00 IST 3918=4}
3 elements: 
Optional[Tue Feb 01 00:00:00 IST 3916=2]

Neoptolemus

Answer 4

I have found a way of getting the Nth key / value from a Map. and that is simply to add a counter.

int count = 1;
for (Map.Entry entry : Map.entrySet())
        {
            if (count == 1) //the Nth value
            {
                System.out.println(count + " "
                     + entry.getKey() + " "
                     + entry.getValue());
            }
            count++;
        }

Centigram