обязательно ли классу реализовывать интерфейс comparable чтобы его можно было использовать в treeset

Русские Блоги

TreeSet, интерфейс Comparable, объект класса реализации Comparator

TreeSet, интерфейс Comparable, объект класса реализации Comparator

Один, сводка коллекции коллекции

|–LinkedList
Базовая структура данных представляет собой связанный список, который медленно запрашивает и быстро добавляет и удаляет.
Поток небезопасен и эффективен

|–TreeSet
Базовая структура данных представляет собой красно-черное дерево.
Как обеспечить сортировку элементов?
—- естественный порядок
—- Сортировка по компаратору
Как обеспечить уникальность элементов?
—- Согласно возвращаемому значению сравнения

Во-вторых, кого мы используем для сбора?

Пользовательский список

Три, коллекция TreeSet

(2) Использование настраиваемых объектов, наследует интерфейс Comparable.

b: Сортировка компаратора (коллекция является сравнительной). Разрешить методу построения коллекции получить объект класса реализации компаратора.

В-четвертых, объяснение исходного кода метода add ()

При просмотре нижний слой фактически представляет собой метод put () TreeMap.
Создать корневой узел
, чтобы узнать, есть ли интерфейс компаратора.
содержит:
сравнить корень, если меньше корня, левый узел
сравнить корень, если он больше корня, правый узел

Пять, практика

тема:
Введите с клавиатуры информацию об учащемся 5 (имя, оценка по языку, оценка по математике, оценка по языку), выведите на консоль в соответствии с общей оценкой сверху вниз

результат операции

Источник

Русские Блоги

В последнее время в процессе изучения жадного алгоритма и динамического программирования появилась естественная операция сортировки.Кстати, давайте вкратце разберемся с двумя интерфейсами, используемыми для сортировки после сравнения объектов в Java: Comparable и Comparator. Если это число, просто сравните его напрямую, а если это объект, как отсортировать его после сравнения? Вам необходимо использовать эти два интерфейса и передать самоопределяемый класс в качестве параметра универсальному интерфейсу, переопределить метод сравнения в интерфейсе и добавить атрибуты класса, которые вы хотите выбрать и отсортировать, в условия сравнения.

Основное отличие интерфейса

(1) Интерфейс Comparable находится под java.lang, а интерфейс Comparator находится под java.lang.

(2) Если интерфейс Comparable реализован, когда класс определен, метод compareTo () прямо переопределяется в нем. Если он не реализован, на более поздних этапах развития бизнеса требуется функция относительной сортировки, а затем отдельный класс будет написан для реализации интерфейса Comparator., Перепишите внутри метод compare (), а затем этот класс необходимо передать в качестве параметра методам collections.sort и Arrays.sort класса инструмента.

(3) Класс, реализующий интерфейс Comparable, должен иметь естественный порядок, а другой не является обязательным условием.

Использовать сопоставимый

(1) При определении класса реализации реализуйте интерфейс Comparable.

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

В выводе консоли обнаруживается, что обычная сортировка осуществляется по зарплате, то есть по возрастанию.

Использовать компаратор

При использовании этого интерфейса вам не нужно реализовывать интерфейс при создании класса, вам нужно создать отдельный класс для реализации этого интерфейса.

(2) Создайте класс, реализующий интерфейс, и перепишите в нем метод сравнения. Это способ использования универсальных шаблонов в интерфейсах, то есть того, что является универсальным для интерфейса, а что является универсальным в реализующем классе.

Протестируйте класс, чтобы убедиться, что он отсортирован в соответствии с вашими требованиями.

Из вывода консоли видно, что первая сортировка обратная по возрасту.Когда она сортируется на clyang и herry, поскольку возраст совпадает, она продолжает сортировку по возрастанию в соответствии с зарплатой.

Выше приведены методы использования двух интерфейсов, которые также можно узнать, обратившись к статье блоггера, и которые могут быть использованы в будущем.

Источник

Руководство по TreeSet на Java

