Java：递归迭代映射

Question

我们有一个看起来像“递归”数据结构的对象。

假设我们有一个Person对象，其结构是这样的

public class Person { 
    private String id; 

    private Map<String,Person> persons; 

    public Person(String id, Map<String,Person> persons){ 
     this.id = id; 
     this.persons = persons; 
    } 

    public String getId() { 
     return id; 
    } 

    public void setId(String id) { 
     this.id = id; 
    } 

    public Map<String, Person> getPersons() { 
     return persons; 
    } 

    public void setPersons(Map<String, Person> persons) { 
     this.persons = persons; 
    } 

    @Override 
    public String toString() { 
     return "Person [id=" + id + ", persons=" + persons + "]"; 
    } 

} 

该对象的一个​​实例表示为：ImmutableMap是从谷歌：（样本数据）

Person p1 = new Person("Jim", ImmutableMap.of("A001",new Person("Mike",ImmutableMap.of("D001",new Person("Jack",ImmutableMap.of("E001",new Person("Kim",null))))), 
                 "Z001",new Person("Adam",ImmutableMap.of("Y001",new Person("Eve",ImmutableMap.of("X001",new Person("Dave",null))))))); 

注1番石榴集合

注2：我们假设Person对象中Map的'key'是人的名字。

给定一个人的名字，什么是最有效的方式去迭代和获得id。？

例如，如果输入的是“夏娃”，输出应该如你已经在使用番石榴NE“Y001”

Answer 1

，考虑加入这样的方法给Person类：

public FluentIterable<Map.Entry<String, Person>> tree() { 
    if (persons == null) 
     return FluentIterable.from(ImmutableList.of()); 
    return FluentIterable.from(persons.entrySet()) 
      .transformAndConcat(
       entry -> Iterables.concat(ImmutableList.of(entry), entry.getValue().tree())); 
} 

或者，如果你不能使用Java-8：

public FluentIterable<Map.Entry<String, Person>> tree() { 
    if (persons == null) 
     return FluentIterable.from(ImmutableList.of()); 
    return FluentIterable.from(persons.entrySet()) 
     .transformAndConcat(
      new Function<Entry<String, Person>, Iterable<Entry<String, Person>>>() { 
      @Override 
      public Iterable<Map.Entry<String, Person>> apply(
        Map.Entry<String, Person> entry) { 
       return Iterables.concat(ImmutableList.of(entry), entry.getValue().tree()); 
      } 
     }); 
} 

将压扁的所有人员进入单Iterable它可以在for循环很容易使用的树：

String name = "Eve"; 
for(Map.Entry<String, Person> e : p1.tree()) { 
    if(e.getValue().getId().equals(name)) { 
     System.out.println(e.getKey()); 
     break; 
    } 
} 

或者与FluentIterable操作：

System.out.println(p1.tree() 
        .firstMatch(e -> e.getValue().getId().equals(name)) 
        .get().getKey()); 

Answer 2

您的结构在现实中类型的树。所以你可以使用标准的树木排序方法。如果你的树是一棵二叉树（看起来不是这样），你可能能够非常有效地做到这一点。

下面会工作，但我没有证据证明它是最有效的方法。大部分非二叉树都必须被阻塞。

效率取决于您认为递归性堆叠的程度。如果你认为大多数建筑物会像样本结构一样，那就是：非常深，但是每层只有几个人，这样会很有效率。特别是如果你的结果将接近底部。

public String iterate(String name) { 
     if (persons != null) { 
      for (Entry<String, Person> entry : persons.entrySet()) { 
       Person value = entry.getValue(); 
       if (value.getId().equals(name)) { 
        return entry.getKey(); //Since the key of each map is the ID when they return the key 
       } else { 
        String ans = value.iterate(name); 
        if (ans != null) { 
         return ans; 
        } 
       } 
      } 
     } 
     return null; 
    } 

它快速浏览整个人员列表，而不必返回顶部。

但是，如果您有一个广泛的设置，并且您认为您的值将大部分靠近顶部，您可以使用类似以下内容。

public String iterate(String name) { 
     if (persons != null) { 
      for (Entry<String, Person> entry : persons.entrySet()) { 
       Person value = entry.getValue(); 
       if (value.getId().equals(name)) { 
        return entry.getKey(); //Since the key of each map is the ID when they return the key 
       } 
      } 

      for (Entry<String, Person> entry : persons.entrySet()) { 
       String ans = entry.getValue().iterate(name); 
       if (ans != null) { 
        return ans; 
       } 
      } 
     } 
     return null; 
    } 

这将允许您快速找到靠近结构顶​​部的东西，但在结构底部找到一个人会更慢。

我猜你会想要更高的解决方案，这是更标准的。但是，我不认为他们之间有巨大的差异。有关它的另一个版本，请参阅有关遍历树的this question。

Answer 3

这是番石榴的TreeTraverser一个完美的工作：

Iterable<Person> allPersons = new TreeTraverser<Person>() { 
    @Override public Iterable<Person> children(Person p) { 
    return p.getPersons().values(); 
    } 
}.preOrderTraversal(rootPerson); 
for (Person p : allPersons) { 
    if (p.getId().equals(id)) { 
    return p; 
    } 
}