В этом руководстве по коллекциям Java мы подробно изучим Java ConcurrentSkipListMap и рассмотрим существенные различия между ConcurrentSkipListMap и другими реализациями Map.
1. Введение в ConcurrentSkipListMap
Класс ConcurrentSkipListMap(присутствует в java.util.concurrent) является классом реализации интерфейса ConcurrentNavigableMap и присутствует с версии Java 1.6. Он имеет следующие особенности:
- По умолчанию элементы сортируются на основе естественного порядка сортировки ключей. Порядок ключей можно настроить с помощью Comparator, предоставленного во время инициализации карты.
- Он потокобезопасен и может одновременно получать доступ к нескольким потокам.
- Он использует параллельную вариацию структуры данных SkipList, обеспечивающую затраты времени log(n) на операции вставки, удаления, обновления и доступа.
- Он лучше, чем ConcurrentHashMap, для поиска элементов.
- Не допускается использование ключей и значений NULL.
- Он возвращает представления Map, которые являются моментальными снимками отображений, когда они были созданы. Эти представления не поддерживают метод Entry.setValue().
В коллекциях Java класс объявлен следующим образом:
public class ConcurrentSkipListMap<K,V>extends AbstractMap<K,V>implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable { ... }Иерархия классов ConcurrentSkipListMap выглядит следующим образом:
2. Что такое список пропускаемых материалов?
Список пропуска — это структура данных, которая позволяет эффективно искать, вставлять и удалять элементы в отсортированном списке. Она построена с использованием нескольких последовательностей слоев, где самый нижний слой связывает все элементы с помощью LinkedList, а последующие более высокие слои пропускают некоторые элементы между списком.
Это означает, что самый высокий слой содержит наименьшее количество элементов в связанной последовательности. Элементы, которые пропускаются между ними, выбираются вероятностно.
Допустим, у нас есть LinkedList с некоторыми узлами, и если мы хотим найти определенный элемент в этом списке. В худшем случае нам придется обойти все элементы, начиная с первого узла, и следовать всем указателям до последнего, где мы получим совпадение. Это соответствует сложности O(n) времени в худшем случае в LinkedList.
Предположим, мы добавляем указатель на два узла вперед к каждому другому узлу, начиная с первого узла; мы можем пропускать два узла за раз, поэтому в худшем случае нам не придется посещать более n/2 узлов, прежде чем мы либо найдем нужное нам число, либо придем к выводу, что элемента нет в списке.
Аналогично, мы можем дать каждому узлу указатель на четыре узла впереди него для более высоких уровней. В результате количество узлов, которые нам придется посетить в худшем случае, будет приблизительно n/4. В общем, если каждый 2^k-й узел имеет указатель на узел на 2^k узлов впереди него, мы можем уменьшить количество узлов, которые нам придется исследовать в худшем случае поиска, до O(log n) временной сложности.
Основная идея Skip List — обеспечить быстрый переход к нужному элементу, сокращая среднее количество шагов, необходимых для его достижения. Следовательно, он обеспечивает сложность log(n) времени для основных операций.
3. Инициализация карты
Мы можем создать новый экземпляр, используя один из следующих конструкторов. Конструктор по умолчанию создает новую пустую карту, используя естественный порядок ее ключей. Мы можем настроить порядок, передав аргумент Comparator.
Чтобы создать экземпляр с существующими записями Map, передайте map конструктору. Если Map поддерживает сортировочное поведение, ключи будут отсортированы как указанная аргументная map.
ConcurrentSkipListMap()ConcurrentSkipListMap(Comparator comparator)ConcurrentSkipListMap(Map m)ConcurrentSkipListMap(SortedMap m)
Следующая программа создает экземпляр и размещает пары ключ-значение в случайном порядке, но Map сортирует записи по ключам в естественном порядке.
ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();map.put(2, "B");map.put(1, "A");map.put(3, "C");System.out.println(map); //{1=A, 2=B, 3=C}4. Полезные операции
4.1. Клавиши пола и потолка
В дополнение к поддержке стандартных операций Map, таких как get(), put(), remove() и т. д., ConcurrentSkipListMap поддерживает поиск нижних/верхних ключей и записей. Он также поддерживает поиск нижних/верхних ключей и записей.
- firstKey(): возвращает первый(наименьший) ключ, который в данный момент находится в карте.
- lastKey(): возвращает последний(наибольший) ключ, имеющийся в данный момент в карте.
- ceilingKey(key): возвращает наименьший ключ, больший или равный заданному ключу, или null, если такого ключа не существует.
- higherKey(key): возвращает наименьший ключ, строго больший указанного ключа.
- lowerKey(key): возвращает наибольший ключ, строго меньший указанного ключа.
- floorKey(key): возвращает наибольший ключ, меньший или равный заданному ключу, или null, если такого ключа не существует.
Стоит знать разницу между этими ключами. Например, если мы передадим ключ, которого нет в Map, то ceilingKey/lowerKey и floorKey/higherKey вернут одинаковые значения. Но если аргумент key присутствует в Map, floorKey/ceilingKey вернет один и тот же ключ, всегда, а higherKey/lowerKey строго вернет следующий/предыдущий ключ по порядку.
ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();map.put(1, "A");map.put(2, "B");map.put(4, "D");map.put(5, "E");System.out.println(map.ceilingKey(3)); //4System.out.println(map.higherKey(3)); //4System.out.println(map.ceilingKey(4)); //4System.out.println(map.higherKey(4)); //5
4.2 Карта головы и карта хвоста
Методы headMap() и tailMap() можно использовать для возврата представления части этой карты, ключи которой меньше/больше указанного аргумента key.
ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();map.put(1, "A");map.put(2, "B");map.put(3, "C");map.put(4, "D");map.put(5, "E");System.out.println(map.headMap(3)); //{1=A, 2=B}System.out.println(map.tailMap(3)); //{3=C, 4=D, 5=E}5. Сравнение с другими картами
5.1. Разница между ConcurrentHashMap и ConcurrentSkipListMap
- ConcurrentHashMap не является ни NavigableMap, ни SortedMap, но ConcurrentSkipListMap является и NavigableMap, и SortedMap.
- ConcurrentSkipListMap использует Skip List в качестве внутренней структуры данных, тогда как CocurrentHashMap использует HashTable и чередование блокировок внутри.
- ConcurrentHashMap, как правило, быстрее выполняет большинство своих операций, что делает его подходящим для приложений, требующих высокой производительности и пропускной способности, в то время как ConcurrentSkipListMap обеспечивает временную сложность O(logn) для большинства своих операций.
- ConcurrentHashMap предоставляет несортированную карту, тогда как ConcurrentSkipListMap предоставляет отсортированную карту на основе естественного порядка сортировки ключей по умолчанию или указанного Comparator.
- ConcurrentHashMap позволяет изменять количество потоков для настройки поведения параллелизма, тогда как ConcurrentSkipListMap не позволяет изменять количество параллельных потоков.
5.2. Разница между TreeMap и ConcurrentSkipListMap
- TreeMap был представлен в Java версии 2.0, тогда как ConcurrentSkipListMap был представлен в Java версии 6.0.
- TreeMap не синхронизирован, тогда как ConcurrentSkipListMap синхронизирован и к нему можно получить доступ в многопоточной среде.
- С точки зрения производительности TreeMap работает лучше, чем ConcurrentSkipListMap, поскольку TreeMap не синхронизирован, поэтому несколько потоков могут работать с TreeMap, что сокращает время ожидания потоков и повышает производительность.
- Итератор TreeMap отказоустойчив и может вызывать исключение ConcurrentModificationException, тогда как итератор ConcurrentSkipListMap отказоустойчив и никогда не вызывает исключение ConcurrentModificationException.
6. Когда использовать?
ConcurrentSkipListMap предлагает среднюю производительность O(log(n)) для широкого спектра операций. Поэтому, если вы не нацелены на пиковую производительность в определенных сценариях, вы можете использовать этот класс для хорошей средней производительности для операций поиска. Кроме того, он может быть бесполезен в случаях, когда на карте выполняется слишком много операций добавления/удаления.
Специальные методы, доступные в классе для поиска ключей пола/потолка или карт начала/конца, могут оказаться полезными в определенных ситуациях, когда вам необходимо получить подкарту, подкрепленную исходной картой, чтобы любые изменения отражались на обеих картах.
7. Заключение
В этом руководстве мы узнали о классе Java ConcurrentSkipListMap и его внутреннем устройстве. Мы увидели, как он хранит пары ключ-значение в отсортированном виде — либо в естественном порядке(по умолчанию), либо в каком-то пользовательском порядке ключей(используя предоставленный Comparator). Мы также рассмотрели варианты его использования и существенные различия между ConcurrentSkipListMap и другими Maps.