Быстрое и практическое введение в TreeSet на Java.

1. Обзор

2. Введение в TreeSet

Проще говоря, TreeSet это отсортированная коллекция, которая расширяет АбстрактСет класса и реализует Навигационаясеть интерфейс.

Вот краткое изложение наиболее важных аспектов этой реализации:

Проще говоря, будучи самобалансирующимся двоичным деревом поиска, каждый узел двоичного дерева состоит из дополнительного бита, который используется для определения цвета узла, который является либо красным, либо черным. Во время последующих вставок и удалений, эти “цветные” биты помогают гарантировать, что дерево остается более или менее сбалансированным.

Итак, давайте создадим экземпляр TreeSet :

2.1. TreeSet со конструктором-компаратором Param

По желанию мы можем построить TreeSet с конструктором, который позволяет нам определить порядок, в котором элементы сортируются с помощью Сопоставимые или компаратор:

хотя TreeSet не является безопасным потоком, он может быть синхронизирован внешне с помощью Collections.synchronizedSet() обертка:

Хорошо, теперь, когда у нас есть четкое представление о том, как создать TreeSet например, давайте посмотрим на общие операции, которые у нас есть.

3. TreeSet добавить ()

Давайте добавим элемент в TreeSet :

Переменная м относится к внутреннему резервному TreeMap (Обратите внимание, что TreeMap реализует НавигацияМап ):

Таким образом, TreeSet внутренне зависит от поддержки Навигационая карта который инициализируется с экземпляром TreeMap когда экземпляр TreeSet создается:

4. TreeSet содержит ()

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

Посмотрим на содержит () в действии:

5. TreeSet удалить ()

тем удалить () метод используется для удаления указанного элемента из набора, если он присутствует.

Если набор содержал указанный элемент, этот метод возвращается истинный.

Давайте посмотрим его в действии:

6. TreeSet ясно ()

Если мы хотим удалить все элементы из набора, мы можем использовать ясно () метод:

7. Размер TreeSet ()

8. TreeSet isEmpty ()

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

9. Итератор TreeSet ()

Мы можем наблюдать восходящий порядок итерации здесь:

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

Давайте посмотрим, что в действии:

тем итератор бросает ПараллельноМодификацияИсключение i f набор изменяется в любое время после того, как итератор создается любым способом, за исключением удалить () метод.

Давайте создадим тест для этого:

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

Там нет гарантии на отказ быстрое поведение итератора, как это невозможно сделать какие-либо жесткие гарантии в присутствии несинхронизированных параллельной модификации.

10. TreeSet первый ()

11. TreeSet последний ()

Аналогично приведенного выше примера, этот метод вернет последний элемент, если набор не пуст:

12. Подсеть TreeSet ()

Этот метод будет возвращать элементы, начиная от отЭлемент toЭлемент. Обратите внимание, что отЭлемент является инклюзивным и toЭлемент является эксклюзивным:

13. Глава TreeSet ()

Этот метод вернет элементы TreeSet которые меньше указанного элемента:

14. Хвост TreeSet()

Этот метод вернет элементы TreeSet которые больше или равны указанному элементу:

15. Хранение нулевых элементов

До Java 7 можно было добавить нулевой элементы пустого TreeSet.

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

Когда мы добавляем элементы в TreeSet, элементы сортируются в соответствии с их естественным порядком или в соответствии с компаратор. Таким образом, нулевой, по сравнению с существующими элементами, приводит к NullPointerЭксцепция с нулевой не может сравниться с любым значением:

Элементы, вставленные в TreeSet должны либо реализовать Сопоставимые интерфейс или, по крайней мере, быть принятым указанным компаратором. Все такие элементы должны быть взаимосопоставимыми, т.е. e1.compareTo(e2) или comparator.compare (e1, e2) не должны бросать ClassCastException .

16. Производительность TreeSet

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

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

Когда мы говорим местности:

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

