Алгоритмы и структуры данных JDK

Периодически проверяя нет ли реализации того или иного стандартного алгоритма в jdk, пришла мысль составить подобный обзор. Также интересны были причины наличия/отсутствия многих известных структур данных.
Формат обзора — только ключевые свойства и особенности структур и алгоритмов в составе jdk, подробности и детали — расписаны в javadoc или легко найти в исходниках.
Надеюсь на конструктивную критику и коллективный разум если что упустил.
Хватит вступлений, итак, давайте рассмотрим что включает в себя текущий jdk 7 и почему.

Структуры

Стек

В jdk имеется старый стек (Stack ^[1]), который существует с момента выхода java и использовать уже не рекомендуется, он сложный и странный: наследуется от Vector ^[2], а значит построен на динамически расширяемом массиве и синхронизированный.
Зачем это все обычному стеку и почему это не интерфейс — не совсем ясно (обсуждалось не раз: 1 ^[3], 2 ^[4]), но похоже на ошибку проектирования, такую же как и сам Vector ^[2].
К тому же в самом javadoc советуют вместо него использовать Deque ^[5].

Deque ^[5] — это интерфейс (api) двухсторонней очереди ^[6](LIFO + FIFO за O(1)), который включает в себя и стековые операции (push, pop, isEmpty, size). Доступен в jdk не так давно (1.6+).
Конечно проще если бы эти стековые операции находились в интерфейсе Stack, а Deque его например наследовал бы, но поскольку Stack уже присутствовал, а обратная совместимость — это для java “наше все”, пришлось пожертвовать нормальным дизайном.
Реализации Deque — это ArrayDeque ^[7] и LinkedList ^[8], которые по совместительству также имплементируют обычную очередь, поэтому рассмотрим позже.

Очереди

Далее по порядку смотрим очереди. Здесь все хорошо, дизайн достойный.
Queue ^[9] — интерфейс (api) LIFO очереди, добавление в начало, удаление с конца за O(1).

Основные реализации — это ArrayDeque ^[7], циклический буффер ^[10] на основе динамически расширяемого массива (увеличивается вдвое при заполнении) и LinkedList ^[8], классический двусвязный список ^[11], размер не ограничен. Странным образом, первая не поддерживает случайный доступ ^[12] (add/remove/get с индексом), вторая — поддерживает но за время O(n) итерации по связному списку.
Эти же имплементации реализуют и упомянутую двустороннюю очередь, а значит удаление с конца и добавление в начало — тоже O(1).

Далее c jdk 1.5+ была добавлена PriorityQueue ^[13] которая по факту нарушает контракт очереди т.к. элементы достаются не с конца (кладутся тоже не в начало) а согласно их приоритетам.
Построена на основе расширяемой бинарной кучи ^[14], на вершине — минимальный элемент (согласно его компаратору), при заполнении увеличивается в размере в полтора раза. Соотв-но добавление/удаление — это O(log N), ссылка на минимальный (голову) — O(1).

Остальные типы очередей предназначены для многопоточного использования, это BlockingQueue, TransferQueue, ConcurrentLinkedQueue и ConcurrentLinkedDeque.

Реализации BlockingQueue ( ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue) — это своего рода синхронизированные версии их оригиналов, т.е. почти каждая операция выполняется синхронно (блокируется). Сюда же можно отнести и DelayQueue — также синхронизированная, внутри использует PriorityQueue.

В то время как SynchronousQueue, TransferQueue (LinkedTransferQueue), ConcurrentLinkedQueue, ConcurrentLinkedDeque — основаны на другом подходе: там применяются алгоритмы неблокирующей очереди на связных списках ^[15] с применением CAS ^[16] инструкций, которые хорошо распараллеливаются в многопроцессорном окружении. Подробное описание — в исходниках.
Алгоритмы такого класса довольно обширный и новый материал, еще не совсем стандартизированный и структурированный, поэтому выходит за рамки данного обзора и скорее тема для отдельной статьи.

Очереди с приоритетом (кучи)

Как уже было сказано начиная с 1.5 присутствует универсальная PriorityQueue, кроме того есть еще одна реализации кучи в jdk. Это старый добрый Timer, внутренний классик TaskQueue (на вершине — задача с минимальным временем ожидания). Естественно это закрытая реализация и кроме как внутри таймера она использоваться не может.

Списки

Как известно бывают последовательного и/или случайного доступа.
В java список — это List и 2 основные реализации, первая — это ArrayList, поддерживает случайный доступ, в основе динамически расширяемого массива ^[17] (увеличивается в полтора раза при заполнении), но при удалении элементов сам не сужается, для этого нужно вызывать предусмотренный метод (trimToSize).

И вторая — уже упомянутвый LinkedList, двусвязный список последовательного доступа, размер ограничен только свободной памятью jvm. Хотя методы случайного доступа (по индексу) тоже присутствуют — как уже было сказано, они здесь выполняются за O(n)

Простейшего односвязного списка в коллекциях java почему то нет, хотя наверное бы не помешал (в 2 раза меньше накладных расходов на ссылки), также как и простой стек.

Для использования списков в многопоточном окружении существует CopyOnWriteArrayList (операции изменения — O(n)), обертки (synchonizedList) а также устаревший Vector.

Символьные таблицы

Представлены бинарным деревом и хеш-таблицей.

Дерево — это TreeMap (TreeSet), реализация SortedMap (SortedSet соотв-но), в основе лежит классическое красно-черное дерево ^[18], т.е. сбалансированное и основные операции гарантировано за O(log N), в размерах не ограничен.

