Maplike data structure

Question

Is there a map like data structure with integer as key , string as value, which ends up to be sorted by key no matter on insertion order like when you insert first item {4, somevalue} that it will be on the fourth place when you use it in further application flow

Fourth place? Could you explain that? 4th place if you insert 3 more items with keys lower then 4 ? Or always 4th place? Even if you don't insert anything? What would then be on the first place ? — Ivan, Jul 23 '10 at 09:47

andrewmu · Answer 1 · 2010-07-23T10:16:08.133

4

It sounds like you are looking for java.util.TreeMap<Integer, String>. It orders the entries based on the key.

edited Jul 23 '10 at 10:16

answered Jul 23 '10 at 09:45

andrewmu

14,276
4
39
37

2

I wouldn't says by "hash key", as that could be interpreted that the order depends on the `hashCode()` return value. It orders base on the key. – Joachim Sauer Jul 23 '10 at 09:50
2

It's based on the key's natural ordering, or alternatively, a supplied Comparator. – Gunslinger47 Jul 23 '10 at 10:16

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

The interface SortedMap<K,V> defines a type that has the behavior you're looking for:

A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods).

A particular implementation of a SortedMap that may be of interest is a TreeMap:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

Note that interface NavigableMap<K,V> extends SortedMap<K,V>. That is, a NavigableMap is a SortedMap, but it also specifies additional methods, e.g. all-inclusive bounds subMap. If you don't need these additional functionarlities, simply a SortedMap should work just fine.

Example

This shows basic usage of NavigableSet<K,V>:

    NavigableMap<Integer,String> nmap =
        new TreeMap<Integer,String>();
    
    nmap.put(3, "Three");
    nmap.put(1, "One");
    nmap.put(4, "Four");
    nmap.put(5, "Five");
    nmap.put(7, "Seven");
    
    System.out.println(nmap);
    // {1=One, 3=Three, 4=Four, 5=Five, 7=Seven}

    System.out.println(nmap.firstKey()); // 1
    System.out.println(nmap.lastEntry().getValue()); // Seven
    System.out.println(nmap.higherKey(1)); // 3 
    System.out.println(nmap.lowerEntry(6).getValue()); // Five

    NavigableMap<Integer,String> sub = nmap.subMap(2, true, 5, true);
    for (Map.Entry<Integer,String> entry : sub.entrySet()) {
        System.out.printf("%s => %s%n",
            entry.getKey(),
            entry.getValue()
        );
    }
    // 3 => Three
    // 4 => Four
    // 5 => Five

Maplike data structure

2 Answers2

See also

Example

Related questions