В случае, если данные должны быть прочитаны с жесткого диска (который имеет большую задержку, чем данные, читаемые из кэша или памяти), то предпочитают TreeSet так как она имеет большую локализацию

17. Заключение

В этой статье мы сосредоточимся на понимании того, как использовать стандартные TreeSet реализации в Java. Мы видели его назначение и насколько эффективно оно в отношении удобство использования, учитывая его способность избегать дубликатов и сортировать элементы.

Источник

Comparable и Comparator

Два новых интерфейса java.lang.Comparable и java.util.Comparator были добавлены в версии Java 5. Использование данных интерфейcов в своих приложениях позволяет упорядочивать (сортировать) данные.

Интерфейс Comparable

В интерфейсе Comparable объявлен только один метод compareTo (Object obj), предназначенный для упорядочивания объектов класса. Данный метод удобно использовать для сортировки списков или массивов объектов.

Метод compareTo (Object obj) сравнивает вызываемый объект с obj. В отличие от метода equals, который возвращает true или false, compareTo возвращает:

Если типы объектов не совместимы при сравнении, то compareTo (Object obj) может вызвать исключение ClassCastException. Необходимо помнить, что аргумент метода compareTo имеет тип сравниваемого объекта класса.

Обычные классы Byte, Short, Integer, Long, Double, Float, Character, String уже реализуют интерфейс Comparable.

Пример реализации интерфейса Comparable

Результат выполнения программы:

В примере значения сортируются сначала по полю str (по алфавиту), а затем по num в методе compareTo. Это хорошо видно по двум строкам с одинаковыми значения str и различными num. Чтобы изменить порядок сортировки значения str (в обратном порядке), необходимо внести небольшие изменения в метод compareTo.

Интерфейс Comparator : compare, compareTo

В интерфейсе Comparator объявлен метод compare (Object obj1, Object obj2), который позволяет сравнивать между собой два объекта. На выходе метод возвращает значение 0, если объекты равны, положительное значение или отрицательное значение, если объекты не тождественны.

Метод может вызвать исключение ClassCastException, если типы объектов не совместимы при сравнении. Простой пример реализации интерфейса Comparator:

Результат выполнения программы:

Усложним пример, и реализуем несколько видов сортировки. Для этого создадим класс Product с полями name, price и quantity.

Создадим два класса (SortedByName, SortedByPrice), реализующих интерфейс Comparator для сортировки объектов по названию и по цене :

Пример использования Arrays.sort :

Результат выполнения программы:

Для сортировки объектов были реализованы два независимых компаратора по наименованию и по цене (SortedByName и SortedByPrice). Сортировка выполняется с помощью класса Arrays, у которого есть метод sort. Данный метод в качестве второго аргумента принимает тип компаратора.

Можно использовать также метод sort класса Collections, который в качестве первого входного аргумента принимает список объектов:

Отличие интерфейсов Comparator и Comparable

Интерфейс Comparable используется только для сравнения объектов класса, в котором данный интерфейс реализован. Т.е. interface Comparable определяет логику сравнения объекта определенного ссылочного типа внутри своей реализации (по правилам разработчика).

Comparator представляет отдельную реализацию и ее можно использовать многократно и с различными классами. Т.е. interface Comparator позволяет создавать объекты, которые будут управлять процессом сравнения (например при сортировках).

Источник

Собеседование по Java — коллекции (Collections) (вопросы и ответы)

Список вопросов и ответов по теме “Коллекции в Java”.

К списку вопросов по всем темам

Вопросы

