Удалить из HashSet после сбоя

Question

Я пишу алгоритм агломерационной кластеризации в Java и у меня проблемы с операцией удаления. Кажется, что всегда происходит сбой, когда число кластеров достигает половины исходного числа.

В приведенном ниже примере кода clusters представляет собой Collection<Collection<Integer>>.

      while(clusters.size() > K){
           // determine smallest distance between clusters
           Collection<Integer> minclust1 = null;
           Collection<Integer> minclust2 = null;
           double mindist = Double.POSITIVE_INFINITY;

           for(Collection<Integer> cluster1 : clusters){
                for(Collection<Integer> cluster2 : clusters){
                     if( cluster1 != cluster2 && getDistance(cluster1, cluster2) < mindist){
                          minclust1 = cluster1;
                          minclust2 = cluster2;
                          mindist = getDistance(cluster1, cluster2);
                     }
                }
           }

           // merge the two clusters
           minclust1.addAll(minclust2);
           clusters.remove(minclust2);
      }

После нескольких прогонов цикла clusters.remove(minclust2) в конечном итоге возвращает false, но я не понимаю, почему.

Я проверил этот код, сначала создав 10 кластеров, каждое из которых имеет одно целое число от 1 до 10. Расстояния - это случайные числа от 0 до 1. Вот результат после добавления нескольких операторов println. После количества кластеров я распечатываю фактические кластеры, операцию слияния и результат cluster.remove (minclust2).

Clustering: 10 clusters
[[3], [1], [10], [5], [9], [7], [2], [4], [6], [8]]
[5] <- [6]
true
Clustering: 9 clusters
[[3], [1], [10], [5, 6], [9], [7], [2], [4], [8]]
[7] <- [8]
true
Clustering: 8 clusters
[[3], [1], [10], [5, 6], [9], [7, 8], [2], [4]]
[10] <- [9]
true
Clustering: 7 clusters
[[3], [1], [10, 9], [5, 6], [7, 8], [2], [4]]
[5, 6] <- [4]
true
Clustering: 6 clusters
[[3], [1], [10, 9], [5, 6, 4], [7, 8], [2]]
[3] <- [2]
true
Clustering: 5 clusters
[[3, 2], [1], [10, 9], [5, 6, 4], [7, 8]]
[10, 9] <- [5, 6, 4]
false
Clustering: 5 clusters
[[3, 2], [1], [10, 9, 5, 6, 4], [5, 6, 4], [7, 8]]
[10, 9, 5, 6, 4] <- [5, 6, 4]
false
Clustering: 5 clusters
[[3, 2], [1], [10, 9, 5, 6, 4, 5, 6, 4], [5, 6, 4], [7, 8]]
[10, 9, 5, 6, 4, 5, 6, 4] <- [5, 6, 4]
false

Набор [10, 9, 5, 6, 4, 5, 6, 4, ...] оттуда просто бесконечно растет.

Редактировать: чтобы уточнить, я использую HashSet<Integer> для каждого кластера в кластерах (a HashSet<HashSet<Integer>>).

Answer 1

Ах. Когда вы изменяете значение, которое уже находится в Set (или клавише Map), оно не обязательно находится в правильной позиции, и хеш-коды будут кэшироваться. Вам нужно удалить его, изменить его, а затем снова вставить.

Answer 2

В показанном тесте remove завершается неудачно при первой попытке удалить коллекцию, содержащую более одного целого числа. Это всегда так?

Какой тип коллекции используется?

Answer 3

Очевидная проблема заключается в том, что clusters.remove, вероятно, использует equals для поиска удаляемого элемента. К сожалению, equals в коллекциях обычно сравнивает, являются ли элементы одинаковыми, а не в одной коллекции (я думаю, C # делает лучший выбор в этом отношении).

Простое решение - создать clusters как Collections.newSetFromMap(new IdentityHashMap<Collection<Integer>, Boolean>()) (я думаю).