Best way to flatten and unflatten a HashMap

Question

I would like to flatten a HashMap instance like in this example. Note that the data is not in JSON format, this is just a pseudo code:

nested = {
  "one": {
    "two": {
      "2a": "x",
      "2b": "y"
    }
  },
  "side": "value"
}

// output: { "one.two.2a": "x", "one.two.2b": "y", "side": "value" }

Unfortunately, I couldn't find any reference implementation for that so I came up with my recursive solution shown below. Is there a better way (in terms of not using recursion or performance or safety or cleanliness :)) to achieve this? The output should be another HashMap in flattened form.

I will use the result for this kind of purpose https://redislabs.com/redis-best-practices/data-storage-patterns/object-hash-storage/

public class Flat {

  public static void flatten(Map<String, ?> target, Map<String, String> result, String path) {
    for (var entry : target.entrySet()) {
      var next = path.equals("") ? entry.getKey() : path + "." + entry.getKey();
      if (entry.getValue() instanceof Map) {
        flatten((Map) entry.getValue(), result, next);
      } else {
        result.put(next, entry.getValue().toString());
      }
    }
  }

  public static Map unflatten(Map<String, String> target) {
    var result = new HashMap<String, Object>();
    for (var entry : target.entrySet()) {
      if (entry.getKey().split(".").length == 1) {
        result.put(entry.getKey(), entry.getValue());
      } else {
        var path = entry.getKey().split(".");
        Map<String, Object> current = new HashMap<>();
        for (var i = 0; i < path.length - 1; i++) {
          if (result.containsKey(path[i])) {
            current = (Map) (result.get(path[i]));
          } else {
            current = new HashMap<>();
            result.put(path[i], current);
          }
        }
        current.put(path[path.length - 1], entry.getValue());
      }
    }
    return result;
  }
}

Answer 1

If you want to clean up the recursive code then you could update it like below:

public static Map<String, String> flatten(Map<String, ?> source) {
    Map<String, String> converted = new HashMap<>();

    for (var entry : source.entrySet()) {
        if (entry.getValue() instanceof Map) {
            flatten((Map<String, Object>) entry.getValue())
                    .forEach((key, value) -> converted.put(entry.getKey() + "." + key, value));
        } else {
            converted.put(entry.getKey(), entry.getValue().toString());
        }
    }

    return converted;
}

Thanks to a comment I looked into a stack solution as well. You could rewrite the flatten to use the following example. Which one you should use depends on the skill level of the developers, as the stacked version is a bit more complicated to understand.

private static class StackElement {
    Optional<String> key;
    Map<String, ?> elements;

    public StackElement(String key, Map<String, ?> elements) {
        this.key = Optional.ofNullable(key);
        this.elements = elements;
    }
}

public static Map<String, String> flattenNonRecursive(Map<String, ?> source) {
    Map<String, String> converted = new HashMap<>();

    Stack<StackElement> stack = new Stack();
    stack.push(new StackElement(null, source));

    while (!stack.empty()) {
        var frame = stack.pop();

        for (var entry : frame.elements.entrySet()) {
            var frameKey = frame.key
                    .map(k -> k + ".")
                    .orElse("") + entry.getKey();

            if (entry.getValue() instanceof Map) {
                stack.push(new StackElement(frameKey, (Map<String, ?>) entry.getValue()));
            } else {
                converted.put(frameKey, entry.getValue().toString());
            }
        }
    }

    return converted;
}

Regarding performance the non recursive is faster. I performed a little experiment using a map with Map.of("sample.test.two", "one", "test.sample.two", "three", "four", "file").

Calling the method 1000 times the performance difference was:

Recursive took:         20957300
Non recursive took:     13376000

As for your unflatten, this contains bugs. In a test run I did with a simple map containing only two elements it crashed with an index out of bounds. This has to do with you using result and current in incorrect places. Below is a working copy that is slightly altered:

public static Map<String, ?> unflatten(Map<String, String> target) {
    var result = new HashMap<String, Object>();

    for (var entry : target.entrySet()) {
        var split = entry.getKey().split("\\.");
        if (split.length == 1) {
            result.put(entry.getKey(), entry.getValue());
            continue;
        }

        var current = result;
        for (int i = 0; i < split.length - 1; i++) {
            current = (HashMap<String, Object>) current.computeIfAbsent(
                    split[i], p -> new HashMap<String, Object>());
        }
        current.put(split[split.length - 1], entry.getValue());
    }

    return result;
}