1. Дайте определение понятию “коллекция”.
2. Назовите преимущества использования коллекций.
3. Какие данные могут хранить коллекции?
4. Какова иерархия коллекций?
5. Что вы знаете о коллекциях типа List?
6. Что вы знаете о коллекциях типа Set?
7. Что вы знаете о коллекциях типа Queue?
8. Что вы знаете о коллекциях типа Map, в чем их принципиальное отличие?
9. Назовите основные реализации List, Set, Map.
10. Какие реализации SortedSet вы знаете и в чем их особенность?
11. В чем отличия/сходства List и Set?
12. Что разного/общего у классов ArrayList и LinkedList, когда лучше использовать ArrayList, а когда LinkedList?
13. В каких случаях разумно использовать массив, а не ArrayList?
14. Чем отличается ArrayList от Vector?
15. Что вы знаете о реализации классов HashSet и TreeSet?
16. Чем отличаются HashMap и TreeMap? Как они устроены и работают? Что со временем доступа к объектам, какие зависимости?
17. Что такое Hashtable, чем она отличается от HashMap? На сегодняшний день она deprecated, как все-таки использовать нужную функциональность?
18. Что будет, если в Map положить два значения с одинаковым ключом?
19. Как задается порядок следования объектов в коллекции, как отсортировать коллекцию?
20. Дайте определение понятию “итератор”.
21. Какую функциональность представляет класс Collections?
22. Как получить не модифицируемую коллекцию?
23. Какие коллекции синхронизированы?
24. Как получить синхронизированную коллекцию из не синхронизированной?
25. Как получить коллекцию только для чтения?
26. Почему Map не наследуется от Collection?
27. В чем разница между Iterator и Enumeration?
28. Как реализован цикл foreach?
29. Почему нет метода iterator.add() чтобы добавить элементы в коллекцию?
30. Почему в классе iterator нет метода для получения следующего элемента без передвижения курсора?
31. В чем разница между Iterator и ListIterator?
32. Какие есть способы перебора всех элементов List?
33. В чем разница между fail-safe и fail-fast свойствами?
34. Что делать, чтобы не возникло исключение ConcurrentModificationException?
35. Что такое стек и очередь, расскажите в чем их отличия?
36. В чем разница между интерфейсами Comparable и Comparator?
37. Почему коллекции не наследуют интерфейсы Cloneable и Serializable?

Ответы

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

1. Дайте определение понятию “коллекция”.

Коллекциями/контейнерами в Java принято называть классы, основная цель которых – хранить набор других элементов.

2. Назовите преимущества использования коллекций.

Массивы обладают значительными недостатками. Одним из них является конечный размер массива, как следствие, необходимость следить за размером массива. Другим — индексная адресация, что не всегда удобно, т.к. ограничивает возможности добавления и удаления объектов. Чтобы избавиться от этих недостатков уже несколько десятилетий программисты используют рекурсивные типы данных, такие как списки и деревья. Стандартный набор коллекций Java служит для избавления программиста от необходимости самостоятельно реализовывать эти типы данных и снабжает его дополнительными возможностями.

3. Какие данные могут хранить коллекции?

Коллекции могут хранить любые ссылочные типы данных.

4. Какова иерархия коллекций?

Здесь следует обратить внимание, что interface Map не входит в иерархию interface Collection.

С Java 1.6 классы TreeSet и TreeMap имплементируют интерфейсы NavigableSet и NavigableMap, которые расширяют интерфейсы SortedSet и SortedMap соответственно (SortedSet и SortedMap расширяют Set и Map).

Подробная статья про коллекции с описанием основных методов: http://www.quizful.net/post/Java-Collections

5. Что вы знаете о коллекциях типа List?

List — это упорядоченный список. Объекты хранятся в порядке их добавления в список. Доступ к элементам списка осуществляется по индексу.

6. Что вы знаете о коллекциях типа Set?

7. Что вы знаете о коллекциях типа Queue?

Queue — коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.

Очереди обычно, но не обязательно, упорядочивают элементы в FIFO (first-in-first-out, «первым вошел — первым вышел») порядке.

Методы element() и peek() возвращают (но не удаляют) верхушку очереди.

java.util.Queue реализует FIFO–буфер. Позволяет добавлять и получать объекты. При этом объекты могут быть получены в том порядке, в котором они были добавлены.

Подробнее http://www.seostella.com/ru/article/2012/08/09/kollekcii-collections-v-java-queue.html

8. Что вы знаете о коллекциях типа Map, в чем их принципиальное отличие?

