Многопоточные коллекции в Java

Начиная с версии Java 5 в пакете java.util.concurrent появились реализации коллекций для эффективной работы в многопоточных приложения. Эти коллекции используют различные неблокирующие алгоритмы для достижения высокой скорости чтения/записи значений. Синхронизированный доступ происходит крайне редко и в целом не влияет на производительность. Почти. В зависимости от реализации. :) Рассмотрению таких коллекций посвящен данный урок.

Со списками все просто: единственная существующая concurrent реализация - это CopyOnWriteArrayList. Из названия можно догадаться, как она работает - при изменении создается новая копия списка и, соответственно, происходит блокировка. При чтении блокировок нет. Следовательно, при частых операциях записи или удаления элементов работать будет медленнее, чем даже Collections.synchronizedList(), в котором блокируются все операции, но при этом нет копирования списка. На данном уроке Вы сможете на практике увидеть скороть и медлительность работы этой реализации. Вы напишите мультипоточное приложение, которое определит время чтения/записи значений в разные конкурентные списки.

Учитывая особенности работы CopyOnWriteArrayList, имеет смысл выбирать данную реализацию, только если Вам действительно необходим индексный доступ к элементам, либо в коллекции возможно хранение дубликатов. Данное утверждение справедливо не только к мультипоточным реализациям, а к любым спискам вообще. Если же элементы в коллекции уникальны, и Вам достаточно последовательного доступа, тогда вполне подойдет Set.

Concurrent реализаций интерфейса Set существует две. Первая - это CopyOnWriteArraySet. Свойства такие же, как и у аналогичного списка. Вторая реализация - это ConcurrentSkipListSet. Последняя основана на интересной структуре данных  - слоёный список (SkipList). Подробнее на русском языке Вы можете прочитать на algolist.ru и википедии. Я скажу лишь, что она представляет собой связный список, где вставка и удаление элементов происходит достаточно быстро. Такая структура данных также хорошо подходит для неблокирующего доступа несколькими потоками, ведь, например, для вставки достаточно заблокировать изменение двух соседних элементов в связном списке. В дополнении ко всему, набор ConcurrentSkipListSet хранит значения в отсортированном виде, реализуя интерфейс NavigableSet. При этом, конечно, не стоит забывать о Comparator-е, который будет сравнивать элементы, или интерфейсе Comparable, который они могут реализовывать.

Для использования Map в многопоточной среде существуют два класса - ConcurrentSkipListMap и ConcurrentHashMap. Первая реализация подобна аналогичной для Set. Вторая подобна HashMap, где все пространство значений разбито на независимые области, каждая из которых представляет собой хеш-таблицу. При вставке элемента блокируется только одна область, позволяя параллельные чтение/запись в другие области. Используя этот класс, необходимо помнить о занимаемой памяти, так как для эффектиной работы с несколькими потоками, количество и размеры этих областей быстро растут. Еще одним полезным свойством обоих этих Map есть то, что они реализуют интерфейс ConcurrentMap. В нем представлены методы на основе неблокирующих алгоритмов, позволяющие безопасным образом выполнять проверку и изменение значений в рамках одной атомарной операции. Подобным образом работают атомарные переменные, такие как AtomicInteger и др. Подробнее о них я рассказывал на втором уроке из курса Advanced Java Concurrency.

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

• Во-первых, добавьте параллельную загрузку всех праздников в отсортированный Set. Прочитав файл с помощью org.apache.commons.io.FileUtils.readLines(file, encoding), передайте различные области списка нескольким потокам, которые будут парсить праздники и добавлять их в Set.
• Во-вторых, одновременно с загрузкой и парсингом праздников выполните подсчет количества праздников для каждого дня и каждого месяца. Для этого используйте отдельные Map для хранения того, сколько праздников будет в каждом дне и каждом месяце.
• В результате выполнения программы выведите наиболее и наименее “праздничный” день, а также количество праздников в каждом месяце.

Ну и, конечно, видео данной урока:

Read More...

Интересные реализации интерфейса Map в Java

