Pagsusuri ng mga tanong at sagot mula sa mga panayam para sa developer ng Java. Bahagi 10

Kamusta! Ilang oras ang kailangan para maging master sa isang bagay? Madalas kong marinig ang isang bagay tulad ng: "Upang maging master sa anumang bagay, kailangan mong gumugol ng 10,000 oras." Isang nakakatakot na numero, hindi ba? Gayunpaman, iniisip ko kung totoo ba ito? At patuloy kong sinisikap na malaman kung ilang oras na akong namuhunan sa pag-master ng sining ng programming. At kapag tinawid ko ang mga itinatangi na 10,000 oras at naging master, mararamdaman ko ba ang pagkakaibang ito? O matagal ko na silang natapakan nang hindi ko namamalayan? Sa isang paraan o iba pa, upang maging isang programmer, hindi mo kailangang mamuhunan ng napakalaking oras. Ang pangunahing bagay ay gamitin ito nang matalino. Ang iyong pangunahing layunin ay makapasa sa panayam. At sa mga panayam para sa mga bagong dating, ang unang bagay na itatanong nila ay teorya, kaya dapat kang maging matatag dito. Sa totoo lang, kapag naghahanda para sa panayam, ang iyong gawain ay tuklasin ang lahat ng iyong mga gaps sa pangunahing teorya ng isang developer ng Java at takpan ang mga ito ng kaalaman. At ngayon tutulungan kita sa bagay na ito, dahil narito ako upang ipagpatuloy ang pagsusuri sa mga pinakasikat na tanong. Kaya't magpatuloy tayo!

89. Paano naiiba ang ArrayList sa LinkedList?

Isa ito sa mga pinakasikat na tanong kasama ang tanong tungkol sa panloob na istraktura ng HashMap . Walang isang panayam na kumpleto kung wala ito, at samakatuwid ang sagot dito ay dapat na "tumalbog sa iyong mga ngipin." Bilang karagdagan sa halata - iba't ibang mga pangalan - naiiba sila sa panloob na istraktura. Dati, sinuri namin ang panloob na istraktura ng parehong ArrayList at LinkedList , kaya hindi ako pupunta sa mga detalye ng kanilang pagpapatupad. Ipaalala ko lang sa iyo na ang ArrayList ay ipinatupad batay sa isang panloob na hanay, na tinataasan kung kinakailangan ayon sa formula:

<размерТекущегоМассива> * 3 / 2  + 1

Kasabay nito, ang LinkedList ay ipinatupad batay sa isang panloob na dobleng naka-link na listahan, iyon ay, ang bawat elemento ay may link sa nakaraan at susunod, hindi kasama ang mga halaga na simula/tapos ng listahan. Gustong itanong ng mga tao ang tanong na ito sa format na: "Alin ang mas mahusay - ArrayList o LinkedList ?", umaasang mahuli ka. Pagkatapos ng lahat, kung ituro mo ang isa sa kanila bilang isang sagot, ito ay magiging maling sagot. Sa halip, dapat mong linawin kung anong partikular na sitwasyon ang iyong pinag-uusapan - i-index ang pag-access o pagpasok sa gitna ng isang listahan. Depende sa sagot, magagawa mong ipaliwanag ang iyong pinili. Nauna kong inilarawan kung paano gumagana ang ArrayList at LinkedList sa isang sitwasyon o iba pa. Ibuod natin ito sa pamamagitan ng paglalagay sa kanila sa parehong pahina para sa paghahambing: Pagdaragdag ng elemento (idagdag)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

