Iterator for all elements in hash maps stored in an array

Question

I have a custom made class called Graph in which I use adjacency lists. To be more specific, I have an array of hash maps where each hash map contains all that node's neighbors as edges. The key is the end node and the value is an Edge object.

Now i want to make this Graph class implement Iterable. Is there a way of merging all those hash maps and return a common Iterator for all their elements?

It's very important that the method used is efficient.

Answer 1

You can use ChainedIterator from apache commons collections:

Iterator current = IteratorUtils.emptyIterator();
for(map: arrayOfHashmaps) {
   current = IteratorUtils.chainedIterator(current, map.keySet().iterator);
}

If you want to avoid commons collections you can just collect the keysets in a list and iterate it:

List allKeys = new LinkedList();
for(map: arrayOfHashmaps) {
   allKeys.addAll(map.KeySet());
}
return allKey.iterator();

The second solution will have uses slightly more memory and will be a little slower. However I doubt it will matter.

Answer 2

According to the API HashMap has a function called entrySet() which returns a set view of the mapping in the Hash. A set is an iterable object. To make the Iterator, simply iterate through the array turning each hash into a set and then composing the individual iterators into a single Iterator...

There is no built in way to compose Iterators in java, however, writing your own compose function should be trivial.

Answer 3

The way I would do it is to make an inner class that implements Iterator. Internally, it keeps track of 1) the current index into the array of maps, and 2) the iterator in the current map. Its hasNext() and next() methods would simply delegate to the current iterator, or if the iterator is finished, just increment the index and change the iterator.

Answer 4

Why not just roll your own that iterates successively over the various maps?

public class MapCollection<K,V> implements Iterable<V> {
  Map [] maps;

  public Iterator<V> iterator(){
           return new MapCollectionIterator(maps);
   }


   private class MapCollectionIterator<T>{
        public boolean hasNext() {
        public T next(){... (code omitted due to lazyness..)
  }

}

Answer 5

As an alternative you could try storing all the entries for a graph in a single HashMap, in which the key is an object containing both the node number and the neighbour node number. I presume the node number would normally be the index into the array of HashMaps, and the neighbour node the key to the current HashMap. That would enable you to do the same retrievals that you do now, and iterate over all the entries without having to write any special code.

Don't forget you'll need to write an equals() and a good hash function for the object used as the key (which object can otherwise be very simple). If you have very large graphs this may not be appropriate of course.