展平和取消展平 HashMap 的最佳方法

Question

我想像HashMap这个例子中那样展平一个实例。请注意，数据不是 JSON 格式，这只是一个伪代码：

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

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

不幸的是，我找不到任何参考实现，所以我想出了我的递归解决方案，如下所示。有没有更好的方法（在不使用递归或性能或安全性或清洁度方面:)）来实现这一目标？输出应该是另一个HashMap扁平形式。

我会将结果用于这种目的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

如果你想清理递归代码，那么你可以像下面这样更新它：

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;
}

感谢评论，我也研究了堆栈解决方案。您可以重写展平以使用以下示例。您应该使用哪一个取决于开发人员的技能水平，因为堆叠版本理解起来有点复杂。

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;
}

关于性能，非递归更快。我使用带有 的地图进行了一个小实验Map.of("sample.test.two", "one", "test.sample.two", "three", "four", "file")。

调用该方法 1000 次，性能差异为：

Recursive took:         20957300
Non recursive took:     13376000

至于你的 unflatten，这包含错误。在测试运行中，我使用了一个仅包含两个元素的简单地图，它因索引越界而崩溃。result这与你使用andcurrent的地方不正确有关。以下是稍作修改的工作副本：

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;
}