Iterator pour tous les éléments des mappages de hachage stockés dans un tableau

Question

J'ai une classe personnalisée appelée Graph dans laquelle j'utilise les listes d'adjacence. Pour être plus précis, j'ai un tableau de cartes de hachage où chaque carte de hachage contient tous les voisins de ce nœud comme des bords. La clé est le noeud final et la valeur est un objet Edge.

Maintenant, je veux que cette classe Graph implémente Iterable. Existe-t-il un moyen de fusionner toutes ces cartes de hachage et de renvoyer un itérateur commun pour tous leurs éléments?

Il est très important que la méthode utilisée soit efficace.

Answer 1

Selon le API HashMap a une fonction appelée entrySet() qui renvoie une vue définie du mappage dans le hachage. Un ensemble est un objet itérable. Pour créer l'itérateur, il suffit de parcourir le tableau et de transformer chaque hachage en un ensemble, puis de composer les itérateurs individuels en un seul itérateur ...

Il n'y a pas de manière intégrée de composer des itérateurs en java. La fonction de composition doit être triviale.

Answer 2

Vous pouvez utiliser ChainedIterator de collections communes apache:

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

Si vous voulez éviter communes collections, vous pouvez simplement collecter les keysets dans une liste et itérer il:

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

La deuxième solution aura un peu plus de mémoire et sera un peu plus lent. Cependant, je doute que cela aura de l'importance.

Answer 3

La façon dont je le ferais est de faire une classe interne qui implémente Iterator. En interne, il garde la trace de 1) l'index courant dans le tableau de cartes, et 2) l'itérateur dans la carte actuelle. Ses méthodes hasNext() et next() seraient simplement déléguées à l'itérateur actuel, ou si l'itérateur est terminé, il suffit d'incrémenter l'index et de changer l'itérateur.

Answer 4

Pourquoi ne pas rouler le vôtre qui itère successivement sur les différentes cartes?

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

Comme alternative, vous pouvez essayer de stocker toutes les entrées d'un graphique dans un seul HashMap, dans lequel la clé est un objet contenant à la fois le numéro de noeud et le numéro de nœud voisin. Je suppose que le numéro de nœud serait normalement l'index dans le tableau de HashMaps, et le nœud voisin la clé de la HashMap actuelle. Cela vous permettrait de faire les mêmes extractions que vous faites maintenant, et de parcourir toutes les entrées sans avoir à écrire de code spécial.

N'oubliez pas que vous devez écrire equals() et une bonne fonction de hachage pour l'objet utilisé comme clé (quel objet peut être très simple). Si vous avez de très gros graphiques, cela peut ne pas être approprié, bien sûr.