[Подробно] HashMap удалить еще один элемент (не тот, который вы посещаете) во время итерации?

Question

Я хочу использовать список смежности для преобразования нормального графа в звездный.

Моя идея - использовать HashMap > для хранения точек и их списков смежности. Предположим, у нас есть

1- {2}; 2- {3,4} 3- {2,4} 5- {6} 6- {5} => Я хочу получить результат 1- {2,3,4} 5- {6}

И я повторяю hashmap и связанный с ним массив. Если итерирующий элемент массива hashmap является ключом дальнейшего элемента hashmap. Я вычитаю элементы массива из дополнительного элемента hashmap на основе определенных условий, а затем удаляю этот дополнительный элемент hashmap, чтобы избежать их зацикливания.

Однако итератору hashmap не разрешается удалять дополнительный элемент во время цикла. Серьезно, я не хочу хранить удаленные элементы в другом списке и повторять их снова, чтобы удалить эти элементы, и это слишком дорого, если мой набор данных довольно большой.

Таким образом, спасибо за предложения по итерационной проблеме или по структуре данных.

import java.util.*;
import org.apache.commons.collections.CollectionUtils;;


public class StarFind {


    public static void main(String[] args) {

        Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>() ;
        // contents of the map: <1,[2,4]>  <2,[1,4]>  <3,[1,2,4]>  <5,[6]><6,[5]>

        Map< Integer, ArrayList<Integer>> copyMap = new HashMap<Integer, ArrayList<Integer>>(map);      
        Iterator<Map.Entry<Integer, ArrayList<Integer>>> entries = map.entrySet().iterator();

        while (entries.hasNext()) { //problem here: when iterating 1th, the 2nd is removed from the hashmap and entries.next() is still the deleted 2nd item.
            Map.Entry<Integer, ArrayList<Integer>> entry = entries.next();
            ArrayList<Integer> alTemp = entry.getValue();

            for (int i=0; i<alTemp.size();i++)
            {
                int valueItem= alTemp.get(i);
                if (copyMap.containsKey(valueItem))
                {
                    @SuppressWarnings("unchecked")
                    Collection<Integer> tempCollection =  CollectionUtils.subtract(copyMap.get(valueItem), entry.getValue());
                    tempCollection.remove(entry.getKey());
                    entry.getValue().addAll(tempCollection);
                    copyMap.remove(valueItem);
                    map.remove(valueItem);
                }
            }
        }

}
}

Answer 1

Мне самому нравится ценностное решение, но есть еще один вариант:

Вы можете определить логический порядок ключей на вашей карте (например, идентификатор вершины). Затем, используя SortedMap или отдельную структуру отсортированных данных со значениями ключей, вы можете немедленно удалять элементы и по-прежнему находить следующий элемент в O (log (n)). Вы можете использовать SortedSet, или просто пойти с простым List и использовать Collections.sort ().

Answer 2

Вместо того, чтобы удалять, пока вы проходите, вы можете попробовать установить значение часового значения (обычно ноль), а затем очистить за второй проход.