Как сохранить два итератора над картой в java и удалить промежуточные ключи без ConcurrentModificationException

Мне нужно обработать Map <BitSet,List<List<Integer>> MyMap

if (key1 contains all of corresponding true bits of key2)
     Remove from key2 all those values which are common with key1)

В этом процессе, если количество элементов в списке падает ниже ПОРОГА (определяемое пользователем положительное целое число), он удаляется. Также, если Карта содержит пустой список, соответствующий ключ удаляется.

Я использую следующий код:

List<BitSet> keys = new ArrayList<>(MyMap.keySet());  
ListIterator it1=keys.listIterator();
while(it1.hasNext())  {
     BitSet key1=(BitSet)it1.next();
     ListIterator it2=keys.listIterator(it1.nextIndex());
     while(it2.hasNext()) {
         BitSet key2=(BitSet)it2.next();                 
         BitSet ankey=(BitSet)key1.clone();
         ankey.and(key2);    
         if(ankey.equals(key1)) {//key1 is subset and key2 is superset
               if(removePoints(key1,key2))  {
                     it1.remove();
                     break;
               }
         }
         else if(ankey.equals(key2))  {                           
              if(removePoints(key2,key1))  {
                    it2.remove();                         
              }
         }
     }
}

public static boolean removePoints(BitSet key1,BitSet key2)
 {
     List<List<Integer>> list1=MyMap.get(key1);         
     List<List<Integer>> list2=MyMap.get(key2);
     Boolean ret=false;         
     for(int i=0;i<list1.size();i++)  {                   
         List<Integer> sublist1=list1.get(i);            
         for(int j=0;j<list2.size();j++)  {            
             List<Integer> sublist2=list2.get(j);                 
             sublist1.removeAll(sublist2);
             if(sublist1.isEmpty())
                 break;
         }
         if(sublist1.size()<=THRESHOLD)
             list1.remove(sublist1);
         if( list1.isEmpty()) {             
             MyMap.remove(key1); 
             ret=true;                 
         }
     }
     return ret;
 }

Но программа выдает ошибку:

java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification
at java.util.ArrayList$Itr.next

Кроме того, я не уверен, что это эффективный способ кодирования? Поскольку карта содержит ~ 2000 записей. Пожалуйста, порекомендуйте.


java hashmap iterator concurrentmodification
person Kaur    schedule 11.03.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

ConcurrentModificationException может произойти, когда базовая коллекция изменяется после создания Iterator, и эта модификация не выполняется через сам Iterator.

В вашем коде, как написано, есть только одно место, где это может произойти: взаимодействие между it1 и it2, которые являются итераторами в одной и той же коллекции. Каждый раз, когда вы вызываете remove на одном, другой сломается при следующем вызове next.

Существует множество способов обойти это, но один из них — отделить то, что вы удаляете из своей «ключевой» коллекции, от итерации этой коллекции, например:

List<BitSet> allKeys = new ArrayList<>(MyMap.keySet());  
List<BitSet> removedKeys = new ArrayList<>();

for (ListIterator<BitSet> it1 = allKeys.listIterator(); it1.hasNext(); ) {
   BitSet key1 = it1.next();
   for (ListIterator<BitSet> it2 = allKeys.listIterator(it1.nextIndex()); it2.hasNext(); ) {
       BitSet key2 = it2.next();
       BitSet ankey=(BitSet)key1.clone();
       ankey.and(key2);    
       if(ankey.equals(key1)) {//key1 is subset and key2 is superset
           if(removePoints(key1,key2))  {
                 removedKeys.add(key1);
                 break;
           }
       }
       else if(ankey.equals(key2))  {                           
          if(removePoints(key2,key1))  {
                 removedKeys.add(key2);
                 break;
          }
       }
    }
}

allKeys.removeAll(removedKeys);

allKeys будет в ожидаемом состоянии. Я предполагаю, что когда-нибудь позже вы захотите вызвать MyMap.keySet().retainAll() или что-то подобное.

person sharakan    schedule 03.04.2013

arrow_upward
0
arrow_downward

Вы не можете использовать iterator.remove() для набора ключей карты, поскольку это всего лишь «представление» внутренней структуры карты.

Но вы можете использовать итератор для entrySet() карты, где каждый элемент является экземпляром Map.Entry, содержащим все записи карты (пары ключ/значение). Вы можете вызвать iterator.remove() для этого итератора, который эффективно удалит соответствующую пару ключ/значение с карты.

Map<Integer, String> map = new HashMap<Integer, String>();
map.put(Integer.valueOf(0), "0");
map.put(Integer.valueOf(1), "1");
map.put(Integer.valueOf(2), "2");
map.put(Integer.valueOf(3), "3");
map.put(Integer.valueOf(4), "4");

System.out.println(map);

Iterator<Map.Entry<Integer, String>> entryIter = map.entrySet().iterator();
while (entryIter.hasNext()) {
   Map.Entry<Integer, String> entry = entryIter.next();
   if (entry.getKey().intValue() % 2 == 0)
       entryIter.remove();
}

System.out.println(map);

Надеюсь, что это поможет.

С Уважением

person Marc    schedule 03.04.2013
comment
Вы не правы насчет Map.iterator().remove(), по крайней мере, в целом. Интерфейс указывает, что удаление поддерживается, а добавление — нет. - person sharakan; 03.04.2013