У интерфейса Map из Java Collections Framework есть несколько реализаций, и у некоторых из них есть очень интересные свойства, знание которых поможет Вам эффективно решать определенные задачи. Отличия между двумя распространенными реализациями - HashMap и TreeMap - такие же, как между HashSet и TreeSet (тем более, что последние реализованы на основе первых), и про них я уже рассказывал. В этом видео, я остановился на не-concurrent классах, таких как LinkedHashMap, EnumMap, WeakHashMap.

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

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

Реализация WeakHashMap основана на использовании слабых ссылок (WeakReference) для ключей. Это позволяет эффективно использовать Map для временного хранения информации, где запись будет удалятся, когда сборщик мусора в Java удалит объект ключа. Для продуктивного и правильного использования этой реализации необходимо понимание механизма ссылок в Java и работы сборщика мусора. Об этом можно почитать, например, тут.

Небольшое домашнее задание для практики навыков работы с этими реализациями:

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

<дата> <название праздника> (<страна праздника>)

Неоходимо дописать парсинг этого файла, чтобы теперь в объект класса Holiday также записывалась страна. Но, так как страны повторяются в файле, то необходимо сделать так, чтобы не создавались новые строки в памяти программы, хранящие одинаковые данные. Поясню дополнительно на примере.

Содержание файла holidays.txt:

2013/10/26 Всероссийский день гимнастики (Праздники России)
2013/6/29 День партизан и подпольщиков (Праздники России)

Прочитав этот файл, программа должна создать 2 объекта класса Holiday. Каждый из них будет хранить ссылки на следующие объекты:

• разные объекты класса Date
• разные объекты класса String, хранящие название празника
• один и тот же объект класса String, в котором будет записано "Праздники России".

Кстати, так как в один и тот же день может быть несколько праздников, то можно сделать так, чтобы объект Date тоже был один для каждого для, в который есть хоть один праздник.

Для реализации это задания необходимо использовать WeakHashMap.

Видео, где я рассказываю про реализации интерфейса Map, их свойства и особенности:

Read More...

Использование HashSet и TreeSet

HashSet и TreeSet - две наиболее распространенные реализации интерфейса Set в Java Collections Framework. Первая основана на использовании функции hashCode и структуры данных “хеш-таблица”, вторая - на основе сравнения элементов и структуры данных “бинарное дерево” (точнее красно-черное дерево). Знание и понимание отличий этих структур данных необходимо для любого программиста. К сожалению, многие лишь поверхностно рассматривают их, что приводит к созданию неэффективного кода, а  иногда и к багам. Познакомиться с этими и другими классами коллекций Java можно, посмотрев урок 10 из курса Java для тестировщиков. Для детального изучения необходимо читать дополнительную литературу. В данном видео Вы познакомитесь с некоторыми особенностями этих классов, незнание которых может привести к возникновению ошибок или изобретению новых “велосипедов”.

Я думаю, что некоторым из Вас это видео может показаться неинтересным, не открывшим ничего нового. Это хорошо, что Вы знаете эти темы - подождите следующих видео :) А я буду рад за тех, кто почерпнет что-то полезное из этого материала. Потому что на самом деле, реальные баги в реальных проектах, которые мне пришлось отлавливать, возникли как раз из-за невнимательности (или незнания) при работе с этими реализациями Set.

Так как многие из Вас хотят домашнего задания, чтобы потренировать навыки программирования, то вот одно, среднего уровня сложности:

Написать программу, которая выводит 3 блока информации:

• список праздников на сегодняшний день
• список праздников на завтрашний день
• список праздников на ближайшие 5 дней, не включая сегодняшний и завтрашний дни

Список праздников прочитать при старте программы из этого файла: holidays.txt.zip
Каждую строку в этом файле преобразовать в объект класса Holiday, который implements Comparable<Date>, и который будет иметь два поля: Date date и String name.
Для хранения объектов Holiday в памяти использовать TreeSet.
Результат работы программы должен быть приблизительно таким:

#>java package.name.ShowHoliday
Сегодня:
Праздник 1
Праздник 2

Завтра:
Праздник 3
Праздник 4

Скоро:
Ср, 17 июля - Праздник 5
            - Праздник 6
Чт, 18 июля - Праздник 7
            - Праздник 8

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

P.S. Если вдруг кому интересно, то для формирования файла с праздниками я написал shell-скрипт на bash, который посылает запросы на сайт и парсит праздники с результирующей страницы. Вы можете скачать скрипт и поиграться с ним (нужен Linux): holiday_parse.sh