Интерфейс java.util.Map используется для отображения каждого элемента из одного множества объектов (ключей) на другое (значений). При этом, каждому элементу из множества ключей ставится в соответствие множество значений. В то же время одному элементу из множества значений может соответствовать 1, 2 и более элементов из множества ключей. Интерфейс java.util.Map описывает функциональность ассоциативных массивов.

http://developer.alexanderklimov.ru/android/java/map.php

9. Назовите основные реализации List, Set, Map.

10. Какие реализации SortedSet вы знаете и в чем их особенность?

Реализации: java.util.TreeSet — коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n).

11. В чем отличия/сходства List и Set?

12. Что разного/общего у классов ArrayList и LinkedList, когда лучше использовать ArrayList, а когда LinkedList?

Если необходимо вставлять (или удалять) в середину коллекции много элементов, то лучше использовать LinkedList. Во всех остальных случаях – ArrayList.

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

Из лекции javarush.ru

Структуры данных в картинках. LinkedList: http://habrahabr.ru/post/127864/

13. В каких случаях разумно использовать массив, а не ArrayList?

Если коротко, то Oracle пишет — используйте ArrayList вместо массивов. Если ответить на этот вопрос нужно по-другому, то можно сказать следующее: массивы могут быть быстрее и кушать меньше памяти. Списки теряют в производительности из-за возможности автоматического увеличения размера и сопутствующих проверок. Плюс к этому, что размер списка увеличивается не на 1, а на большее кол-во элементов (+15)*. Так же доступ к [10] в массиве может быть быстрее чем вызов get(10) у списка.

*Читатель прислал комментарий «У ArrayList увеличение происходит в 1.5 раза. int newCapacity = oldCapacity + (oldCapacity >> 1);».

Структуры данных в картинках. ArrayList: http://habrahabr.ru/post/128269/

Еще о ArrayList на сайте http://developer.alexanderklimov.ru/android/java/arraylist.php

14. Чем отличается ArrayList от Vector?

Vector deprecated. У Vector некоторые методы синхронизированы и поэтому они медленные. В любом случае Vector не рекомендуется использовать вообще.

15. Что вы знаете о реализации классов HashSet и TreeSet?

HashSet реализован на основе хеш-таблицы, а TreeSet — на основе бинарного дерева.

Подробнее о Set, HashSet, LinkedHashSet, TreeSet: http://developer.alexanderklimov.ru/android/java/set.php

Годный ответ на StackOverflow http://stackoverflow.com/questions/1463284/hashset-vs-treeset

16. Чем отличаются HashMap и TreeMap? Как они устроены и работают? Что со временем доступа к объектам, какие зависимости?

В целом ответ про HashSet и TreeSet подходит и к этому вопросу.

TreeMap реализован на красно-черном дереве, время добавления/поиска/удаления элемента — O(log N), где N — число элементов в TreeMap на данный момент.

У HashMap время доступа к отдельному элементу — O(1) при условии, что хэш-функция ( Object.hashCode() ) определена нормально (что является правдой в случае Integer ).

Структуры данных в картинках. HashMap: http://habrahabr.ru/post/128017/

17. Что такое Hashtable, чем она отличается от HashMap? На сегодняшний день она deprecated, как все-таки использовать нужную функциональность?

http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable

18. Что будет, если в Map положить два значения с одинаковым ключом?

Последнее значение перезапишет предыдущее.

19. Как задается порядок следования объектов в коллекции, как отсортировать коллекцию?

В этом классе четыре конструктора:

ТгееМар() — создает пустой объект с естественным порядком элементов;
TreeМар(Comparator с) — создает пустой объект, в котором порядок задается объектом сравнения с;
ТгееМар(Map f) — создает объект, содержащий все элементы отображения f, с естественным порядком его элементов;
ТгееМар(SortedMap sf) — создает объект, содержащий все элементы отображения sf, в том же порядке.

Интерфейс Comparator описывает два метода сравнения:

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

Источник