如何使用Map<String, T>在Java中创建递归树形数据结构？

Question

我在创建符合以下模式的数据结构时遇到了难题：Map<String, T>是主要的构建块，其中T要么是Map<String, T>，要么是作为终端运算符的List<String>。是否可能在Java中构建类似的内容，这个想法来自函数式语言��如F#或类似于Haskell的语言。我在SO上进行了搜索，但目前还没有找到与我在Java中的想法相匹配的任何东西。

- Dmytro Chasovskyi

Answer 1

是的，您可以做类似于这样的事情：

public abstract class T {
...
}
public class NonTerminal extends T {
    private Map<String,T> map = new HashMap<>();
...
}
public class Terminal extends T {
    private List<String> list;
---
}

- Maurice Perry

---

我会选择接口而不是抽象类，没有必要限制继承。 - RealSkeptic

我会给抽象类添加私有构造函数，并将子类作为静态嵌套类放置，使其看起来像代数数据类型。 - Some Name

Answer 2

在Java中重新创建函数式编程的东西并不是一个好主意（至少在Java 8中不是，我不知道Java 11如何）。

你可以像这样做：

class EitherMapOrList {
    private Map<String, EitherMapOrList> map;
    private List<String> list;

    public EitherMapOrList(Map<String, EitherMapOrList> map) {
        this.map = map;
    }

    public EitherMapOrList(List<String> list) {
        this.list = list;
    }
    // you can remove the optionals here and use null directly.
    public Optional<Map<String, EitherMapOrList>> getMap() {
        return Optional.ofNullable(map);
    }

    public Optional<List<String>> getList() {
        return Optional.ofNullable(list);
    }
}

然后创建一个Map<String, EitherMapOrList>。

但我认为在Java中使用这个东西可能会很麻烦。

- Sweeper

Answer 3

您可以使用一个 Map<String, KeyOrValue>，其中值可以是带有两个实现的标记接口。

interface KeyOrValue {}

class Key implements KeyOrValue {
    private String key;
}

class Value implements KeyOrValue {
    private List<String> values;
}

你可以创建一个查找方法，该方法递归调用自身，一旦到达末尾就返回值：

private final Map<String, KeyOrValue> map = ...

public List<String> getValues(String key) {
    KeyOrValue keyOrValue = map.get(key);
    if(keyOrValue instanceof Key) {
        // is a key, so use recursion to get the value
        key = ((Key) keyOrValue).key;
        return getValues(key);
    } else if(keyOrValue instanceof Value) {
        // is a value, so just return the value it holds
        return ((Value) keyOrValue).values;
    } else {
        // no mapping was found for "key"
        return null;
    }
}

您也可以不使用递归来实现相同的功能：

public List<String> getValues(String key) {
    KeyOrValue keyOrValue;
    List<String> values = null;
    do {
        keyOrValue = map.get(key);
        if(keyOrValue instanceof Key) {
            // is a key, so iterate further
            key = ((Key) keyOrValue).key;
        } else if(keyOrValue instanceof Value) {
            // is a value, so get the values out and set the key to null to break the loop
            values = ((Value) keyOrValue).values;
            key = null;
        }
    } while(key != null);

    // return the values, may be null due to nothing being found
    return values;
}

---

尽管标记接口并不是必需的，但您可以通过使用Map<String, Object>来获得相同的结果，其中值可以是String或List<String>，然后必须调整instanceof检查，但我更喜欢使用interface的方法。

- Lino

Answer 4

如果你想翻译Haskell，可以参考"最初的回答"。

data Map a = Branch { key :: String, value :: a, left :: Map a, right :: Map a} | MapNul

你可以选择Java：

class Map<T> {
    String key;
    T value;
    Map<T> left;
    Map<T> right;
} 

在Java中，您不需要使用MapNul，因为您可以使用null代替它。

最初的回答已经足够明确了。

- talex