Итог: в LinkedList алгоритмическая сложность будет колебаться от O(1) до O(n/2). То есть, чем ближе вставка к концу or началу списка, тем она быстрее. В то же время у ArrayList она колеблется от O(1) до O(n): чем вставка ближе к концу списка, тем она быстрее. Задание element (set) Данная операция записывает элемент в указанную позицию в списке, перезаписывая предыдущий, если он есть. В LinkedList эта операция будет схожа с добавлением, т.к. самая большая сложность тут — поиск element. Перезапись element будет проходить путем перезаписывания пары ссылок, поэтому тут также алгоритмическая сложность будет колебаться от O(1) до O(n/2) в зависимости от удаленности позиции от конца or начала списка. В то время в ArrayList для этой операции по индексу будет найдена нужная ячейка, а в нее записан новый элемент. Поиск по индексу, How и данная операция, имеет алгоритмическую сложность O(1). Взять элемент по индексу (get) В LinkedList взятие element будет происходить по тому же принципу, что и поиск для других операций — в зависимости от удаленности от конца or начала, т.е. от O(1) до O(n/2). В ArrayList, How я и сказал ранее, поиск element в массиве по индексу имеет сложность O(1). Удалить элемент по индексу (remove) Для LinkedList тут тоже срабатывает его принцип действия: сперва находится элемент, а потом происходит перезаписывание ссылок — соседи element начинают ссылаться друг на друга, теряя ссылки на данный элемент, который впоследствии будет удален сборщиком мусора. То есть, алгоритмическая сложность всё такая же — от O(1) до O(n/2). Для ArrayList данная операция больше схожа с операцией добавления нового element (add). Сперва находится искомый элемент — O(1), потом он удаляется, и все элементы, которые были справа от него перемещаются на одну единицу влево, чтобы закрыть образовавшуюся брешь. Операция удаления будет иметь ту же алгоритмическую сложность, что и операция добавления — от O(1) до O(n). Чем удаление ближе к концу списка, тем меньшая у него алгоритмическая сложность. Собственно, это были все основные операции. Напоминаю: при сравнении этих двух списков вам нужно уточнить, о Howой конкретной ситуации идёт речь, и тогда уже и можно однозначно ответить на поставленный вопрос.

90. Чем отличается ArrayList от HashSet?

Если ArrayList и LinkedList можно было сравнить по операциям — где кто лучше — то с ArrayList с HashSet сравнить уже не так просто, ведь это совершенно разные коллекции. Можно сравнить одно сладкое блюдо с другим, но с мясным уже получится — больно уж они разные. Тем не менее, я попробую привести их некоторые различия:

• ArrayList реализует интерфейс List, в то время How HashSet реализует интерфейс Set;

• В ArrayList возможен доступ по индексу element: операция get имеет алгоритмическую сложность O(1), а в HashSet необходимый элемент можно получить лишь путём перебора, а это у нас от O(1) до O(n);

• ArrayList допускает присутствие дубликатов элементов. В HashSet все элементы уникальны: добавить в HashSet элемент, аналог которого уже присутствует в коллекции, не получится (проверка дубликатов ведется по hashcode, отсюда и название этой коллекции);

• ArrayList реализован с помощью внутреннего массива, а HashSet реализован с помощью внутренней HashMap;

• ArrayList поддерживает порядок вставки элементов, в то время How HashSet — это неупорядоченное множество и не поддерживает порядок элементов;

• ArrayList допускает любое количество пустых значений (null), в HashSet можно вставить лишь одно meaning null (How-ниHow, уникальность элементов).

91. Зачем в Java такое разнообразие имплементации динамического массива?

Ну, это скорее философский вопрос. Ну а зачем придумывают такое количество новых разнообразных технологий? Для удобства. Собственно, так же и с большим количеством имплементаций динамического массива. Ни одну из них нельзя назвать лучшей or идеальной. У каждой есть преимущество в Howой-то конкретной ситуации. И наша задача — знать их различия, их сильные/слабые стороны: чтобы суметь в нужной ситуации использовать самую подходящую из них.

92. Зачем в Java такое разнообразие имплементаций key-value storage?

Здесь ситуация такая же, How и с имплементациями динамического массива. Однозначно лучших нет: у каждой есть сильные и слабые стороны. И мы, конечно, должны по максимуму использовать сильные стороны. Пример: в пакете concurrent, в котором есть множество многопоточных технологий, имеются свои Concurrent коллекции. У той же ConcurrentHashMap есть преимущество в безопасности многопоточной работы с данными в сравнении с обычной HashMap, но не в многопоточной среде она проигрывает в скорости работы. Ну а имплементации, которые ни в одной из ситуаций не бывают сильнейшими, постепенно перестают использовать. Пример: Hashtable, которая изначально задумывалась How потокобезопасная HashMap, но ConcurrentHashMap превзошла ее при работе в многопоточной среде, и в итоге о Hashtable позабыли и перестали использовать.

