What's an efficient way to store data, access it with keys and iterate a subpart of it based on the values?

Question

I have a collection of class storing some data on which I need to do the following:

access the data quite frequently with some unique id
access the data of a subpart of the collection based on the non-unique, ordered value of an attribute of the class

Can you think of any efficient way to do that in Java?

First, I thought of using a HashMap with ids as keys

a HashMap is O(1) to get the data from the key;
it can be sorted on values but it is inefficient when you want to get to a specific value (the whole collection gets iterated);

Then, I thought of using a TreeMap, with ordered values as keys

a TreeMap allows an efficient iteration over the ordered values;
the ordered values aren't unique so it should be a TreeMultimap;
but getting a value from its id will be O(log(n));

Using the two structures simultaneously doesn't seem like a good solution either as they would have to be synchronized. I guess some kind of BiMultiMap sorted on its values with a way to iterate on it starting from a specific value would solve my problem but I can't find a way to do that.

I have tried to craft an example to illustrate my needs. This train thing is not my actual problem, I've tried to make it a little bit less abstract.

public static class Train implements Comparable<Train> {
    String id;
    int maxSpeed;
    String trainColor;

    public Train(String id, int d1, String d2){
        this.id = id;
        this.maxSpeed = d1;
        this.trainColor = d2;
    }

    @Override
    public String toString() {
        return id + " = (" + maxSpeed + ", " + trainColor + ")";
    }

    @Override 
    public int compareTo(Train o) {
        return Integer.compare(this.maxSpeed, o.maxSpeed);
    }
}

public static void main(String[] args){
    // Let's say I need two things:
    //   - the trains that can go higher than a certain speed
    //   - the train data of a particular train
    int start = 3;
    String seekedId = "FlyingScotman";

    Train d1 = new Train("HogwartExpress", 5, "blue");
    Train d2 = new Train("TGV", 4, "red");
    Train d3 = new Train("FlyingScotman", 3, "blue");
    Train d4 = new Train("OrientExpress", 2, "black");
    Train d5 = new Train("Trans-Siberian", 1, "grey");

    /******* HashMap implementation *******/

    Map<String, Train> hashMapData = new HashMap<String, Train>();
    hashMapData.put(d1.id, d1);
    hashMapData.put(d2.id, d2);
    hashMapData.put(d3.id, d3);
    hashMapData.put(d4.id, d4);
    hashMapData.put(d5.id, d5);
    hashMapData = MapUtil.sortByValue(hashMapData);

    // Bad: I have to iterate the whole collection to reach the subcollection
    System.out.println("\n>>>>>>> HashMap: subcollection");
    for(Map.Entry<String, Train> entry : hashMapData.entrySet()) {
        if (entry.getValue().maxSpeed < start) {
            continue;
        }
        System.out.println(entry.getValue());
    }

    // Good: I get my data directly
    System.out.println("\n>>>>>>> HashMap: get");
    System.out.println(hashMapData.get(seekedId));

    /******* TreeMap implementation *******/

    TreeMap<Integer, Train> treeMapData = new TreeMap<Integer, Train>();
    treeMapData.put(d1.maxSpeed, d1);
    treeMapData.put(d2.maxSpeed, d2);
    treeMapData.put(d3.maxSpeed, d3);
    treeMapData.put(d4.maxSpeed, d4);
    treeMapData.put(d5.maxSpeed, d5);

    // Good: I can iterate a subcollection efficiently
    System.out.println(">>>>>>> TreeMap: subcollection");
    for(Map.Entry<Integer, Train> entry : treeMapData.tailMap(start).entrySet()) {
        System.out.println(entry.getValue());
    }

    System.out.println("\n>>>>>>> TreeMap: get");
    // Bad: I have to iterate the whole collection to reach the data
    for(Map.Entry<Integer, Train> entry: treeMapData.entrySet()) {
        if (entry.getValue().id.equals(seekedId)) {
            System.out.println(entry.getValue());
        }
    }

    // Also bad: the values used as keys might not be unique

}

Output

>>>>>>> TreeMap: subcollection
FlyingScotman = (3, blue)
TGV = (4, red)
HogwartExpress = (5, blue)

>>>>>>> TreeMap: get
FlyingScotman = (3, blue)

>>>>>>> HashMap: subcollection
FlyingScotman = (3, blue)
TGV = (4, red)
HogwartExpress = (5, blue)

>>>>>>> HashMap: get
FlyingScotman = (3, blue)

The MapUtil.sortByValue method is courtesy of Carter Page : Sort a Map<Key, Value> by values (Java)

Thanks in advance, please tell me if anything wasn't clear.

I meant how to store it locally, accessing a database everytime I need something wouldn't make it faster, would it...? — 7hibault, Mar 06 '15 at 09:44
You need multiple maps, http://stackoverflow.com/questions/822322/how-to-implement-a-map-with-multiple-keys . If you have non unique keys look at guava Multimap and TreeMultimap. But as suggested ealier a mem db is very convenient and pretty fast. — nomoa, Mar 09 '15 at 11:25

score 0 · Answer 1 · answered Mar 10 '15 at 05:00

You can make wrapper-class for HashMap implementing Map and add a sorted set to store values. Guava TreeMultiset should be good as it allows elements with same order.

It will look like index in database. You will get faster read operations at the cost of slower modifications.

public class MyMap<K, V extends Comparable<V>> implements Map<K, V> {
  private HashMap<K, V> hashMap = new HashMap<K, V>();
  private TreeMultiset<V> treeMultiset = TreeMultiset.create();

  // delegate all Map methods to hashMap
  // delegate subset methods to treeMultiset
  // all mutators should make corresponding modifications to treeMultiset
}

What's an efficient way to store data, access it with keys and iterate a subpart of it based on the values?

1 Answers1