Хеш-таблица — HashMap (HashSet) наверное самая используемая структура в java, построена на динамически расширяемой хеш-таблице с цепочками ^[19], со всеми вытекающими: производительность зависит от хеш функции, в худшем случае O(N). Когда размер достигает заданного loadFactor — увеличивается вдвое.
Других типов хеш-таблиц (с открытой адресацией ^[20] и тд) в jdk нет. Деревьев — тоже.

Многопоточные версии: ConcurrentHashMap, обертка synchronizedMap, Hashtable и ConcurrentSkipListMap. Обертка — естественно просто блокирующая версия обычной HashMap, Hashtable — тоже самое, ConcurrentHashMap — lock-striping версия, позволяющая сократить критические секции (читать об этом лучше в JCiP ^[21], вот отрывок ^[22]).
ConcurrentSkipListMap — неблокирущая версия одноименного алгоритма ^[23] адаптированного для хеш-таблицы (подробнее — в исходниках).

Через хеш-таблицы реализованы и множества Set (не допускающие дубликатов), поэтому все что сказано к хеш-таблицам — справедливо для Set.

Графы

Графовые структуры и алгоритмы в jdk не представлены. Поэтому в этом случае остается использовать только сторонние библиотеки

Строки

Реализация стандартная — на основе массива unicode символов. Стоит напомнить что начиная с версии 1.7_17 производительность substring теперь O(n), поскольку подстрока копируется.

Интересно что для поиска подстроки используется алгоритм простого перебора дающий O (N*M) в худшем случае, а не какой нибудь эффективный алгоритм ^[24] построенный на конечном автомате (Knuth-Morris-Pratt и др.).
Причин несколько: во-первых опять же большой размер алфавита UTF символов (~65K), а значит большие накладные расходы на хранение конечного автомата, в то время как алгоритм перебора — in-place (не используется доп память).
И во-вторых, производительность на среднестатистических строках — в этом видимо перебор не сильно проигрывает другим алгоритмам.

Тоже самое с сортировкой. Существуют эффективные сортировки строк подсчетом ^[25] (LSD, MSD и др), но в jdk используется стандартная для объектов, дающая O(M * N * log N), если большинство строк не сильно отличаются (M — средняя длина строк).
Причина та же: сортировки подсчетом используют вспомогательные массивы размером алфавита UTF, что делает их неэффективными на среднестатических входных данных.

Алгоритмы

Сортировка

В jdk7 произошло много изменений касательно вариантов сортировок, тема обсуждалась неоднократно, информации и статей на эту тему полно, подробней могу посоветовать вот этот обзор ^[26].
В кратце, актуальный список реализаций сортировок доступных на данный момент в jdk: TimSort ^[27] — сортировка объектов по умолчанию, слиянием ^[28] — тоже для объектов, старый вариант (включаемый через системное свойство), для примитивов используется Dual-Pivot Quick sort ^[29], для байтовых/символьных массивов используется сортировка подсчетом, для небольших массивов во всех случаях используется сортировка вставками ^[30].

Cортировка коллекций Collections.sort(List ...) по прежнему делается через копирование в массив, сортировку и затем перезаписывает коллекцию. Поэтому без накладных расходов сделать это стандартными средствами нельзя, хотя наверное не помешало бы иметь in-place сортировку связных списков ^[31].

Для сортировки строк тоже используется объектная версия, причины упомянуты выше.

Поиск

Традиционный бинарный поиск ^[32] присутствует для всех массивов примитивов и объектов а также списков поддерживающих случайный доступ.

Более того в Collections присутствует версия для связных списков. Получается сортировку для связных списков делать смысла не было, но двоичный поиск понадобился, хотя смысла еще меньше поскольку производительности O (log N) там и близко нет.

Регулярные выражения

Используется традиционная реализация на основе недетерминированного конечного автомата (NFA ^[33]) и поиска с возвратом (backtracking ^[34]). Т.е. экспоненциальная сложность ^[35] O(m^N) в худшем случае на вырожденных значениях, пример:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".matches("(a|aa)*b")

Также имеет место т.н. “ordered alternation” (порядковая альтернатива?) — это когда поиск прекращается сразу после нахождения первого соответствия из нескольких а не самого специфического (длинного), пример ^[36].

Хеш-функции, контрольные суммы

Алгоритмов вычисления hashCode в jdk целых шесть, по-умолчанию используется Park-Miller_random_number_generator ^[37], подробней — недавняя статья на хабре ^[38].

Имеются также стандартные промышленные алгоритмы хеширования (SHA-*, MD5 и вариации) — MessageDigest ^[39]

Для вычисления контрольных сумм присутствуют еще реализации алгоритмов Adler-32 ^[40] (javadoc ^[41]) и CRC32 ^[42] (javadoc ^[43])

Сжатие

В jdk имеется реализация стандартного алгоритма сжатия deflate (Deflater ^[44]) и также на его основе zip/gzip. Все это в пакете java.util.zip ^[45]

Вывод

Как видно классические структуры данных в java представлены далеко не полностью, но в тоже время почти для каждой имеется несколько вариантов потокобезопасных версий.
Чего не хватает — вопрос открытый. Например можно спорить нужен ли в jdk какой-нибудь Union-Find ^[46] или хеш-таблица с открытой адресацией ^[20], но отсутствие графовых структур и алгоритмов совсем в век социальных сетей в языке претендующим на самый универсальный — вызывает удивление баги и велосипеды.

Автор: yetanothercoder

Источник ^[47]