какие структуры данных вы знаете java

29.1. Java – Структуры данных

Структуры данных в Java, предоставленные в пакете утилит, очень мощные и выполняют широкий спектр функций. Эти структуры данных состоят из следующего интерфейса и классов:

Все эти классы теперь являются устаревшими, а Java 2 представила новую структуру под названием Collections Framework, о которой мы поговорим в следующем уроке.

Содержание

Интерфейс Enumeration

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

Например, Enumeration определяет метод под названием nextElement, который используется для получения следующего элемента в структуре данных, содержащей несколько элементов.

Чтобы узнать больше об этом интерфейсе, прочитайте главу интерфейс Enumeration.

Класс BitSet

Класс BitSet реализует группу битов или флажков, которые могут быть установлены и очищены отдельно.

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

Чтобы узнать больше об этом классе, прочитайте главу класс BitSet.

Класс Vector

Класс Vector похож на традиционный массив Java, за исключением того, что он может расти по мере необходимости для размещения новых элементов.

Подобно массиву, доступ к элементам объекта Vector можно получить через индекс в вектор.

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

Чтобы узнать больше об этом классе, прочитайте главу класс Vector.

Класс Stack

Класс Stack реализует last-in-first-out (LIFO) стек элементов.

Вы можете думать о стеке как о пирамидке: когда вы добавляете новый элемент, он складывается поверх других.

Когда вы достаёте элемент из стека, он выходит из вершины. Иными словами, последний добавленный элемент к стеку будет первым вышедшим из него.

Чтобы узнать больше об этом классе, прочитайте главу класс Stack.

Класс Dictionary

Класс Dictionary является абстрактным классом, который определяет структуру данных для сопоставления ключей со значениями.

Это полезно для случаев, когда вы хотите получить доступ к данным через конкретный ключ вместо целочисленного индекса.

Так как класс Dictionary абстрактный, он предоставляет только фреймворк для структуры данных с сопоставленными ключами, а не конкретной реализации.

Чтобы узнать больше об этом классе, прочитайте главу класс Dictionary.

Класс Hashtable (хэш-таблица)

Класс Hashtable предоставляет способы организации данных, основываясь на ключевую структуру, определённую пользователем.

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

Конкретное значение ключей в хэш-таблице полностью зависит от хэш-таблицы и от данных, которые она содержит.

Чтобы узнать больше об этом классе, прочитайте главу класс Hashtable.

Класс Properties

Properties – это подкласс Hashtable. Он используется для хранения списков значений, в которых ключ является String, а значение также является String.

Класс Properties используется множеством других Java классов. Например, это тип объекта, возвращаемый System.getProperties( ), когда тот получает внешние значения.

Чтобы узнать больше об этом классе, прочитайте главу класс Properties.

Источник

Структуры данных в Java. Полезные методы вспомогательных классов

Я Software Engineer в EPAM. Более 8 лет я работаю с legacy-кодом, написанном на языке Java (предвосхищая комментарии, отмечу, что понимание и терпимость к legacy началась задолго до EPAM, в заключении вы найдёте ответ, почему). Часто в работе я сталкивался с одними и теми же повторяющимися недочетами. Это побудило меня написать заметку, и начать я хочу со структур данных и вспомогательных классов Collections и Arrays. Почему-то некоторые разработчики пренебрегают их использованием, и напрасно

Разработчику на Java часто приходится сталкиваться с различными структурами данных. Это могут быть массивы, всевозможные коллекции или реализации Map. Казалось бы, всё с ними ясно и понятно, но существует несколько мелочей, о которые легко споткнуться.

Эта заметка может оказаться полезной как новичкам, которые ещё не знают этих нюансов, так и опытным разработчикам, которые могли что-то из этого забыть.

Photo by ammiel jr on Unsplash

Сразу хочу оговориться, что этот материал актуален для Java 8. Понятно, что какие-то вещи уже сделаны лучше в Java 9+, но в большинстве крупных проектов чаще всего используется версия Java 8 (а иногда и Java 6).

Как лучше получить коллекцию на базе массива?

Предлагаю начать с формирования коллекции на базе массива.

Чаще всего встречается такой способ:

Он безусловно работает, но так ли всё с ним хорошо? И есть ли альтернативны решения?

На ум приходят сразу два минуса этого подхода:

Метод Collections.addAll принимает на входе объект Collection и массив. Вместо массива также можно указать элементы через запятую.

Какие преимущества Collections.addAll перед Arrays.asList?

The behavior of this convenience method is identical to that of c.addAll(Arrays.asList(elements)), but this method is likely to run significantly faster under most

Как проще всего напечатать массив, многомерный массив или коллекцию?

