1
\$\begingroup\$

I am building some statistic counter in Java. Each metric could have flexible depth so the implementation should able to explore the depth when value insert or update.

So I implement like below (with Test)

public class TestRecursiveMap {

    private void recursiveRegister(Map<String, Object> target, String[] keys, int curr) {
        if(curr > keys.length -1) return;
        String currKey = keys[curr];
        if(target.containsKey(currKey)) {
            Object currVal = target.get(currKey);
            if(curr >= keys.length -1) {
                int value = (int) currVal;
                target.put(currKey, value + 1);
            } else {
                Map<String, Object> subMap = (Map<String, Object>)currVal;
                recursiveRegister(subMap, keys, curr + 1);
            }
        } else {
            if(curr >= keys.length -1) {
                target.put(currKey, 1);
            } else {
                Map<String, Object> emptyMap = new HashMap<>();
                target.put(currKey, emptyMap);
                recursiveRegister(emptyMap, keys, curr + 1);
            }
        }
    }

    // result looks like
    // {a={b={c=1}}}
    // {a={b={c=2}}}
    @Test
    public void testRecursive(){
        Map<String, Object> originMap = new HashMap<>();
        String[] keys = {"a", "b", "c"};
        recursiveRegister(originMap, keys, 0);
        System.out.println(originMap);
        recursiveRegister(originMap, keys, 0);
        System.out.println(originMap);
    }
}

The code is so unsatisfied because of

  • casting in recursive logic - Map<String, Object> is very flexible but need to cast object to map or integer in every level

  • while casting there are bunch of possibilities of exceptions

How could I implement this safe and fast?

=====================================

Use case #1.

Actually this is an api counter. When you have an API call, it will counting the mount of the request.

For instance,

/api/user/1 and /api/v1/user/1 then it will have some value like below (in JSON form)

{
    "api" : {
        "user" : {
            "1" : 1
        },
        "v1" : {
            "user" : {
                "1" : 1
            }
        }
    }

}

So the basic logic is

  • if there is a key in the map, it will increase the number
  • if not, it will assign new k,v set and the initial value is 1
\$\endgroup\$
1
  • \$\begingroup\$ This looks more like a file/directory hierarch (Map<Path, Object>?) And a well known design pattern exists (Container). But show us the desired API in some unit tests, how to store, how to query. Does get("a") return a list of either values or "b" pointing to further subhierarchies. If we know the API we'll can start searching for a fitting data structure. \$\endgroup\$ – Joop Eggen Dec 18 '20 at 14:15
1
\$\begingroup\$
if(curr > keys.length -1) return;

// ... 

Object currVal = target.get(currKey);

Don't shorten variable names just because you can. It makes the code harder to read and harder to maintain.


if(curr > keys.length -1) return;

Ideally you're always use a "full block if" for statements, as it makes it easier to see the return condition.

if (curr > keys.length - 1) {
    return;
}

Also, your formatting seems to be off in a few cases. I'd suggest to always use an automatic formatter in your workflow so that you never need to worry about the formatting of your code ever again.


target.put(currKey, 1);

int and Integer are requiring conversion between each other, that's called "boxing" and might or might not be a problem when doing it implicit.


You ain't got any sort of error handling, if I see this right.


So, let's get to the design. If I understand your example right, what you want to do is to have a list of keys, which represent the path through the tree structure, and the last key keeps a counter how often it was added.

There are several ways to achieve that, and the question is what exactly you're trying to achieve to know which one applies.

For every further implementation, we'll assume the following interface:

public class CounterTreeMap {
    public int getValue(String... keys);
    public void putValue(String... keys);
}

You notice that we've already simplified how to use this class, the rest are implementation details. Additionally, I'll skip tests on the input parameters for brevity.

The cheap one

The cheapest solution is to "fake" depth by hashing the input array and having a single Map. However, this implementation would be able to store a value for the path "A, B" as well as for "A, B, C".

protected Map<Integer, Integer> values = new HashMap<>();

public int getValue(String... keys) {
    int keysHash = Arrays.hashCode(keys);
    // TODO We are missing logic here to handle possible hash collisions.
    Integer value = values.get(Integer.valueOf(keysHash));
    
    if (value != null) {
        return value.intValue();
    } else {
        return -1; // Or throw exception here.
    }
}

The nearly as cheap one

Given the problems from the previous implementation, we can fix at least the possible has collisions by using the full path as key instead.

protected Map<String, Integer> values = new HashMap<>();

public int getValue(String... keys) {
    String key = String.join("/", keys);
    Integer value = values.get(Integer.valueOf(key));
    
    if (value != null) {
        return value.intValue();
    } else {
        return -1; // Or throw exception here.
    }
}

Now that solves the possible hash collisions, but still allows us to store values at each node, basically. That might even be wanted, I don't know, you never specified.

The one with the many maps

As you've done, we can build a hierarchy of Maps, however, I'd base decisions on the type of the encountered leaf.

Recursive implementation:

protected Map<String, Object> tree = new HashMap<>();

public int getValue(String... keys) {
    return getValue(tree, keys, 0);
}

protected int getValue(Map<String, Object> branch, String[] keys, int currentKeyIndex) {
    String key = keys[currentKeyIndex];
    Object value = branch.get(key);
    
    if (value == null) {
        return -1; // Or throw an exception here.
    } else if (value instanceof Integer) {
        return ((Integer)value).intValue();
    } else if (value instanceof Map<?, ?>) {
        return getValue((Map<String, Object)value, keys, currentKeyIndex + 1)
    }
}

