Конспект получился довольно громоздким, поэтому разделил его на две части. Во второй части собраны ответы на вопросы касательно канкаренси и многопоточности. В первой части остальные.
Написание далось довольно-таки тяжело. Многого все равно не понимаю, поэтому как всегда, комментарии, замечания, дополнения - приветствуются)
obj. В отличие от метода
1. Как пользоваться интерфейсом Comparable?
В интерфейсеComparable
объявлен всего один метод compareTo(Object obj)
, предназначенный для реализации упорядочивания объектов класса. Его удобно использовать при сортировке упорядоченных списков или массивов объектов.
Данный метод сравнивает вызываемый объект с equals
, который возвращает true или false, compareTo
возвращает:
- 0, если значения равны;
- Отрицательное значение, если вызываемый объект меньше параметра;
- Положительное значение , если вызываемый объект больше параметра.
java.util.List
) и массивов объектов. Если список/массив содержит элементы, реализующие этот интерфейс, то они могут быть отсортированы автоматически методами java.util.Collections.sort(List)/Arrays.sort(Object[])
.
С интерфейсом Comparable
связано понятие натурального упорядочивания, потому как он устанавливает натуральный порядок следования экземпляров любого класса, реализующего этот интерфейс. Иначе говоря, порядок (x, y) соответствует выполнению условия x.compareTo(y) <= 0
.
Правила реализации Comparable
, а вернее, его метода compareTo(Object)
следующие (x и y – экземпляры класса, реализующего Comparable
):
x.compareTo(y)
возвращает -1 или 1, если x должен находиться, соответственно, раньше или позже y. Если метод возвращает 0, то порядки (x, y) и (y, x) эквивалентны.- Если
sign(a)
– функция, возвращающая -1,0,1 для а, соответственно, меньше 0, равного 0 и больше 0, то должно выполняться равенствоsign(x.compareTo(y))==-sign(y.compareTo(x))
. Что логично: если x идет раньше y, то y должен идти позже x, и наоборот. - Если
x.compareTo(y) > 0
иy.compareTo(z) > 0
, тоx.compareTo(z) > 0
– соотношение транзитивности неравенств. - Если
x.compareTo(y) == 0
, тоsign(x.compare(z)) == sign(y.compareTo(z))
, для любых z. - Вызов
x.compareTo(null)
должен бросать исключениеNullPointerException
. В этом есть расхождение с логикой реализацииequals
(напомню,x.equals(null)
возвращает false). - Если y по своему типу не может быть сравнен с x, то вызов
x.compareTo(y)
должен бросать исключениеClassCastException
. (x.compareTo(y) == 0) == x.equals(y)
, т.е. вызовx.compareTo(y)
должен возвращать 0 тогда и только тогда, когдаx.equals(y)
возвращает true. Это правило непротиворечивости, и его очень важно учитывать.
- Сортировка и упорядочивание. Интерфейсы Comparable и Comparator
- Упорядочивание – интерфейс java.lang.Comparable
2. Как пользоваться интерфейсом Comparator?
В интерфейсеComparator
объявлено два метода compare(Object obj1, Object obj2)
и equals(Object obj)
.
При использовании интерфейса Comparator
, логика сравнения пары объектов не прячется внутрь класса/объекта, а реализуется в отдельном классе.
Метод compare(x,y)
в точности соответствует по своей сути вызову x.compareTo(y)
. Точно так же должны выполняться все правила, что и правила для реализации метода compareTo(Object)
интерфейса Comparable
.
Comparator
может использоваться в любом месте, где нужна сортировка. При этом, во-первых, появляется необходимая гибкость – возможность реализации нескольких правил сортировки. А во-вторых, сортируемые объекты могут не реализовывать интерфейс Comparable
. В случае, если они его все-таки реализуют, Comparator
имеет приоритет.
Интерфейс Comparator
определяет еще и метод equals(Object)
, как это ни парадоксально. Этот метод служит для сравнения самих экземпляров интерфейса Comparator
и должен возвращать true только в том случае, если сравниваемые объекты обеспечивают одинаковый порядок сортировки. Однако всегда безопасно оставлять исходную реализацию Object.equals(Object)
нетронутой
Источник:
- Сортировка и упорядочивание. Интерфейсы Comparable и Comparator
- Упорядочивание – интерфейс java.lang.Comparable
3. Какие методы есть у класса Collections?
public static <T> boolean addAll(Collection<? super T> c, T... elements)
Метод добавляет элементы массива elements
в коллекцию Collection<? super T> c
. Элементы могут быть указаны по одиночке, либо как массив. Когда элементы указанны по отдельности данный метод предоставляет возможность удобно добавить все элементы в имеющуюся коллекцию:
Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
Оба метода ищут в списке переданном в параметре объект переданный в параметре используя алгоритм двоичного поиска. Возвращают индекс элемента, если такой элемент в списке есть, иначе индекс первого элемента списка большего key
, если все элементы меньше key
, возвращает list.size()
.
Перед использованием данных методов списки должны быть отсортированы. В первом случае отсортированы по возрастанию в "естественном" порядке следования элементов списка (такой же, как при использовании Collections.sort(list)
). Во втором случае список должен быть отсортирован по возрастанию в порядке следования, который обеспечивает переданный компаратор (такой же порядок, как при использовании Collections.sort(list, c)
[здесь "с" - компаратор из параметров описываемого метода])
public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type)
Преамбула: механизм дженериков в языке обеспечивает проверку типов во время компиляции. Обычно этого и достаточно, однако бывают случаи, когда все-таки нет. К примеру мы нашу коллекцию передаем в код библиотеки, куда-нибудь на сторону, нам неизвестную, и нам очень сильно хочется, чтоб код этой "third-party library" не вставил в нашу коллекцию элемент неправильного типа. Это вот возможная проблема номер 1.
Возможная проблема номер 2 следующая. Предположим наша программа выдает нам ClassCastException
, который оповещает нас о том, что в коллекцию был вставлен элемент неправильного типа. К сожалению данное исключение может вылететь в любой момент, после того, как неправильный элемент был вставлен, и обычно предоставляет нам совсем немного или вообще ноль информации об источнике проблемы.
Используя метод метод checkedCollection
мы можем избавить себя от проблемы один и два, т.к. этот метод создает коллекцию проверяемую на этапе выполнения.
Решение проблемы номер два, с помощью данного метода: К примеру мы имеем вот это, и у нас вываливается ClassCastException
.
Collection<String> c = new HashSet<String>();
Код выше можно временно заменить на:
Collection<String> c = Collections.checkedCollection(
new HashSet<String>(), String.class);
При запуске программы снова мы локализуем строку кода, которая вставляет элемент неправильного типа в нашу коллекцию.
Родственные на мой взгляд методы:
public static <E> List<E> checkedList(List<E> list,Class<E> type)
public static <K,V> Map<K,V> checkedMap(Map<K,V> m, Class<K> keyType,Class<V> valueType)
public static <E> Set<E> checkedSet(Set<E> s,Class<E> type)
public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K,V> m,Class<K> keyType,Class<V> valueType)
public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,Class<E> type)
public static <T> void copy(List<? super T> dest,List<? extends T> src)
Метод копирует элементы src в dest. индексы у копированных элементов будут совпадать.
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll,Comparator<? super T> comp)
public static <T> T max(Collection<? extends T> coll,Comparator<? super T> comp)
методы возвращают минимальный\максимальный элемент в коллекции с точки зрения "естественного порядка"(интерфейс Comparable) либо порядка переданного компаратора.
public static boolean disjoint(Collection<?> c1,Collection<?> c2)
Возвращает true если у коллекций нет одинаковых элементов.
<T> List <T> emptyList(), <K,V> Map <K,V> emptyMap(),
<T> Set <T> emptySet()
– возвращают пустой список, карту отображения
и множество соответственно;
<T> void fill(List<? super T> list, T obj)
– заполняет список заданным элементом ;
int frequency(Collection<?> c, Object o)
– возвращает количество вхождений в коллекцию заданного элемента;
<T> List <T> nCopies(int n, T o)
– возвращает список из n заданных элементов;
<T> boolean replaceAll(List<T> list, T oldVal, T newVal)
– заменяет все заданные элементы новыми;
void reverse(List<?> list)
– “переворачивает” список;
void rotate(List<?> list, int distance)
– сдвигает список циклически на заданное число элементов;
void shuffle(List<?> list)
– перетасовывает элементы списка;
<T> Set <T> singleton(T o), singletonList(T o), singletonMap(K key, V value)
– создают множество, список и карту отображения, состоящие из одного элемента;
<T extends Comparable<? super T>> void sort(List<T> list),
<T> void sort(List<T> list, Comparator<? super T> c)
– сортировка списка, естественным порядком и используя Comparator
соответственно;
void swap(List<?> list, int i, int j)
– меняет местами элементы списка стоящие на заданных позициях.
Источники:
4. Какие методы есть у класса Arrays?
Полный перечень методов класса Arrays можно увидеть в документации. В данном конспекте приведу лишь некоторые из них. [переводил методы из документации, и к сожалению потерял большую часть своего перевода. Обидно, и тратить время на тоже самое не хочется, так что вставлю нагугленное]public static <T> List<T> asList(T... a)
формирует список на основе массива. Массив при этом используется для внутреннего представления списка. Таким образом сохраняется связь между списком и исходным массивом:
изменения в массиве отразятся на списке:
String[] a = { "foo", "bar", "baz"};
List<String> list = Arrays.asList(a);
System.out.println(list); // [foo, bar, baz]
a[0] = "aaa";
System.out.println(list); // [aaa, bar, baz]
изменения в списке отразятся на массиве:
String[] a = { "foo", "bar", "baz"};
List<String> list = Arrays.asList(a);
System.out.println(list); // [foo, bar, baz]
list.set(0, "bbb");
System.out.println(Arrays.toString(a)); // [bbb, bar, baz]
Если массив содержит объекты, очевидно, и массив и список будут ссылаться на одни и те же экземпляры:
Object[] a = { new Object(), new Object(), new Object()};
List<Object> list = Arrays.asList(a);
System.out.println(a[0] == list.get(0)); // true
int binarySearch(параметры)
– перегруженный метод организации бинарного поиска значения в массивах примитивных и объектных типов. Возвращает позицию первого совпадения;
void fill(параметры)
– перегруженный метод для заполнения массивов значениями различных типов и примитивами;
void sort(параметры) – перегруженный метод сортировки массива или его части с использованием интерфейса Comparator и без него;
static <T> T[] copyOf(T[] original, int newLength)
–заполняет массив определенной длины, отбрасывая элементы или заполняя null при необходимости;
static <T> T[] copyOfRange(T[] original, int from, int to)
– копирует заданную область массива в новый массив;
<T> List<T> asList(T… a)
– метод, копирующий элементы массива в объект типа List<T>.
Источник:
5. Как называется сортировка, которая используется при вызове Collections.sort()?
Из документации: Реализация является адаптированным вариантом сортировки списка для Python Тима Петерса (TimSort). Данная реализация сбрасывает список в массив, сортирует массив, затем проходит по списку и перезагружает каждый элемент списка из соответствующего элемента массива. Это позволяет избежать сложности n*n log(n), которая возникла бы при попытки отсортировать связный список напрямую Из вики: Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. В настоящее время Timsort является стандартным алгоритмом сортировки в Python, OpenJDK 7 и реализован в Android JDK 1.5. Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки.10. Что такое итератор?
Представленный в релизе JDK 1.2 языка Java интерфейсjava.util.Iterator
обеспечивает итерацию контейнерных классов. Каждый Iterator реализует методы next()
и hasNext()
и дополнительно может поддерживать метод remove()
. Итераторы создаются соответствующими контейнерными классами, как правило методом iterator()
.
Метод next()
переводит итератор на следующее значение и возвращает указываемое значение итератору. При первоначальном создании итератор указывает на специальное значение, находящееся перед первым элементом, поэтому первый элемент можно получить только после первого вызова next()
. Для определения момента, когда все элементы в контейнере были перебраны, используется тестовый метод hasNext()
. Следующий пример демонстрирует простое использование итераторов:
Iterator iter = list.iterator();
//Iterator<MyType> iter = list.iterator(); в J2SE 5.0
while (iter.hasNext())
System.out.println(iter.next());
Для коллекции типов, поддерживающей подобное, метод итератора remove()
удаляет последний 'посещенный' элемент из контейнера. Почти все остальные типы модификации контейнера во время итерации являются небезопасными.
Кроме того, для java.util.List
существует java.util.ListIterator
со схожим API, но позволяющем прямую и обратную итерации, обеспечивая определение текущего индекса в списке и переход к элементу по его позиции.
Источник:
Часть 2
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