Ниже приведен короткий список реализаций мап из пакета java.util. Выбрав наиболее подходящую реализацию не забывайте обратится к
Java API заболее детальной информацией.
Интерфейсы:
- Map - структура данных типа ключь-значение, где ключи не могут содержать дубликатов. Мапы не отслеживают изменение полей объектов которые в них содержатся!
Этот интерфес содержит методы:
- добавления/удаления новых значений в мапу
- проверки присутствия елемента или ключа в мапе
- возвращения сета ключей или пар ключь-значение, а также колекции значений. При этом последние возвращаются по ссылке, т.е. любое изменение в мепе отразится в сетах/колекциях которые были получены и наоборот.
При помощи утилитного класса java.util.Collections вы можете произвести такие действия над вашей мапой:
- synchronizedMap, synchronizedSortedMap - синхронизирует все методы (реализуя паттерн Decorator)
- unmodifiableMap, unmodifiableSortedMap - возвращает колекцию при попытке модификации которой будет брошено исключение UnsupportedOperationException(реализация - паттерн Decorator)
- checkedMap, checkedSortedMap - возвращает колекцию гарантированно содержащую заданый тип. При попытке вставить елемент другого типа будет брошено исключение ClassCastException(реализация - паттерн Decorator)
- SortedMap - Map которая гарантирует сохранение ключей в отсортированом виде.
Содержит методы:
- для получения мин/max значения - firstKey/lastKey
- для получения мап с ключами меньше/больше заданого ключа - headMap/tailMap
- для получения мап с значениями в диапазоне между двумя ключами - subMap
- NavigableMap - SortedMap оптимизированая для поиска по условиям сравнения.
Cвойства:
- содержит оптимизированые методы для получения ключей и их значений по условиям: <, <=,>, >=
- методы NavigableMap параметризированы для включения/не включения граничных условий
- Эти методы возвращаеют наборы ключей, значений, или мапу отсортированую в обратном порядке
- ConcurrentMap - мапа предоставляющая atomic операции putIfAbsent, remove, replaсe. Возвращают true - если операция изменила данные, иначе false
- ConcurentNavigableMap -расширяет NavigableMap возвращая результатом операций тип ConcurentNavigableMap вместо NavigableMap
Классы:
- HashMap - мапа ключи которой размещаются в бакетах, согласно значению их hashcode.
Cвойства:
- методы не синхронизированы
- может содержать нули
- сложность операций извлечения/вставки (get/put/containsKey) - O(1)
- сложность операции containsValue - O(capacity +size)
- При итерировании порядок не гарантирован.
- Сложность итерирования: O(capacity +size), где capacity - количество бакетов, size -размер мапыv
- перестраивает хеши автоматически если: size > loadFactor* capacity. По умолчанию loadFactor = 0.75, capacity=16. При этом capacity увеличивается в двое.
- LinkedHashMap - HashMap ключи которой связаны в LinkedList, это гарантирует порядок обхода ключей (в порядке добавления(insertion-order) или в порядке получения доступа(access-order).
- свойства insertion-order - это дефолтный режим, если существующий ключ вставляется второй раз - порядок в LinkedList не изменится.
- свойства access-order - включается специальным параметром в конструкторе, любая операция put или get изменяет порядок листа
- cложность операции containsValue и итерирования: O(size)!
- Остальные свойства аналогичны HashMap.
- Hashtable - старая потокобезопасная реализация HashMap. Болееновая реализация - ConcurentHashMap. Аналогичен HashMap за исключением:
- не может содержать нулей
- все методы синхронизированы
- Properties - представляет набор пропертейю обладает всеми свойствами Hashtable плюс:
- все ключи типа String
- содержит методы чтения/записи в поток
- для каждого ключа может содержатся 2 значения: обычное и значение по умолчанию, которое задается на конструкторе.
- TreeMap - реализация Red-Black treе -самобалансирующиеся BST
Свойства:
- сложность вставки, удаления, получения, проверки вхождения - O(log(n))
- методы не синхронизированы
- ConcurrentHashMap - более новая реализация Hashtable. Методы имеют туже сигнатуру, поэтому можно просто заменить Hashtable на ConcurentHashMap.
Cвойства:
- все операции потокобезопасны
- операции извлечения данных не блокируют потоки выполнения, и возвращают согласованные данные (относительно завершившихся операций по изменению данных)
- операции по изменению данных блокируют только часть таблицы (грубо говоря нельзя одновременно писать в один бакет, но можно в разные)
- операции по изменнению набора данных типа putAll, clear будут в течении своей работы блокировать определенные сегменты но не всю таблицу
- Операции для работы с набором данных putAll, clear не атомарны!
- Один из параметров конструктора concurrencyLevel - число одновременно работающих потоков, таблица будет разбита на соответствующее число бакетов. (По умолчанию - 16)
- ConcurrentSkipListMap - потокобезопасная реализация SkipList.
- Сложность операций contains, get, put, remove - O(log(n))
- Сложность операции size - O(n)!!!
- Операции для работы с набором данных putAll, equals, и clear не атомарны!
- EnumMap - мапа ключами которой могут быть только занчения Enum.
Свойства:
- Данные сохранняются в масивах, длина которого совпадает с количеством Enum.
- ключи отсортированы в порядке возростания.
- сложность операций извлечения/вставки (get/put/containsKey) - O(1)
- сложность операции containsValue - O(Enum.size())
- IdentityHashMap - хеш мапа с хитрым свойством:
Ключи равны тогда и только тогда когда равны их ссылки (key1 == key2)
Остальные свойства аналогичны обычной HashMap.
Используется если вам нужно по какойто причине иметь список обектов, например при сериализации - когда хотите знать какие объекты уже сериализированы, или при отладке - если хотите иметь список объектов для которых включен дебаг и т.д.
- WeakHashMap - Хеш мапа, в которой значения ключей не содержатся на прямую, а сохраняются как WeakReference. Иначе говоря, сборщик мусора может собирать ключи (если на них отсутствуют ссылки из других мест). Значения привязаные к таким собранным ключам будут удалятся из мапы автоматически. Внимание: значения сохраняются в Мапе как обычные ссылки
Комментариев нет:
Отправить комментарий