Оглавление
Предисловие............................................................................... 12
Философия книги................................................................... 12
Обязательные условия........................................................... 14
Работа с кодом ...................................................................... 15
Условные обозначения .......................................................... 16
Соавторы............................................................................... 17
Глава 1. Интерфейсы .............................................................. 19
Почему существует два типа List............................................ 20
Интерфейсы в Java ................................................................ 21
Интерфейс List....................................................................... 22
Упражнение 1........................................................................ 25
Глава 2. Анализ алгоритмов .................................................... 28
Сортировка выбором ............................................................. 30
Нотация «О» большого .......................................................... 33
Упражнение 2........................................................................ 35
Оглавление 7
Глава 3. Класс ArrayList ........................................................... 40
Классификация методов MyArrayList ...................................... 40
Классификация версий метода add ........................................ 43
Размер задачи ....................................................................... 46
Связные структуры данных .................................................... 47
Упражнение 3........................................................................ 51
Примечание о сборке мусора ................................................. 54
Глава 4. Класс LinkedList ......................................................... 56
Классификация методов MyLinkedList..................................... 56
Сравнение MyArrayList и MyLinkedList..................................... 60
Профилирование ................................................................... 61
Интерпретация результатов................................................... 65
Упражнение 4........................................................................ 67
Глава 5. Двусвязный список .................................................... 69
Результаты профилирования производительности................. 69
Профилирование производительности
методов LinkedList.................................................................. 73
Добавление в конец LinkedList............................................... 74
Двусвязный список ................................................................ 78
Выбор структуры ................................................................... 79
Глава 6. Обход дерева ............................................................ 82
Поисковые системы ............................................................... 82
Парсинг HTML........................................................................ 84
8 Оглавление
Применение jsoup.................................................................. 86
Итерация по дереву DOM....................................................... 90
Поиск в глубину..................................................................... 91
Стеки в Java........................................................................... 92
Итеративный поиск в глубину................................................ 94
Глава 7. Путь к философии ..................................................... 97
Начало разработки ................................................................ 97
Интерфейсы Iterable и Iterator ............................................... 98
WikiFetcher............................................................................101
Упражнение 5.......................................................................103
Глава 8. Индексатор ............................................................... 106
Выбор структуры данных ......................................................107
TermCounter..........................................................................109
Упражнение 6.......................................................................112
Глава 9. Интерфейс Map ........................................................ 118
Реализация MyLinearMap.......................................................118
Упражнение 7.......................................................................120
Анализ MyLinearMap..............................................................121
Глава 10. Хеширование .......................................................... 125
Хеширование ........................................................................125
Как работает хеширование ...................................................128
Хеширование и изменяемость...............................................131
Упражнение 8.......................................................................133
9
Глава 11. HashMap ................................................................. 135
Упражнение 9.......................................................................136
Анализ MyHashMap ...............................................................137
Компромиссные решения......................................................140
Профилирование MyHashMap................................................141
Исправление MyHashMap ......................................................142
Диаграммы классов UML .......................................................145
Глава 12. TreeMap .................................................................. 149
Что не так с хешированием...................................................149
Бинарное дерево поиска.......................................................151
Упражнение 10 .....................................................................154
Реализация TreeMap .............................................................155
Глава 13. Бинарное дерево поиска ........................................ 160
Простая реализация MyTreeMap............................................160
Поиск по значению...............................................................162
Реализация put.....................................................................164
Симметричный обход............................................................166
Методы, выполняющиеся за логарифмическое время ...........168
Самобалансирующиеся деревья............................................172
Дополнительное упражнение................................................173
Глава 14. Сохраняемость ....................................................... 174
Redis.....................................................................................175
Клиенты и серверы Redis ......................................................177
Оглавление
10
Создание индекса на основе Redis ........................................178
Типы данных Redis................................................................181
Упражнение 11 .....................................................................184
Дополнительные рекомендации............................................186
Несколько советов по проектированию.................................188
Глава 15. Сбор данных в «Википедии» ................................... 190
Индексатор на основе Redis ..................................................190
Анализ поиска ......................................................................194
Анализ индексирования........................................................195
Обход графа .........................................................................196
Упражнение 12 .....................................................................198
Глава 16. Логический поиск ................................................... 202
Решение для поискового робота ...........................................202
Поиск информации ...............................................................206
Логический поиск .................................................................207
Упражнение 13 .....................................................................208
Интерфейсы Comparable и Comparator ..................................211
Дополнения ..........................................................................214
Глава 17. Сортировка ............................................................. 216
Сортировка вставкой ............................................................217
Упражнение 14 .....................................................................220
Анализ сортировки слиянием................................................222
Оглавление
11
Поразрядная сортировка ......................................................226
Пирамидальная сортировка ..................................................229
Ограниченная куча ...............................................................232
Пространственная сложность................................................233
Об авторе ..................................................................................235
Об обложке ...............................................................................236
