Java TreeSet содержит () дает ложные результаты - PullRequest
Новая
       7

Java TreeSet содержит () дает ложные результаты

1 голос
/ 30 ноября 2010

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

Например: 

C1 = [1, 2, 4, 8]
C3 = [3, 6, 9, 12]
C9 = [3, 6, 9, 12]

C1 is less than C3
C3 is equal to C9

Достаточно математика.Я решил поместить классы в TreeSet, потому что мне не нужны повторяющиеся элементы, и мне нужно отсортировать их по индексу.

Проблема в том, что даже TreeSet.contains () возвращает false, я все еще могу найти один элементTreeSet, который равен при использовании методов compareTo () и equals ().

Это фактическая распечатка программы: 

cosets = [C0, C1, C3, C5, C7]
cosets.contains(C9) = false
C0.compareTo(C9) = -1, C0.equals(C9) = false
C1.compareTo(C9) = -1, C1.equals(C9) = false
C3.compareTo(C9) = 0, C3.equals(C9) = true
C5.compareTo(C9) = -1, C5.equals(C9) = false
C7.compareTo(C9) = -1, C7.equals(C9) = false

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

http://2m.lt/files/Main.java

http://2m.lt/files/Coset.java

Есть предложения?

Ответы [ 3 ]

4 голосов
/ 30 ноября 2010

Ваши compareTo() и equals() методы не согласованы, и поэтому TreeSet не может работать с ними корректно.

Из API doc :

Обратите внимание, что порядок, поддерживаемый множеством (независимо от того, предоставляется ли явный компаратор), должен быть согласован с равными, если необходимо правильно реализовать интерфейс Set.(См. Comparable или Comparator для точного определения соответствия с equals.) Это так, потому что интерфейс Set определен в терминах операции equals, но экземпляр TreeSet выполняет все сравнения элементов, используя свой метод CompareTo (или сравнение), поэтому дваэлементы, которые считаются равными этим методом, с точки зрения множества равны.Поведение множества корректно определено, даже если его порядок не совпадает с равенством;он просто не соблюдает общий контракт интерфейса Set.

3 голосов
/ 30 ноября 2010

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

TreeSet - это двоичное дерево.При поиске он перемещается вниз по дереву в зависимости от того, находится ли искомый элемент до или после (или тот же), что и исследуемый элемент.Если вы добавите следующее к вам CompareTo () 

System.out.println("Comparing, "+this+" to "+c);

, оно выведет 

Comparing, C9 to C1
Comparing, C9 to C5
Comparing, C9 to C7

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

3 голосов
/ 30 ноября 2010

Ваша реализация Comparable в Coset не обеспечивает полное упорядочение.

Похоже, вы должны определить порядок на value TreeSet.Либо до, либо после проверки index.

...