93. Как отсортировать коллекцию элементов?

Первое, что нужно сказать, — класс element коллекции должен имплементировать интерфейс Comparable и его метод compareTo. Или же нужен класс, который имплементирует Comaprator с его методом comparator. Подробнее о них можно почитать в этом посте. Оба способа указывают, Howим образом нужно сравнивать an objectы данного типа. При сортировке это критически важно, ведь нужно понимать принцип, по которому элементы можно сравнить. В основном используется способ через имплементацию Comparable, реализуемый непосредственно в классе, который вы хотите сортировать. В то же время применение Comparator-а более редко. Скажем, вы используете класс с Howой-то библиотеки, у которого нет реализации Comparable, но вам How-то нужно будет его сортировать. Не имея возможности изменить code данного класса (кроме How расширить его), вы можете написать реализацию Comparator-а, в котором укажете, по Howому принципу нужно сравнивать an objectы данного класса. И еще один пример. Допустим, вам нужны разные принципы сортировки an objectов одного и того же типа, поэтому вы пишете несколько Comparator-ов которые используете в разных ситуациях. Как правило, многие классы из коробки уже реализуют интерфейс Comparable — тот же String. Собственно, при их использовании вам не нужно париться, How их сравнить. Вы просто берете и используете их. Первый и самый очевидный способ — использовать коллекцию типа TreeSet or TreeMap, которые хранят элементы в ужеотсортированном порядке, согласно компаратору класса элементов. Не забывайте, что TreeMap сортирует ключи, но не значения. Если вы используете имплементацию Comparator instead of Comparable, вам нужно будет передать его an object в конструктор коллекции при создании:

TreeSet treeSet = new TreeSet(customComparator);

А что если у вас коллекция другого типа? Как её отсортировать? В этом случае подходит второй способ утorтного класса Collections — метод sort(). Он статический, поэтому всё, что вам нужно — Name класса и метод, в который передается необходимый список. Например:

Collections.sort(someList);

Если вы используете не Comparable, а реализацию Comparator, его нужно передать вторым параметром:

Collections.sort(someList, customComparator);

В итоге внутренний порядок элементов переданного списка изменится: он будет отсортирован согласно компаратору элементов. Отмечу, что передаваемый список элементов должен быть мутабельным, т.е. изменяемым, иначе метод не сработает и будет выброшено UnsupportedOperationException. В качестве третьего способа можно использовать Stream операцию sort, которая сортирует элементы коллекции, если используется имплементация Comparable:

someList = someList.stream().sorted().collect(Collectors.toList());

если Comparator:

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

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

Class Object. Equals and HashCode

94. Дайте краткую характеристику class object в Java

Во второй части разбора мы уже говорor о методах класса Object, и я напомню, что класс Object — прародитель всех классов в Java. У него есть 11 методов, которые, соответственно, наследуются всеми классами. Информацию обо всех 11 методах можно найти во второй части разбора вопросов.

95. Для чего используют Equals и HashCode в Java?

hashCode() — это метод класса Object, который наследуется всеми классами. Его задача — генерирование некоторого числа, которое представляет конкретный an object. Примером использования данного метода может служить его применение в HashMap на an objectе ключа для дальнейшего определения локального хешcodeа, по которому определится ячейка внутреннего массива (бакета), в которой будет сохранена пара. Подробно о работе HashMap мы говорor в 9 части разбора, поэтому особо останавливаться на этом не будем. Также How правило данный метод используется в методе equals() How один из его основных инструментов определения идентичности an objectов. equals() — метод класса Object, задача которого — сравнивать an objectы и определять, равны они or нет. Данный метод используется повсеместно там, где нам необходимо сравнить an objectы, ведь обычное сравнение через == не подходит для an objectов, т.к. сравнивает только ссылки на них.

96. Расскажите про контракт между Equals и HashCode в Java?

Первое, что скажу — для корректной работы методов equals() и hashCode() их нужно правильно переопределить. После этого они должны соблюдать правила:

• одинаковые an objectы, для которых сравнение через equals возвращает true, обязательно имеют одинаковые хеш-codeы;
• an objectы с одинаковыми хеш-codeами не всегда могут быть равны.

На этом мы и сделаем паузу до следующей части разбора!