Блог

Я действительно хочу углубить свое понимание того, как именно TreeSet, особенно версия без аргументов, которая не использует компаратор, поддерживает элементы, которые он содержит в порядке. Я нигде не могу найти удовлетворительного объяснения; они либо слишком простые, либо слишком сложные для меня. Из моих исследований кажется, что наборы деревьев фактически хранят свои элементы в TreeMap, а TreeMaps на самом деле являются красно-черными деревьями. Я чувствую себя довольно уверенно в своем понимании того, как элементы добавляются в красно-черные деревья.

Я предполагаю, что где-то в java API должен быть алгоритм или метод, который выполняет вставку элементов в красно-черное дерево. Мой первый вопрос: где в Java API находится этот алгоритм?

Кроме того, как именно вызывается этот алгоритм? Я предполагаю, что он вызывается методом add(E e) в классе TreeSet, верно? Может кто-нибудь предоставить более подробную информацию о точной цепочке событий, которые происходят при добавлении элемента в treeset.

Наконец, просто в качестве эксперимента я дал объекту метод compareTo(), но НЕ реализовал сопоставимый интерфейс. При попытке добавить эти объекты в TreeSet выдается исключение. Я хочу понять, почему генерируется исключение, даже если у объекта есть метод compareTo(). Я предполагаю, что где-то в алгоритме вставки есть метод, который требует, чтобы все объекты были сопоставимы, это правильно? Трассировка стека генерируемого исключения указывает на метод TreeMap.compare(). Я предполагаю, что это метод, который требует, чтобы все объекты, добавляемые в TreeSet, реализовывали сопоставимый интерфейс, но я не вижу этого метода TreeMap.compare() в API. Как я могу найти больше информации об этом методе TreeMap.compare() в API?

Заранее большое вам спасибо за вашу помощь.

1. Версия TreeSet / без аргументов TreeMap действительно использует a Comparator , в частности, компаратор естественного порядка ( Comparator.naturalOrder() в Java 8). Это означает, что тип ключа должен быть a Comparable<?> , потому что это дает понять, что экземпляры класса можно сравнивать друг с другом.

2. Java является строго типизированным языком, что означает, что типы переменных имеют приоритет над тем, какие методы он содержит. Если кто-то решит переименовать compareTo метод в вашем классе через несколько лет, не понимая, что он используется в Comparable контексте (что вполне правдоподобно, если это большая система), это приведет к боли и страданиям. implements Comparable<?> Объявление делает это намерение ясным с самого начала.

Пожалуйста, посмотрите TreeMap исходный код. В частности, переход к строке 2039 . Это исходный код, который соответствует версии 8 обновление 40 Java.

Там вы можете рассмотреть всю красно-черную механику. В принципе, это более или менее так, как вы предложили: методы записи запускают перебалансировку узлов дерева.

Что касается compareTo метода, элементы TreeSet / TreeMap должны реализовывать Comparable интерфейс. compareTo Для этого недостаточно реализации метода, элементы должны быть явным подтипом Comparable .