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

Question

在尝试创建遵循模式的数据结构时，我有一个思维障碍：

Map<String, T>是一个主要的构建块，并且T是Map<String, T>或作为终端运营商List<String>。是否可以在 中构建任何类似的东西Java，这个想法来自类似F#或类似的函数Haskell式语言。

我搜索SO但到目前为止找不到任何符合我的想法的Java.

Answer 1

是的：你可以这样做：public abstract class T {...}public class NonTerminal extends T {&nbsp; &nbsp; private Map<String,T> map = new HashMap<>();...}public class Terminal extends T {&nbsp; &nbsp; private List<String> list;---}

Answer 2

您可以只使用一个Map<String, KeyOrValue>值可以是具有两个实现的标记接口interface KeyOrValue {}class Key implements KeyOrValue {&nbsp; &nbsp; private String key;}class Value implements KeyOrValue {&nbsp; &nbsp; private List<String> values;}然后，您可以创建一个查找方法，该方法递归调用自身，然后在到达末尾时返回该值：private final Map<String, KeyOrValue> map = ...public List<String> getValues(String key) {&nbsp; &nbsp; KeyOrValue keyOrValue = map.get(key);&nbsp; &nbsp; if(keyOrValue instanceof Key) {&nbsp; &nbsp; &nbsp; &nbsp; // is a key, so use recursion to get the value&nbsp; &nbsp; &nbsp; &nbsp; key = ((Key) keyOrValue).key;&nbsp; &nbsp; &nbsp; &nbsp; return getValues(key);&nbsp; &nbsp; } else if(keyOrValue instanceof Value) {&nbsp; &nbsp; &nbsp; &nbsp; // is a value, so just return the value it holds&nbsp; &nbsp; &nbsp; &nbsp; return ((Value) keyOrValue).values;&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; // no mapping was found for "key"&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; }}你也可以在没有递归的情况下做同样的事情：public List<String> getValues(String key) {&nbsp; &nbsp; KeyOrValue keyOrValue;&nbsp; &nbsp; List<String> values = null;&nbsp; &nbsp; do {&nbsp; &nbsp; &nbsp; &nbsp; keyOrValue = map.get(key);&nbsp; &nbsp; &nbsp; &nbsp; if(keyOrValue instanceof Key) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // is a key, so iterate further&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; key = ((Key) keyOrValue).key;&nbsp; &nbsp; &nbsp; &nbsp; } else if(keyOrValue instanceof Value) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // is a value, so get the values out and set the key to null to break the loop&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; values = ((Value) keyOrValue).values;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; key = null;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; } while(key != null);&nbsp; &nbsp; // return the values, may be null due to nothing being found&nbsp; &nbsp; return values;}虽然实际上并不需要标记接口，但如果您只使用Map<String, Object>值可能是 aString或 a 的地方，您可以获得相同的结果List<String>，然后instanceof检查也必须进行调整，但我喜欢这种方法interface更多

Answer 3

在 Java 中重新创建函数式编程的东西并不是一个好主意（至少在 Java 8 中不是，我不知道 Java 11）。你可以这样做：class EitherMapOrList {&nbsp; &nbsp; private Map<String, EitherMapOrList> map;&nbsp; &nbsp; private List<String> list;&nbsp; &nbsp; public EitherMapOrList(Map<String, EitherMapOrList> map) {&nbsp; &nbsp; &nbsp; &nbsp; this.map = map;&nbsp; &nbsp; }&nbsp; &nbsp; public EitherMapOrList(List<String> list) {&nbsp; &nbsp; &nbsp; &nbsp; this.list = list;&nbsp; &nbsp; }&nbsp; &nbsp; // you can remove the optionals here and use null directly.&nbsp; &nbsp; public Optional<Map<String, EitherMapOrList>> getMap() {&nbsp; &nbsp; &nbsp; &nbsp; return Optional.ofNullable(map);&nbsp; &nbsp; }&nbsp; &nbsp; public Optional<List<String>> getList() {&nbsp; &nbsp; &nbsp; &nbsp; return Optional.ofNullable(list);&nbsp; &nbsp; }}然后创建一个Map<String, EitherMapOrList>.但我想在 Java 中使用这个东西会很痛苦。

Answer 4

如果你想翻译haskelldata Map a = Branch { key :: String, value :: a, left :: Map a, right :: Map a} | MapNul到java你可以去：class Map<T> {&nbsp; &nbsp; String key;&nbsp; &nbsp; T value;&nbsp; &nbsp; Map<T> left;&nbsp; &nbsp; Map<T> right;}&nbsp;MapNul你在java中不需要，因为你可以使用null它来代替它。