воскресенье, 27 января 2013 г.

Java колекции обзор

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

Collection Set 
public interface Collection<E> extends Iterable<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c); 
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

public interface Set<E> extends Collection<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c);
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array Operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}
Основные реализации:
HashSet - самая быстрая реализация множества, ее основной недостаток, что она не может гарантировать порядок хранения элементов. Скорости итерации этого множества соотносится к сумме элементов множества и его емкости.  Емкость если не задавать при создании по-умолчанию == 16, если это значение слишком большое мы теряем и время и память, если слишком маленькая, то мы теряем время на копирование/дублирование каждый раз ячеек памяти, когда заполняем выделенную емкость.
Пример переопределения емкости: Set<String> s = new HashSet<String>(64);.
Есть еще один параметр, который мы можем переопределять, это load factor, он также определяет сколько памяти занимает наш хешсет (на самом деле это процентный коефициент, который определяет на сколько может быть заполнен наш хештейбл, когда его размер автоматически увеличится, по-умолчании это 0.75(75%)). В большинстве случаев значение по-умолчанию удовлетворяет, общая рекомендация если мы используем значение по умолчанию, то емкость нужно иметь "ожидаемый размер"*2.
TreeSet - самая медленная реализация множества, но элементы хранятся в соответствующем порядке -- либо "естественном", либо определенным компаратором с которым было создано наше множество. У этой реализации нет тюнингующих параметров(емкости и лоудфактора).
LinkedHashSet - это множество которое реализует также интерфейс листа, тоесть это множество сохраняет то порядок элементов, в котором они были вставлены. По скорости немного уступает хешсету, имеет те же тюнингующие параметры, что и хешсет.
EnumSet - реализация для работы с Enum<?>, очень продуктивна для этого типа, содержит полезные фабричные методы. пример
CopyOnWriteArraySet - реализация хороша для конкурентной среды. Это наш идеальный вариант когда мы много и часто (и в разных потоках) итерируем это множество и редко его изменяем. Во время мутирующих операция множество не блокируется, оно копируется и в копию добавляется/изменяется/удаляется элемент, когда вся операция заканчивается в тот момент и происходит подмена ссылки на новую коллекцию. Только вот цена этому время мутирующих операций, оно пропорционально размеру множества.

Collection List 
public interface Collection<E> extends Iterable<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c); 
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

public interface List<E> extends Collection<E> {
    // Positional access
    E get(int index);
    // optional
    E set(int index, E element);
    // optional
    boolean add(E element); 
    // optional
    void add(int index, E element);
    // optional
    E remove(int index);
    // optional
    boolean addAll(int index, Collection<? extends E> c);

    // Search
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // Iteration
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);

    // Range-view
    List<E> subList(int from, int to);
}
Основные реализации:
ArrayList - Vector но без синхронизации и связанной с этим нагрузкой. У него есть один тюнингующий параметр, это инициализируемая емкость. Для доступа к любой позиции такого списка расходуется константное время. А вот удаление и добавление в начальные позиции элементов расходуют время в линейной зависимости от размера массива.
LinkedList -в большинстве случаев эта реализация уступает предыдущей, доступ к ее элементам требует линейного времени от его размера. Зато удаление и добавление в стартовые позиции расходует константное время. Поэтому если мы много удаляем из списка и вставляем в начало, то это реализация подходит идеально. Кроме интерфейса List он также реализует Deque->Queque.
CopyOnWriteArrayList -  реализация хороша для конкурентной среды. Это наш идеальный вариант когда мы много и часто (и в разных потоках) итерируем этот список и редко его изменяем. Во время мутирующих операций список не блокируется, он копируется, и в копию добавляется/изменяется/удаляется элемент, когда вся операция заканчивается в тот момент и происходит подмена ссылки на новую коллекцию. Только вот цена этому время мутирующих операций, оно пропорционально размеру списка.
Vector - наследие старых библиотек. В нем также реализовали для совместимости интерфейс List, когда им пользуемся, то желательно пользоваться только методами листа, для дальнейших совместимостей. Эта реализация незначительно превышает по производительности синхронизированный список, полученный с помощью Collections.synchronizedList.
Collection Queque 
public interface Collection<E> extends Iterable<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c); 
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

public interface Queue<E> extends Collection<E> {
    E element();
    boolean offer(E e);
    E peek();
    E poll();
    E remove();
}
Queue Interface Structure
Type of OperationThrows exceptionReturns special value
Insertadd(e)offer(e)
Removeremove()poll()
Examineelement()peek()