Implementation using a loop instead:

protected Map<String, Object> tree = new HashMap<>();

public int getValue(String... keys) {
    Map<String, Object> branch = tree;
    int currentKeyIndex = 0;
    
    while (branch != null) {
        String key = keys[currentKeyIndex];
        Object value = branch.get(key);
        
        if (value == null) {
            return -1; // Or throw an exception here.
        } else if (value instanceof Integer) {
            return ((Integer)value).intValue();
        } else if (value instanceof Map<?, ?>) {
            branch = (Map<String, Object)value;
            currentKeyIndex++;
        }
    }
}

Both implementations lack proper checks, though, but you should get the idea.


Given the use case as example, I'd go with flattening/joining the path into a single string (using "/" as separator) and, when adding a new path, increasing the existing value or setting a new one if it does not exist.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks Bobby. The hashing key method looks nice for me. However what do you think about return -1; // Or throw an exception here. statement in the last code block? (which is my most concern). Basically Object is a super class of whole class that statement is compilable but I think it is not safe enough. I would like to know your opinion about that. (I added use case on OP) \$\endgroup\$ – Juneyoung Oh Dec 20 '20 at 23:32
  • \$\begingroup\$ I'd go with flattening/joining the path into a single string (using "/" as separator) and, when adding a new path, increasing the existing value or setting a new one if it does not exist. Regarding error handling, the question is what you want to do when trying to get the information on non-existing path, "0" would most likely be appropriate. Also, you most likely need a method which returns the whole Map. \$\endgroup\$ – Bobby Dec 21 '20 at 17:51
1
\$\begingroup\$

It took a long time just to understand what your program is doing and how it might be useful.

You were concerned about the unchecked casting, and that's a valid concern, but maybe it's not a problem if you make that behaviour clear, for instance, by including a failure scenario in the test case or JavaDoc, in which case you are just stating it's the responsibility of the other code that makes use of this to only pass valid arguments.

Here's a version of the same thing that's hopefully a bit better at describing what it does. With things a bit more plain to read, you can decide if you want your program to behave differently in the failure case -- maybe it should throw a checked exception instead of ClassCastException or maybe you want to actually support these cases?

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/**
 * I am building some statistic counter in Java. Each metric could have flexible
 * depth so the implementation should able to explore the depth when value
 * insert or update.
 *
 */
public class StatisticsCounter {

    private Map<String, Object> rootMap = new HashMap<>();

    public void increment(String... paths) {
        recursiveIncrement(rootMap, paths, 0);
    }

    private void recursiveIncrement(Map<String, Object> targetMap, String[] pathToTarget,
            int pathIndex) {

        final int targetDepth = pathToTarget.length - 1;
        final String counterName = pathToTarget[pathIndex];

        if (pathIndex == targetDepth && targetMap.containsKey(counterName)) {
            // assume objects at the target depth are int
            targetMap.put(counterName, (int) targetMap.get(counterName) + 1);
        } else if (pathIndex == targetDepth) {
            // at the target depth, put ints
            targetMap.put(counterName, 1);
        } else if (targetMap.containsKey(counterName)) {
            // assume object is a map, recur into it for the next counter name
            recursiveIncrement((Map<String, Object>) targetMap.get(counterName),
                    pathToTarget, pathIndex + 1);
        } else {
            // create a new map and recur into it for the next counter name
            Map<String, Object> emptyMap = new HashMap<>();
            targetMap.put(counterName, emptyMap);
            recursiveIncrement(emptyMap, pathToTarget, pathIndex + 1);
        }
    }

    public String toString() {
        return rootMap.toString();
    }

    @Test
    public void test() {
        StatisticsCounter counters = new StatisticsCounter();
        counters.increment("USA", "California", "Los Angeles");
        counters.increment("USA", "California", "Los Angeles");
        counters.increment("USA", "California", "San Diego");
        counters.increment("USA", "California", "Bay Area", "San Francisco",
                "Financial District");
        counters.increment("USA", "Tennessee", "Memphis");
        counters.increment("USA", "Tennessee", "Memphis");
        counters.increment("Italy", "Venice");
        counters.increment("Italy", "Rome");
        counters.increment("Italy", "Venice");
        counters.increment("Vatican City");
        counters.increment("Vatican City");

        try {
            counters.increment("USA", "California");
            fail("Cannot increment a key that already has subcounters");
        } catch (ClassCastException expectedException) {
            assertEquals("java.util.HashMap cannot be cast to java.lang.Integer",
                    expectedException.getMessage());
        }

        try {
            counters.increment("USA", "Tennessee", "Memphis", "Graceland");
            fail("Cannot add subcounters to a key that already has a count");
        } catch (ClassCastException expectedException) {
            assertEquals("java.lang.Integer cannot be cast to java.util.Map",
                    expectedException.getMessage());
        }

        System.out.println(counters);
        // {USA={Tennessee={Memphis=2}, California={San Diego=1, Bay Area={San
        // Francisco={Financial District=1}}, Los Angeles=2}}, Italy={Rome=1, Venice=2},
        // Vatican City=2}
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your opinion. Flatten if statement makes code more readable. But my most concern is the design. I simply avoid casting Object to Integer because it could be a cause of ClassCastingException as you mentioned. However I used Map<String, Object> to make the map flexible. The best way I expected(If it is possible) kind of flexible type safe map... \$\endgroup\$ – Juneyoung Oh Dec 20 '20 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.