为嵌套 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>());

在这个例子中，前两个"values"是两个Integer，第三个"value"是一个嵌套的HashMap，它包含两个Integer和一个"deeper level"嵌套的HashMap。关于key 7，我想表达的是 "value" 也可以是一个空的HashMap——因为这是一道面试题，我猜这种有 "empty value" 的可能性可能会影响到 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();
    }
  };
}

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

Implement a Java Iterator for a nested HashMap in which an element can be any of 1) an Integer or, 2) another nested HashMap or, 3) an empty HashMap

java

iterator

hashmap