LinkedList - гибрид листа и очереди, реализация FIFO очереди.
PriorityQueue -  структура данных куча. Операции выборки из очереди — poll, remove, peek, and element — имеют доступ к голове очереди - к последнему элементу в соответсвии с сортированием.
Пользуясь итератором из метода .iterate(), у нас нет никаких гарантий, что мы обойдем элементы в определенном в поточной сортировке порядке. Чтобы его обеспечить нужно использовать Arrays.sort(pq.toArray()).
java.util.concurrent.BlockingQueue (I) - интерфейс который подразумевает ожидание при выборке до тех пор пока не появится в очереди элемент, и ожидание в случае добавления до тех пор пока появится место.
java.util.concurrent.LinkedBlockingQueue — блокирующий гибрид линкед-листа и очереди.
java.util.concurrent.ArrayBlockingQueue — блокирующий гибрид аррей-листа и очереди.
java.util.concurrent.PriorityBlockingQueue — блокирующая куча.
java.util.concurrent.DelayQueue — временной планерa с кучей на бекенде.
java.util.concurrent.SynchronousQueue — простейшая блокирующая реализаця BlockingQueue interface
java.util.concurrent.TransferQueue (I) - (In JDK 7) специальная BlockingQueue, код который добавляет элемент может блокировать очередь для другого потока, который пытается получить его в это время
java.util.concurrent.LinkedTransferQueue — реализация TransferQueue основанная linked nodes

Collection Deque 
public interface Collection<E> extends Iterable<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c); 
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}
Deque Methods
Type of OperationFirst Element (Beginning of the Deque instance)Last Element (End of the Deque instance)
InsertaddFirst(e)
offerFirst(e)		addLast(e)
offerLast(e)
RemoveremoveFirst()
pollFirst()		removeLast()
pollLast()
ExaminegetFirst()
peekFirst()		getLast()
peekLast()
ArrayDeque - двунаправленная очередь в основе реализации которой лежит массив, это очередь более продуктивна посравнению со своей следующей коллегой в плане добавления и удаления как последнего элемента, так и первого.
LinkedList - плюс это очереди в том, что она более гибкая, имеет реализованные все методы интерфейса список. Но она занимает на много больше места в памяти, не лучший вариант для итерации, единственный плюс итератора в реализации его удаления, она достаточно продуктивная.
java.util.concurrent.LinkedBlockingDeque - конкурентная реализация, если поток пытается получить в такой очереди первый или последний элемент, а его пока нет, то этот метод отпускается в момент, когда другой поток добавит в него элемент.
Collection Map 
public interface Collection<E> extends Iterable<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c); 
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

public interface Map<K,V> {

    // Basic operations
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();

    // Bulk operations
    void putAll(Map<? extends K, ? extends V> m);
    void clear();

    // Collection Views
    public Set<K> keySet();
    public Collection<V> values();
    public Set<Map.Entry<K,V>> entrySet();

    // Interface for entrySet elements
    public interface Entry {
        K getKey();
        V getValue();
        V setValue(V value);
    }
}
HashMap - традиционно самый быстрый вариант.
TreeMap - сортирует по ключам.
LinkedMap - порядок в порядке вставляния в мэп.
EnumMap - если ключами у нас выступают перечисления, то это самый быстродействующий вариант для такого случая.
WeekHashMap - если кроме этой мапы ссылки на ключ больше нигде не будет, то сборщик почистит такую пару ключ-значение.
IdentityHashMap - как я понял, у этой реализации несколько применений. То есть ключами выступают обьекты, которые сравниваются при выборке по такому ключу не через метод обьекта еквиалс, а как-то по другому, что усложняет атаки путем обмана, когда обьекту перегружают метод еквиалс и он выдает тру на сфабрикованный обьект. Также он полезен в серилизации и глубоком копировании, потому что тут сохраняется "топология графа":) С этого места я уже не понял:)
ConcurrentHashMap - реализация интерфейса ConcurrentMap, реализует такие атомарные операция как putIfAbsent. Реализация не блокируется при чтении. На бекенде лежит хештейбл.
Set SortedSet 
public interface Set<E> extends Collection<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c);
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array Operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

public interface SortedSet>E< extends Set>E< {
    // Range-view
    SortedSet>E< subSet(E fromElement, E toElement);
    SortedSet>E< headSet(E toElement);
    SortedSet>E< tailSet(E fromElement);

    // Endpoints
    E first();
    E last();

    // Comparator access
    Comparator>? super E< comparator();
}
Map SortedMap 
public interface Map<K,V> {

    // Basic operations
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();

    // Bulk operations
    void putAll(Map<? extends K, ? extends V> m);
    void clear();

    // Collection Views
    public Set<K> keySet();
    public Collection<V> values();
    public Set<Map.Entry<K,V>> entrySet();

    // Interface for entrySet elements
    public interface Entry {
        K getKey();
        V getValue();
        V setValue(V value);
    }
}
 
public interface SortedMap<K, V> extends Map<K, V>{
    // Range-view
    SortedMap<K, V> subMap(K fromKey, K toKey);
    SortedMap<K, V> headMap(K toKey);
    SortedMap<K, V> tailMap(K fromKey);

    // Endpoints
    K firstKey();
    K lastKey();

    // Comparator access
    Comparator<? super K> comparator();
}

Автор: coreer на 12:29
Ярлыки: , ,

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)