Java TreeSet содержит () дает ложные результаты
Я пытаюсь немного кодировать математику с Java. То, что я пытаюсь сделать, это поместить циклотомические классы в TreeSet. Класс имеет индекс и набор целых чисел. Класс смежности равен другому классу смежности, если набор имеет те же элементы. Если множества различаются, то класс смежности упорядочен по его индексу.
Например:
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 для меня.
Какие-либо предложения?
3 ответа
Как я часто говорю, если у вас есть ошибка в вашей программе, используйте отладчик. Это очень быстро показало мне вашу проблему.
TreeSet - это двоичное дерево. При поиске он перемещается вниз по дереву в зависимости от того, находится ли искомый элемент до или после (или тот же), что и исследуемый элемент. Если вы добавляете следующее, то сравнивайте ()
System.out.println("Comparing, "+this+" to "+c);
это распечатает
Comparing, C9 to C1
Comparing, C9 to C5
Comparing, C9 to C7
Проблема в том, что C9 находится после каждого элемента, которому он не соответствует. Поэтому, когда он достигает C5 на дереве, ваш CompareTo говорит, что он после него, когда на самом деле ему нужно посмотреть раньше (чтобы добраться до C3), и поиск идет по неверному пути дерева.
Ваш compareTo() а также equals() методы не согласованы, и поэтому TreeSet не может правильно работать с ними.
Из документа API:
Обратите внимание, что порядок, поддерживаемый набором (независимо от того, предоставляется или нет явный компаратор), должен быть согласован с equals, если необходимо правильно реализовать интерфейс Set. (См. Comparable или Comparator для точного определения соответствия с equals.) Это так, потому что интерфейс Set определен в терминах операции equals, но экземпляр TreeSet выполняет все сравнения элементов, используя свой метод CompareTo (или сравнение), поэтому два элементы, которые считаются равными этим методом, с точки зрения множества равны. Поведение множества корректно определено, даже если его порядок не совпадает с равенством; он просто не соблюдает общий контракт интерфейса Set.
Ваш Comparable реализация в Coset не обеспечивает полный заказ.
Похоже, вы должны определить порядок на valueTreeSet, Либо до, либо после проверки index,