Ну и, собственно, видео:

Read More...

Курсы Advanced Java

Опыт общения с различного уровня программистами на языке Java - как на собеседованиях, так и просто в дружественной обстановке - показал наличие некоторых пробелов в знаниях особенностей языка, а также его инструментов. В целом, причины этого вполне объяснимы – ведь, если все время программируешь, например, web-интерфейсы, то не будешь особо задумываться над различными способами взаимодействия с базами данных или обеспечения эффективного чтения/записи файлов. Однако, никогда не знаешь, к чему может привести очередной виток в карьере. Поэтому хорошее владение выбранным языком программирования и знание его особенностей просто необходимо, чтобы не изобретать повторно велосипеды и не ощущать удары грабель по уже набитым шишкам. Выделив отдельные темы из области Java Core, в которых было замечено большего всего пробелов, а также которые, возможно, сложны для понимания из-за отсутствия практики, я создал курс Advanced Java, который и представляю Вашему вниманию.

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

Курс Advanced Java построен в первую очередь на основе практики. Т.е. Вы не только узнаете, как использовать тот или иной инструмент, но также сможете написать код. Такая практика не только поможет лучше понять изложенное в тренингах, но и закрепит Ваши умения, чтобы использовать их на деле. В записях данного блога я постараюсь также написать несколько домашних заданий по отдельным темам, чтобы помочь Вам лучше закрепить материал. На видео я предлагаю решения некоторых поставленных задач, однако советую Вам сначала написать код самостоятельно, ведь на реальной работе Вам редко когда будут в точности говорить, что и как делать.

Данный курс разбит на пять отдельных мини-курсов, которые охватывают такие темы, как многопоточность (concurrency), коллекции (collections), обобщения (generics), аннотации (annotations), рефлексию (reflection) и сериализацию (serialization). Эти мини-курсы можно изучать отдельно, по каждому из них будет выпущено несколько видео. Единственное, что стоит упомянуть – вторая часть мини-курса по коллекциям посвящена неблокирующим реализациям коллекций (concurrent collections), и ее стоит изучать после мини-курса по многопоточности.

Мини-курс "Advanced Java - Concurrency" знакомит со сложными концепциями многопоточности и параллелизма в языке Java на основе пакета java.util.concurrent. В нем кратко вспоминаются основные механизмы синхронизации в Java, одновременно представляются общие проблемы, связанные с использованием потоков (например, возникновение взаимной блокировки (deadlock)), и показываются эффективные способы их решения. Курс знакомит с высокоуровневыми методами синхронизации с использованием CountDownLatch, CyclicBarrier, ThreadLocal, а также различными Executors для запуска потоков.

Мини-курс “Advanced Java – Collections” посвящен детальному рассмотрению стандартных реализаций интерфейсов Java Collections Framework (hash maps, queues, sets), объясняет их особенности, способы применения и знакомит с некоторыми интересными свойствами, позволяющими повысить эффективность работы с коллекциями в программе, а также избежать возникновения скрытых багов. Вторая часть данного мини-курса знакомит с неблокирующими реализациями коллекций (non-blocking lists and sets, concurrent maps, blocking queues), объясняет разницу между ними, а также на практике показывает их плюсы и минусы, и возможное применение.

Мини-курс “Advanced Java – Generics” подробно рассматривает скрытые проблемы, возникающие при игнорировании женериков, объясняет особенности наследования при использовании классов с обобщенной типизацией, а также показывает, как повысить эффективность кода с применением метасимволов (wildcard) и расширителей обобщения (extends и super).

Мини-курс “Advanced Java – Annotations/Reflection” рассказывает о том, как создавать собственные аннотации, определять их свойства и обрабатывать их с помощью рефлексии (reflection). В дополнении к этому данный мини-курс знакомит с другими часто используемыми особенностями применения Java Reflection API.

Мини-курс “Advanced Java – Serialization” представляет различные популярные техники для сериализации объектов в Java. Рассматривается базовая сериализация с применением встроенных инструментов, объясняются тонкости ее настройки и использования. Кроме того, мини-курс знакомит со ставшей уже встроенной сериализацией в XML с применением JAXB, а также с сериализацей в формат JSON с помощью библиотеки от Google.

Read More...