среда, 10 октября 2012 г.

Java Collection Framework - part 2

Ниже приведен короткий список реализаций мап из пакета 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. Иначе говоря, сборщик мусора может собирать ключи (если на них отсутствуют ссылки из других мест). Значения привязаные к таким собранным ключам будут удалятся из мапы автоматически. Внимание: значения сохраняются в Мапе как обычные ссылки