Интерфейс

Перевод:

Глава 1. Интерфейс

Оригинал: Chapter 1 Interfaces (http://greenteapress.com/thinkdast/html/thinkdast002.html)

Переводчик: Летающий дракон (https://github.com/wizardforcel)

Лицензия: CC BY-NC-SA 4.0 (http://creativecommons.org/licenses/by-nc-sa/4.0/)

С гордостью использую Google Translate (https://translate.google.cn/).

В этой книге рассматриваются три темы:

• Структуры данных: вы начнёте с изучения структур данных, таких как списки и карты, из Java Collection Framework (JCF), и узнаете, как они работают.

• Анализ алгоритмов: я предоставлю методы для анализа кода и прогнозирования скорости выполнения и требуемого объёма памяти.

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

Вот план тем:

• Мы начнём с интерфейса List и напишем две разные реализации этого интерфейса. Затем мы сравним вашу реализацию с классами ArrayList и LinkedList в Java.

• Далее я представлю древовидные структуры данных, и вы будете работать над первым приложением: программой, которая считывает страницы из Википедии, анализирует содержимое и обходит созданное дерево для поиска ссылок и других характеристик. Мы будем использовать эти инструменты для проверки гипотезы «достижения философии» (вы можете прочитать http://thinkdast.com/getphil, чтобы узнать больше).

• Затем мы рассмотрим интерфейс Map в Java и его реализацию HashMap. После этого вы будете использовать хеш-таблицы и бинарные деревья поиска для написания классов, реализующих этот интерфейс.

• Наконец, вы будете использовать эти (и некоторые другие классы, которые я представил ранее) для создания веб-поисковой системы, включающей в себя: сканер для поиска и чтения страниц, индексатор для хранения содержимого веб-страниц для эффективного поиска и поисковик, который принимает запросы от пользователей и возвращает релевантные результаты.

Давайте начнём.

1.1 Почему два вида List?

Когда люди начинают использовать Java Collection Framework, иногда возникает путаница между ArrayList и LinkedList. Почему Java предоставляет две реализации интерфейса List? Как выбрать, какой из них использовать? В следующих главах мы ответим на эти вопросы.

Я начну с обзора интерфейсов и их реализаций, а также представлю концепцию «программирования, ориентированного на интерфейсы».

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

1.2 Интерфейсы в Java

Интерфейс Java определяет набор методов, и любой класс, реализующий этот интерфейс, должен предоставить эти методы. Например, вот исходный код Comparable, определённого в пакете java.lang:

public interface Comparable<T> {
    public int compareTo(T o);
}

Этот интерфейс использует параметр типа T, что делает Comparable универсальным типом. Чтобы реализовать этот интерфейс, класс должен:

• Определить тип T.
• Предоставить метод с именем compareTo, принимающий объект в качестве параметра и возвращающий int.

Например, вот исходный код java.lang.Integer:

public final class Integer extends Number implements Comparable<Integer> {

    public int compareTo(Integer anotherInteger) {
        int thisVal = this.value;
        int anotherVal = anotherInteger.value;
        return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
    }

    // other methods omitted
}

Примечание переводчика: Согласно документации Comparable, нет необходимости делать это так сложно, достаточно просто вернуть this.value — that.value.

Этот класс расширяет Number, поэтому он наследует методы и переменные экземпляра Number; он реализует Comparable, поэтому он предоставляет метод с именем compareTo, который принимает Integer и возвращает int.

Когда класс объявляет, что он реализует интерфейс, компилятор проверяет, предоставил ли он все методы, определённые в интерфейсе.

Кроме того, реализация compareTo использует «тернарный оператор», иногда записываемый как ?: Если вы не знакомы с ним, вы можете прочитать http://thinkdast.com/ternary.

1.3 Интерфейс List

Java Collection Framework (JCF) определяет интерфейс под названием List и предоставляет две его реализации: ArrayList и LinkedList.

Этот интерфейс определяет, что такое List; любая реализация этого интерфейса должна предоставлять набор определённых методов, включая add, get, remove и около 20 других.

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

Это искусственный пример, демонстрирующий эту точку зрения:

public class ListClientExample {
    private List list;
    
    public ListClientExample() {
        list = new LinkedList();
    }

    private List getList() {
        return list;        
    }

    public static void main(String[] args) {
        ListClientExample lce = new ListClientExample();
        List list = lce.getList();
        System.out.println(list);
    }
}

ListClientExample не содержит ничего полезного, но он инкапсулирует List и имеет основные элементы класса. То есть он содержит переменную экземпляра List. Я буду использовать этот класс, чтобы выразить эту идею, и затем вы будете использовать его в первом упражнении.

Создавая новый LinkedList, конструктор ListClientExample инициализирует список; метод чтения называется getList и возвращает ссылку на внутренний объект List; и main содержит несколько строк кода для тестирования этих методов.

Суть этого примера заключается в том, что он максимально использует List и избегает указания LinkedList, ArrayList или любого другого конкретного типа списка, если только это не необходимо. Например, переменная экземпляра объявлена как List, и getList возвращает List, но оба не указывают конкретный тип списка.

Если вы решите использовать ArrayList, вам нужно будет изменить только конструктор; вам не нужно вносить никаких других изменений.

Такой стиль программирования называется «программирование, основанное на интерфейсах» или, более свободно, «программирование, ориентированное на интерфейсы» (см. http://thinkdast.com/interbaseprog). Здесь мы обсуждаем общую идею интерфейсов, а не конкретные интерфейсы Java.

При использовании библиотеки ваш код зависит только от чего-то вроде «списка», интерфейса. Он не должен зависеть от конкретной реализации, такой как ArrayList. Таким образом, если реализация изменится в будущем, код, использующий её, всё равно будет работать.

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

1.4 Упражнение 1

Поскольку это первое упражнение, мы оставим его простым. Вы возьмёте код из предыдущего раздела и поменяете реализацию, то есть замените LinkedList на ArrayList. Поскольку мы занимаемся программированием, ориентированным на интерфейсы, вы сможете поменять реализацию, изменив одну строку и добавив оператор import.

Начните с настройки вашей среды разработки. Для всех упражнений вам потребуется возможность компилировать и запускать Java-код. Я использовал JDK7 для разработки примеров. Если вы используете более новую версию, все должно по-прежнему работать нормально. Если вы используете старую версию, некоторые вещи могут быть несовместимы.

Я рекомендую использовать интерактивную среду разработки (IDE) для получения синтаксической проверки, автозаполнения и рефакторинга исходного кода. Эти функции помогут вам избежать ошибок или быстро их найти. Однако, если вы готовитесь к техническому собеседованию, помните, что во время собеседования у вас не будет доступа к этим инструментам, поэтому вы также можете практиковаться в написании кода без них.

Если вы ещё не загрузили код для этой книги, обратитесь к разделу 0.1 для получения инструкций.

В каталоге с именем code вы должны найти следующие файлы и каталоги:

• build.xml — файл Ant, который упрощает компиляцию и запуск кода. В данном запросе основной язык текста — английский.

lib содержит нужные вам библиотеки (для этого упражнения это только JUnit).

• src содержит исходный код.

Если вы просмотрите src/com/allendowney/thinkdast, вы найдёте исходный код этого упражнения:

• ListClientExample.java содержит код из предыдущего раздела.
• ListClientExampleTest.java содержит один JUnit-тест для ListClientExample.

Просмотрите ListClientExample и убедитесь, что вы понимаете его назначение. Затем скомпилируйте и запустите его. Если вы используете Ant, вы можете обратиться к каталогу кода и запустить ant ListClientExample.

Вы можете получить предупреждение:

List is a raw type. References to generic type List<E> 
should be parameterized.

Чтобы этот пример оставался простым, я не учитывал указание типа элементов в списке. Если это предупреждение вас беспокоит, вы можете исправить это, заменив List или LinkedList на List или LinkedList.

Пересмотрите ListClientExampleTest. Он запускает тест, создаёт ListClientExample, вызывает getList, а затем проверяет, является ли результат ArrayList. Первоначально этот тест будет неудачным, потому что результатом будет LinkedList, а не ArrayList. Запустите этот тест и убедитесь, что он неудачный.

Обратите внимание: этот тест имеет смысл для этого упражнения, но это не очень хороший пример теста. Хорошие тесты должны проверять, соответствует ли класс требованиям интерфейса; они не должны зависеть от деталей реализации.

В ListClientExample замените LinkedList на ArrayList. Возможно, вам потребуется добавить оператор import. Скомпилируйте и запустите ListClientExample. Затем снова запустите тест. После этого изменения тест должен пройти.

Для того чтобы этот тест прошёл, вам нужно изменить только LinkedList в конструкторе ListClientExample; вам не нужно изменять все места, где встречается List. Что произойдёт, если вы это сделаете? Попробуйте заменить один или несколько List на ArrayList. Программа всё ещё может работать нормально, но теперь она «переопределена». Если вы передумаете и захотите снова поменять интерфейс, вам придётся изменить код.

Что произойдёт, если в конструкторе ListClientExample вы замените ArrayList на List? Почему нельзя создать экземпляр List?