Multilevel map in Java [duplicate]

问题:

This question already has answers here:

Closed 7 years ago.

What is the best way in Java to keep values ("o") in a tree structure like this:

                    obj1                 
                     /\
                    /  \
                   /    \
              obj2        obj3
              /\            /\
             /  \          /  \
            /    \        /    \
          obj4  obj5    obj6   obj7
          /\     /\     /\      /\
         /  \   /  \   /  \    /  \
        o8   oN...

It looks like a tree, but I don't need arbitrary depth. I rather need strong datatyping and predefined good looking methods for working with final structure.

I need to be able to get some kind of list of values by keys - exactly like on my picture. In other words, structure should not become planar in any way.

I need .get(obj3) to return {obj6, obj7}, .get(obj1) - {obj2, obj3}.

For now I use Map for that, but inflating such map is ugly, because I need to check each level of the structure. Looks like that (data is the map):

if(data.get(somedouble) == null) {
    Map<Integer, Data> inm = new TreeMap<>();
    inm.put(someint, obj);
    Map<Double, Map<Integer, Data>> m = new TreeMap<>();
    m.put(somedouble2, inm);
    data.put(somedouble, m);
}
else {
    if(data.get(somedouble).get(somedouble2) == null) {
        Map<Integer, Data> inm = new TreeMap<>();
        inm.put(someint, obj);
        data.get(somedouble).put(somedouble2, inm);
    }
    else
        data.get(somedouble).get(somedouble2).put(someint, obj);
}

Performance in not an issue, but code beauty is.

回答1:

You can use your specific key:

class MyKey {
    Double beta;
    Double yaw;
    int minute;

    public int hashCode() {
        /* Returns hash code from a combination of hash of the key members. */
    }

    @Override
    public boolean equals(Object obj) {
        /* Returns true if obj is a MyKey with same members. */
    }
}

And then simply:

data.put(myKey, obj);

This way the "multi-level checks" are all hidden in MyKey.equals(). It keeps the client code clean and the key complexity is in a safe place.

Edit after requirement changes:

If on top of this, you want to be able to have a map from your double beta to your objects, then I would still keep the thing planar like that.

What you actually want is to have multiple "indexes" for your data, like in a database, so you can query for objects with same "beta" or "yaw". For that the best way is to use several Map (actually Multimap), one for each of your "indexes".

Using Guava's Multimap:

ListMultimap<Double, Data> mapForBeta;
ListMultimap<Double, Data> mapForYaw;

You can put all the multimap and the Map<MyKey, Data> in your a specific class. Actually the best way would be to subclass Map<MyKey, Data>:

public class MyMap extends HashMap<MyKey, Data> {

    ListMultimap<Double, Data> mapForBeta;
    ListMultimap<Double, Data> mapForYaw;


    public Data put(MyKey key, Data value) {
        super.put(key, value);
        mapForBeta.add(key.beta, value);
        mapForYaw.add(key.yaw, value);
    };

    public List<Data> getFromBeta(Double beta) {
        return mapForBeta.get(beta);
    }

    public List<Data> getFromYaw(Double yaw) {
        return mapForYaw.get(yaw);
    }
}

New Edit with better solution:

Actually, it got me thinking, and I realized that you are really having a problem with default values for your maps, and that's why your code is a bit messy.

You can solve this with a Default Map using a generator to create underlying maps:

public class DefaultMap<K, V> extends TreeMap<K, V> {

    static abstract class Generator<V>{
        abstract V create();
    }

    final Generator<V> generator;


    DefaultMap(Generator<V> generator) {
        this.generator = generator;
    }

    @Override
    public V get(Object key) {
        V val = super.get(key);
        if (val == null) {
            val = generator.create();

            put((K)key, val);
        }

        return val;
    }
}

Now you can have your utility tree class to store all your data :

public class MyTree {
  private final Map<Double, Map<Double, Map<Integer, Data>>> data;

  public MyTree() {
    data = new DefaultMap<>(new Generator<Map<Double, Map<Integer, Data>>>() {
      @Override
      Map<Double, Map<Integer, Data>> create() {
        return new DefaultMap<>(new Generator<Map<Integer, Data>>() {

          @Override
          Map<Integer, Data> create() {
            return new TreeMap<>();
          }

        });
      }
    });
  }

  void add(MyKey d, Data obj) {
    data.get(d.beta).get(d.yaw).put(d.minute, obj);
  }
}

Now you can access your data with data.get(beta).get(yaw) and you don't have spaghetti code to store your values.

回答2:

What about a binary tree?

Node.java

public class Node {

    private Node leftChild;
    private Node rightChild;

    public Node(Node leftChild, Node rightChild) {
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    public boolean isLeaf() {
        return this instanceof Leaf;
    }

}

Leaf.java

public class Leaf extends Node {

    private Data data;

    public Leaf(Data data) {
        super(null, null);
        this.data = data;
    }

}

For example, if you want to build to following tree:

         root
          /\
         /  \
        /    \
   node1     node2
   /\           /\
  /  \         /  \
leaf1 leaf2  leaf3 leaf4

Use:

Leaf leaf1 = new Leaf(new Data());
Leaf leaf2 = new Leaf(new Data());
Leaf leaf3 = new Leaf(new Data());
Leaf leaf4 = new Leaf(new Data());

Node node1 = new Node(leaf1, leaf2);
Node node2 = new Node(leaf3, leaf4);

Node root = new Node(node1, node2);