API-интерфейс Java Collections API HashSet

Question

Я столкнулся с этой проблемой при работе с API коллекций Java.По сути, это метод поддержки реализации алгоритма Крускала для нахождения MST.Я создал этот класс для реализации алгоритма union / find.

Мой вопрос, поскольку мне удалось найти обходной путь, заключается в том, знает ли кто-нибудь какую-либо причину, почему метод remove в методе "union" будетне работает последовательно.То есть во время выполнения он удалит некоторые элементы, а не другие.Например, я реализовал это для задачи, связанной с городами, и мне не нравилось удалять некоторые города.В частности, он неоднократно сталкивался с несколькими разными наборами, но всегда одинаковыми.Я задавался вопросом, была ли это проблема со ссылкой на объект, т. Е. Проверял ли я не ту вещь, но я не мог ее обойти.

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

Мне было интересно, может ли кто-нибудь увидеть ошибку.Также я должен отметить, что я вызвал его из другого класса, однако, вызовы были сделаны с элементами, которые были получены с использованием метода find.Обратите внимание, что метод find должен работать хорошо, так как простое изменение метода удаления заставляло все это работать, то есть находило и возвращало соответствующие объекты.

Спасибо

Оскар

/*
 * A constructor for creating a new object of this class.
 */
DisjointSets()
{
    underlying = new HashSet<HashSet<String>>();
}

/*
 * A method for adding a set to this DisjointSets object
 */
void add(HashSet<String> h)
{
    underlying.add(h);
}

/*
 * A method for finding an element in this DisjointSet object.
 */
HashSet<String> find(String s)
{
    // Check each set in the DisjointSets object
    for(HashSet<String> h: underlying)
    {
        if(h.contains(s))
        {
            return h;
        }
    }
    return null;
}

/*
 * A method for combining to subsets of the DisjointSets
 */
void union(HashSet<String> h1, HashSet<String> h2)
{
    System.out.print("CHECK ON DS\n");
    System.out.print("*********************\n");
    System.out.print("H1 is : { ");
    for (HashSet<String> n: underlying) 
    {
        System.out.print("Set is : { ");
        for (String h : n) 
        {
            System.out.print(h + " , ");
        }
        System.out.print("} \n ");
    }
    // Add the objects of h1 to h2
    // DOES NOT WORK CONSISTENTLY
            h1.addAll(h2);
    underlying.remove(h2);
}

}

И я заменил его на

HashSet<HashSet<String>> temp = new HashSet<HashSet<String>>();
        for(HashSet<String> f: underlying)
        {
            if(f != h2)
            {
                temp.add(f);
            }
        }
        underlying = temp;

Answer 1

Проблема в том, что когда вы изменяете содержимое одного из вложенных HashSet, вы запинаете внутренние компоненты внешнего HashSet (потому что hashCode () вложенного HashSet изменился). чтобы правильно поддерживать эту коллекцию, всякий раз, когда вы хотите изменить один из вложенных HashSets, вы должны сначала удалить его из внешнего HashSet, а затем повторно добавить его (при необходимости).

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

Set<Set<String>> outerSet = new HashSet<String>();
Set<String> innerSet = new HashSet<String>();

innerSet.add("foo");
outerSet.add(innerSet);

// *** BROKEN ***
innerSet.add("bar");       // <- adding element to innerSet changes result of innerSet.hashCode()
outerSet.remove(innerSet); // <- this may or may not work because outerSet is _broken_
// *** BROKEN ***

// *** CORRECT ***
outerSet.remove(innerSet);
innerSet.add("bar");
// now you can put innerSet back in outerSet if necessary

Answer 2

В ответ на ответ @ jtahlborn, контракт на AbstractSet.hashCode() говорит

Возвращает значение хэш-кода для этого набора.Хеш-код набора определяется как сумма хеш-кодов элементов в наборе.Это гарантирует, что s1.equals (s2) подразумевает, что s1.hashCode () == s2.hashCode () для любых двух наборов s1 и s2, как того требует общий контракт Object.hashCode.

Эта реализацияперечисляет набор, вызывая метод hashCode для каждого элемента в коллекции и суммируя результаты.

Код для демонстрации ответа @ jtahlborn (это правильно)

import java.util.HashSet;
import java.util.Set;


public class TestHashSetHashCode {

  public static void main(String[] args)
  {
    Set<String> strings = new HashSet<String>();
    strings.add("one");
    strings.add("two");
    strings.add("three");
    strings.add("four");
    strings.add("five");
    Set<String> test = new HashSet<String>();
    System.out.println("Code "+test.hashCode());
    for (String s : strings) {
      test.add(s);
      System.out.println("Code "+test.hashCode());
    }
  }
}

Outputs

Code 0
Code 115276
Code 3258622
Code 3368804
Code 113708290
Code 116857384

Еще одна причина добавить в список, чтобы по возможности использовать неизменяемые коллекции.