![Уровень 26. Ответы на вопросы к собеседованию по теме уровня. Часть 1. Вопросы 1-5, 10. - 1]()
Конспект получился довольно громоздким, поэтому разделил его на две части. Во второй части собраны ответы на вопросы касательно канкаренси и многопоточности. В первой части остальные.
Написание далось довольно-таки тяжело. Многого все равно не понимаю, поэтому как всегда, комментарии, замечания, дополнения - приветствуются)
1. Как пользоваться интерфейсом Comparable?
В интерфейсе
Comparable объявлен всего один метод
compareTo(Object obj), предназначенный для реализации упорядочивания объектов класса. Его удобно использовать при сортировке упорядоченных списков или массивов объектов.
Данный метод сравнивает вызываемый объект с
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. Это правило непротиворечивости, и его очень важно учитывать.
Источники:
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) нетронутой
Источник:
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);
a[0] = "aaa";
System.out.println(list);
изменения в списке отразятся на массиве:
String[] a = { "foo", "bar", "baz"};
List<String> list = Arrays.asList(a);
System.out.println(list);
list.set(0, "bbb");
System.out.println(Arrays.toString(a));
Если массив содержит объекты, очевидно, и массив и список будут ссылаться на одни и те же экземпляры:
Object[] a = { new Object(), new Object(), new Object()};
List<Object> list = Arrays.asList(a);
System.out.println(a[0] == list.get(0));
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();
while (iter.hasNext())
System.out.println(iter.next());
Для коллекции типов, поддерживающей подобное, метод итератора remove() удаляет последний 'посещенный' элемент из контейнера. Почти все остальные типы модификации контейнера во время итерации являются небезопасными.
Кроме того, для java.util.List существует java.util.ListIterator со схожим API, но позволяющем прямую и обратную итерации, обеспечивая определение текущего индекса в списке и переход к элементу по его позиции.
Источник:
Часть 2
Конспект получился довольно громоздким, поэтому разделил его на две части. Во второй части собраны ответы на вопросы касательно канкаренси и многопоточности. В первой части остальные.
Написание далось довольно-таки тяжело. Многого все равно не понимаю, поэтому как всегда, комментарии, замечания, дополнения - приветствуются)