[详细] HashMap迭代时删除更多的项目（不是你正在访问的项目）？

问题描述

我的想法是使用HashMap< p> Interger，ArrayList<整数>>存储点及其邻接列表。假设，我们有

1- 1- {2}; 2- {3,4} 3- {2,4} 5- {6} 6- {5} =>结果我想1- {2,3,4} 5- {6}

然后迭代hashmap和相关的数组列表。如果hashmap的数组列表的迭代项是进一步hashmap项的关键字。我根据某些条件从进一步的hashmap项目中减去arraylist项目，然后删除此进一步的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>>（）; 
 //映射的内容：< 1，[2,4]> &2，[1,4]> < 3，[1,2,4]>小于5，[6]>&10 6，[5]> 
 
地图<整数，ArrayList<整数>> copyMap = new HashMap< Integer，ArrayList< Integer>>（map）; 
 Iterator< Map.Entry< Integer，ArrayList< Integer>>> entries = map.entrySet（）。iterator（）; 
 
 while（entries.hasNext（））{//这里的问题：迭代1时，第二个从hashmap中删除，并且entries.next（）仍然是第二个被删除的项目。 
 Map.Entry< Integer，ArrayList< Integer>> entry = entries.next（）; 
 ArrayList<整数> 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）; 
} 
} 
} 
 
} 
} 
  

$ b $我自己喜欢哨兵价值的解决方案，但这里有另一种选择：

你可以定义一个逻辑排序到你的地图中的键（例如顶点id）。然后，通过使用SortedMap或具有键值的单独排序数据结构，您现在可以立即删除项目，并仍然可以找到O（log（n））中的下一个项目。你可以使用SortedSet，或者只是用一个简单的List来使用Collections.sort（）。

I wanna use the adjacency list to convert the normal graph to a star graph.

My idea is to use HashMap< Interger， ArrayList< Integer >> to store the points and their adjacency lists. Assume, we have

1-{2}; 2-{3,4} 3-{2,4} 5-{6} 6-{5} => The result I want 1-{2,3,4} 5-{6}

And I iterate the hashmap and related arraylist. If the iterating item of hashmap's arraylist is the key of further hashmap item. I subtract the arraylist items from the further hashmap item based on certain conditions and then delete this further hashmap item to avoid looping them.

However, hashmap iterator is not allowed to delete an further item while looping. Seriously, I do not want to store the removed items in another list and iterate them again to remove these items and it is too expensive if my dataset is rather large.

Thus, thanks for the suggestions on iterating problem or on the data structure.

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);
                }
            }
        }

}
}

解决方案

I like the sentinel value solution myself, but here's another option:

You could define a logical ordering to the keys into your map (e.g. vertex id). Then either by using a SortedMap or a separate sorted data structure with the key values, you can now delete items immediately and still find the next item in O(log(n)). You could use SortedSet, or perhaps just go with a simple List and use Collections.sort().

这篇关于[详细] HashMap迭代时删除更多的项目（不是你正在访问的项目）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！