java - 为嵌套 HashMap 实现 Java 迭代器，其中元素可以是 1) Integer 或 2) 另一个嵌套 HashMap 或 3) 空 HashMap 中的任意一个

Question

如标题所述，我们该如何做到这一点？我觉得它应该类似于树遍历，但我不知道如何做到这一点。

    Map<Integer, Object> map = new HashMap<>();     

    map.put(1, 1);
    map.put(2, 2);


    map.put(3, new HashMap<Integer, Object>());
    Map<Integer, Object> m1 = (Map<Integer, Object>)map.get(3);
    m1.put(4, 4);
    m1.put(5, new HashMap<Integer, Object>());      
    m1.put(6, 6);

    Map<Integer, Object> m2 = (Map<Integer, Object>)m1.get(5);
    m2.put(8, 8);
    m2.put(9, 9);

    map.put(7, new HashMap<Integer, Object>());

在此示例中，前两个“值”是两个 Integers，第三个“值”是一个嵌套 HashMap，其中包含两个 Integers 和一个“更深层次”嵌套 HashMap。关于键7，我想表达的是“值”也可以是一个空的HashMap——因为这是一个面试题，我猜这种“空值”的可能性可能会影响next()或hasNext()的实现？

Answer 1

实际上有很多不同的解决方案。到目前为止，最短的是这里，它使用 Streams。

@SuppressWarnings("unchecked")
static <T> Stream<T> mapTraversalStream(Map<Integer, T> map) {
  return map.values().stream().flatMap(value -> {
    if(value instanceof Map) {
      return mapTraversalStream((Map<Integer, T>)value);
    } else {
      return Stream.of(value);
    }
  });
}

static <T> Iterator<T> mapTraversalIterator(Map<Integer, T> map) {
  return mapTraversalStream(map).iterator();
}

编辑:

如果您无法使用 Java 8，您可以定义自己的映射和展平方法。

@SuppressWarnings("unchecked")
static <T> Iterator<T> mapTraversalIterator(Map<Integer, T> map) {
  return flatten(map(map.values().iterator(), new Function<T, Iterator<T>>() {
      public Iterator<T> apply(T value) {
        if(value instanceof Map) {
          return mapTraversalIterator((Map<Integer, T>)value);
        } else {
          return Collections.singleton(value).iterator();
        }
      }
  }));
}

interface Function<A, B> {
  B apply(A a);
}

static <A, B> Iterator<B> map(Iterator<A> iter, Function<A, B> op) {
  return new Iterator<B>() {
    public boolean hasNext() {
      return iter.hasNext();
    }
    public B next() {
      return op.apply(iter.next());
    }
  };
}

static <A> Iterator<A> flatten(Iterator<Iterator<A>> iter) {
  return new Iterator<A>() {
    private Iterator<A> next = null;

    public boolean hasNext() {
      while(iter.hasNext() && (next == null || !next.hasNext())) {
        next = iter.next();
      }
      if(next == null || !next.hasNext()) return false;
      else return true;
    }
    public A next() {
      if(!hasNext()) throw new NoSuchElementException();
      return next.next();
    }
  };
}