Давайте теперь перейдём к такому вопросу, как получение печатного представления массива и коллекций.

Если просто сделать System.out.println(someArray), то получим что-то вроде этого:
[Ljava.lang.Integer;@6d06d69c.
Аналогичный результат ждёт при использовании метода toString() у массива.
Для вывода массива на помощь приходит метод Arrays.toString(. ).

Вывод у этой строки будет такой:

Если речь идёт о многомерном массиве, то можно воспользоваться методом: Arrays.deeptoString.

Выводом этого фрагмента будет:

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

Что касается коллекций или реализаций Map, то тут нет никаких проблем. Все структуры данных, кроме массива, нормально выводятся.

Допустим, есть такой пример:

Обратите внимание в выводе ниже, что и множество, и Map были выведены в удобном для чтения виде:

Как легко можно сравнить массивы между собой?

Бывают ситуации, когда необходимо сравнить массивы. В классе Arrays есть метод, позволяющий провести такое сравнение. Метод Arrays.equals сравнивает количество элементов и проверяет эквивалентность соответствующих элементов.

Допустим, у нас есть класс Elements с одним полем и определённым equals

Определим три массива:

Обратите внимание, что у первого и третьего массива элементы в одинаковом порядке.
Теперь можно выполнить сравнение используя метод Arrays.equals.

Результат будет следующим:

Как эффективно скопировать массив?

Часто можно встретить в коде ручное копирование массивов с использованием циклов. Однако существует метод System.arraycopy, который выполнит копирование гораздо быстрее.

Предлагаю взглянуть на такой простой пример:

У нас есть массив элементов. Мы создаём пустой массив той же длинны и копируем все элементы из первого во второй. В результате получим такой вывод:

Как по-разному отсортировать массив или коллекцию?

Массивы могут быть отсортированы с помощью метода Arrays.sort(someArray). Если требуется отсортировать массив в обратном порядке, то можно передать на вход этому методу Collections.reverseOrder() как второй параметр.

К примеру, есть массив, который мы отсортируем в прямом, а потом в обратном порядке:

Вывод будет следующий:

Кроме прямой и обратной сортировки, бывает, возникает необходимость отсортировать массив строк независимо от регистра. Это легко сделать, передав String.CASE_INSENSITIVE_ORDER как второй параметр в Arrays.sort.

Collections.sort, к сожалению, позволяет отсортировать только реализации List.

По какому алгоритму сортирует Java?

Последнее, о чём можно упомянуть, говоря о сортировке в Java, это то, что в Java для простейших типов используется “quick sort”, а для объектов — “stable merge”. Так что не стоит тратить ресурсы на разработку собственной реализации метода сортировки, пока профилировщик не покажет, что это необходимо.

Что делать, если у нас есть массив, а метод принимает Iterable?

Предлагаю теперь перейти к такому вопросу, как передача массива в метод, требующий Iterable. Напомню, что Iterable — это интерфейс, который содержит метод iterator(), который должен возвращать Iterator.

Если есть метод, который принимает на входе Iterable, то массив туда просто так передать не получится. Несмотря на то, что массив можно перебирать в цикле for, он не является Iterable.

В этом примере всё хорошо. Но если есть метод:

То такая строка не скомпилируется:

Единственный выход в этой ситуации — преобразовать массив в коллекцию и уже её подать на вход такому методу.

Коротко еще о нескольких полезных методах Collections

Что стоит почитать?

Это лишь небольшая часть средств, которые могут облегчить жизнь разработчику при работе со структурами данных. Многие интересные моменты самой работы коллекций и удобные средства для работы с ними можно найти в книге Брюса Эккеля «Философия Java» (4-е полное издание). Однако, стоит быть внимательным, так как в ней встречаются ситуации, которые уже не воспроизводятся на Java 7, Java 8 и выше. Хоть в этой книге и описана Java 6, её материал остается в большинстве своём актуален и сейчас.

Конечно, «Философией Java» ограничиваться не стоит. Любому разработчику Java не повредит прочтение таких книг:

Что в итоге?

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

Отдельно хочу пожелать удачи и терпения тем, кто трудится с унаследованным старым кодом. Большинство крупных проектов — это legacy. И их значимость для заказчика трудно переоценить. Да и чувство победы от устранения бага, на поиск причин которого ушла не одна неделя, ничуть не уступает ощущениям при окончании реализации новой фичи.

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

Источник

Русские Блоги

Структура данных Java

Структура данных Java

содержание

1 массив
2 связанных списка
3 стопки и очереди
4 двоичное дерево
5 куч и стопок
6 хэш-таблица
7 красно-черное дерево

1. Массив

2. Связанный список

N узлов распределены дискретно и соединены указателями.Каждый узел имеет только один узел-предшественник, каждый узел имеет только один последующий узел, первый узел не имеет узла-предшественника, а конечный узел не имеет последующего узла.
Чтобы определить связанный список, нам нужен только указатель заголовка, а весь связанный список можно вытолкнуть с помощью указателя заголовка.

Преимущества связанного списка
Без ограничений по пространству
Быстрая вставка и удаление элементов

Недостатки связанного списка
Скорость доступа очень низкая

Связанный список разделен на 3 категории:

Java реализует связанный список
Сначала мы определяем класс как узел. Узел должен иметь два атрибута:
Поле данных
поле указателя

Как и выше, создается объект узла связанного списка, но понять сам связанный список несложно, но нелегко выполнять связанные операции. Алгоритм включает, но не ограничивается:

Создать связанный список и добавить узлы

1. Создайте головной узел.

2. Затем найдите хвостовой узел, который нужно вставить.

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

Остальные алгоритмы опущены, читатели и друзья могут практиковаться самостоятельно.

3. Стеки и очереди

Мы можем думать о стопке как о коробке для хранения компакт-дисков, отверстие которой немного больше, чем для компакт-дисков. тогда

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

Обход стека
Пока указатель верхнего элемента стека не указывает на нижнюю часть стека, результат обхода всегда будет выводиться

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

очередь

Очередь очень легко понять, мы можем думать об очереди, как о очереди на обед.

Реализация с использованием массива называетсяСтатическая очередь

Использование связанных списков называетсяДинамическая очередь

На этот раз я буду использовать массив для реализации статической очереди.

Очередь реализации Java

Реализация других алгоритмов очередей, циклических очередей и структур связанных списков опускается, и читатели и друзья могут практиковаться самостоятельно.

4. Двоичное дерево

Сначала определите узлы с помощью классов Java

Их текущее состояние разбросано, и эти 5 узлов необходимо подключить.

Пройдите по бинарному дереву

Есть три способа пройти по двоичному дереву:

В качестве примера возьмем приведенное выше двоичное дерево:

Следовательно, мы можем написать такой код обхода по порядку:

5. Куча и стопка

Память кучи: используется для хранения объектов и массивов, созданных командой new.
Память, выделенная в куче, управляется автоматическим сборщиком мусора виртуальной машины Java.

Преимущество кучи состоит в том, что размер памяти можно выделять динамически, и не нужно сообщать компилятору заранее время жизни: сборщик мусора Java автоматически соберет эти больше не используемые данные.
Но недостатком является низкая скорость доступа из-за динамического выделения памяти во время выполнения.

6. Хеш-таблица

Прежде всего, мы также должны просмотреть данные и связанный список:

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

7. Красно-черное дерево

Это сбалансированное двоичное дерево, нижние уровни TreeSet и TreeMap представлены красными и черными деревьями.

Существует также случай (худший) случай (линейный) двоичного дерева поиска:

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

Следовательно, существует концепция сбалансированного дерева

На картинке выше изображено красно-черное дерево, буквально означает красно-черное дерево с красными узлами и черными узлами.

Свойство 1. Узел красный или черный.
Природа 2. Корневой узел черный.
Природа 3. Каждый листовой узел (узел NIL, пустой узел) черный.
Природа 4. Два дочерних узла каждого красного узла черные. (На всех путях от каждого листа до корня не может быть двух последовательных красных узлов)
Свойство 5. Все пути от любого узла к каждому листу содержат одинаковое количество черных узлов.

Красно-черное дерево можно назвать очень сложным. Здесь вводится только понятие. Желающие могут изучить его самостоятельно.

Источник

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

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

Структуры

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

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

Очереди

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

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

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

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

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

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

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

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

Списки

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

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

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

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

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

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

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

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

Есть в jdk реализации хеш-таблиц и с открытой адресацией (linear probing). Одна из них это IdentityHashMap, в которой к тому же используется оптимизация классического linear probing когда и ключи и значения хранятся в одном массиве рядом с друг другом, для лучшего кеширования данных (javadoc: «better locality for large tables than does using separate arrays»)
Вторая реализация — очень специфическая: служит только для хранения ThreadLocal элементов (внутренний скрытый классик ThreadLocalMap) и для использования конечно недоступна.

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

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

Графы

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

Строки

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

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

65K), а значит большие накладные расходы на хранение конечного автомата, в то время как алгоритм перебора — in-place (не используется доп память).
И во-вторых, производительность на среднестатистических строках — в этом видимо перебор не сильно проигрывает другим алгоритмам.

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

Алгоритмы

Сортировка

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

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

Поиск

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

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

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

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

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

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

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

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

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

Источник