Core Java. Лекция 7

Collections API

ponomarev@corchestra.ru

@inponomarev

Иван Пономарёв, КУРС/МФТИ

Collections: Separation of interfaces and implementations

colintf

Интерфейсы коллекций: потомки Collection

intf coll

Iterable: интерфейс, умеющий участвовать в for loop

iterable
Iterable<T> collection = ...
for (T e: collection) {
  ...
}
Iterable<T> collection = ...
Iterator<T> i = collection.iterator();
while (i.hasNext()) {
  T e = i.next();
  if (e...)
    i.remove();
}

ListIterator: расширение для List

listiter

Интерфейсы коллекций: потомки Map

intf map

Comparable и Comparator

public interface Comparable<T>{
/**
 * @param  o the object to be compared.
 * @return a negative integer, zero, or a positive integer as this object
 *         is less than, equal to, or greater than the specified object.
 */
 int compareTo(T o);
}

/*Применяется в случае, если сравниваемые объекты
не реализуют Comparable*/
public interface Comparator<T> {
  int compare(T o1, T o2);
}

Intermediate Conclusions

  • Use interfaces for variable types and method arguments. Don’t be tied to specific implementations.

  • In addition to the possibility of substitution of implementations, there are surrogate collections, for example, the following important special cases:

//IMMUTABLE
//Empty                   //From a single element
Collections.emptyList();   Collections.singletonList(o);
Collections.emptySet();    Collections.singleton(o);
Collections.emptyMap();    Collections.singletonMap(k,v);

Surrogate collections: (partial) protection when an object is published

Collections.unmodifiableList(List<? extends T> l);
Collections.unmodifiableSet(Set<? extends T> s);
Collections.unmodifiableMap(Map<? extends K,
                                ? extends V> s);
...

In the Collections class (as well as in the Arrays class) there is a lot of useful stuff!

Иммутабельные коллекции произвольной длины по заданным элементам (Java 9+)

//Of specified elements
List.of(a, b, c...);
Set.of(a, b, c...);
Map.of(k1, v1, k2, v2...);

MapN: иммутабельная хэшмапа

Map.of(1, 'A', 2, 'B', 3, 'C', 4, 'D'));
Diagram

(Визуализация внутреннего устройства структур данных сделана с помощью Lightweight Java Visualizer.)

Коллизии в MapN: linear probing

 Map.of("aaa", 1, "abB", 2, "bBa", 3)
Diagram

Его Величество ArrayList

List<String> list = new ArrayList<>();
list.add("foo"); list.add("bar"); list.add("baz");
Diagram

ArrayList: геометрический рост буфера

  • Когда внутренний массив заполняется, увеличиваем ёмкость в фиксированное число раз \(g > 1\), а не на фиксированное число ячеек.

  • Копирование дорого, но происходит всё реже: ёмкость растёт пропорционально \(1,\ g,\ g^2,\ g^3,\ \ldots\)

  • Полные затраты на запись и копирование при добавлении \(N\) элементов ограничены величиной

    \[{\LARGE CN(1 + \frac{1}{g} + \frac{1}{g^2} + \cdots) < CN \frac{g}{g-1} = KN}\]

    где \(C\) — стоимость записи одного элемента, \(K = Cg/(g-1)\) не зависит от \(N\).

  • Значит, амортизированные затраты на одно добавление не превышают \(KN/N = K\): это \(O(1)\), хотя каждое расширение требует \(O(N)\).

Свойства ArrayList

  • get(int index) is \(O(1)\) ← main benefit of ArrayList<E>

  • add(E element) is \(O(1)\) amortized, but \(O(n)\) worst-case since the array must be resized and copied

  • add(int index, E element) is \(O(n)\) (with \(n/2\) steps on average)

  • remove(int index) is \(O(n)\) (with \(n/2\) steps on average)

  • Iterator.remove() is \(O(n)\) (with \(n/2\) steps on average)

  • ListIterator.add(E element) is \(O(n)\) (with \(n/2\) steps on average)

LinkedList (implements List, Deque)

List<Integer> list = new LinkedList<>();
list.add(1); list.add(2); list.add(3); list.add(4);
Diagram

Algorithmic properties of LinkedList

  • Implements List and Deque

  • get(int index) is \(O(n)\) (with \(n/4\) steps on average)

  • add(E element) is \(O(1)\)

  • add(int index, E element) is \(O(n)\) (with \(n/4\) steps on average),

    but \(O(1)\) when index = 0 ← main benefit of LinkedList<E>

  • remove(int index) is \(O(n)\) (with \(n/4\) steps on average)

  • Iterator.remove() is \(O(1)\) ← main benefit of LinkedList<E>

  • ListIterator.add(E element) is \(O(1)\) This is one of the main benefits of LinkedList<E>

'Does anyone use LinkedList'?

А если всё-таки нужен Deque?

  • ArrayDeque

  • Circular array

  • Faster than LinkedList.

Deque<Integer> arrayDeque = new ArrayDeque<>(4);
arrayDeque.add(1); arrayDeque.add(2); arrayDeque.add(3);
Diagram

ArrayDeque

        arrayDeque.poll(); //returns 1
        arrayDeque.poll(); //returns 2
Diagram

ArrayDeque

    arrayDeque.add(4); arrayDeque.add(5); arrayDeque.add(6);
Diagram

PriorityQueue

  • Постановка в очередь с сортировкой по приоритету за счёт Comparable или Comparator.

List<Integer> list = IntStream.range(0, 16)
                     .boxed()
                     .collect(Collectors.toList());
Collections.shuffle(list);
Diagram

PriorityQueue

PriorityQueue<Integer> q = new PriorityQueue<>(16);
q.addAll(list);
Diagram

PriorityQueue: в чём фокус?

  • Binary min-heap, инварианты:

    • \(q[n] \leq q[2n + 1]\)

    • \(q[n] \leq q[2n+2]\)

  • Следствие:

    • \(q[0] = \min(q)\)

Diagram

Удаление элемента

q.poll();
Diagram

Удаление элемента

q.poll();
Diagram

Удаление элемента

q.poll();
Diagram

Добавление элемента

q.add(1);
Diagram

Conclusions

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

    • частные «удачные» случаи и частота их использования,

    • эффективность использования кэша,

    • количество производимого «мусора»

    • и т. п.

  • ArrayList and ArrayDeque are the preferred choice as implementation of List and Deque in most of the cases.

Его Величество HashMap

Diagram

6 коллизий

Diagram

  • Длинная цепочка может привести к проблемам, если злоумышленник намеренно осуществляет коллизии.

  • При большом кол-ве коллизий на одной ячейке, если значение реализует Comparable, связный список заменяется на красно-черное дерево.

11 коллизий, Java 8+: одеревенение

Diagram

LinkedHashMap: почти готовый LRU кэш

Diagram

LinkedHashMap: режим access order

Map<String, Integer> map = new LinkedHashMap<>(5, 0.8f,
                    /*accessOrder:*/ true);
map.put("one", 1);   map.put("two", 2);
map.put("three", 3); map.put("four", 4);
Diagram

LinkedHashMap: режим access order

map.get("two");
Diagram

LinkedHashMap: выводы

  • LinkedHahMap помнит порядок вставки элементов.

  • Хорош для LRU-кэширования.

  • Хорош для хранения настроек вида «ключ-значение», задаваемых текстом.

More variations on the hash table theme

  • IdentityHashMap — keys are compared by == rather than equals().

  • WeakHashMap — values can be garbage collected if not used elsewhere.

TreeMap: красно-чёрное дерево

Diagram

  • Ключи сравниваются по Comparable или Comparator.

  • Как обычный Map уступает HashMap-у,

  • Незаменим в ситуациях, когда ключ известен только приблизительно.

Красно-чёрное дерево: в чём фокус?

  • Инварианты КЧД:

    • Корень — чёрный.

    • null—«листья» в конце ветвей считаются чёрными.

    • Оба потомка каждого красного узла — чёрные.

    • Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число чёрных узлов.

  • Следствие:

    • Путь от корня до самого дальнего листа (ЧКЧКЧ…​) не более чем вдвое длиннее, чем до самого ближнего (ЧЧЧ…​)

TreeMap

Diagram

TreeMap

Diagram

TreeMap

Diagram

TreeMap

Diagram

TreeMap

Diagram

TreeMap

Diagram

TreeMap

Diagram

TreeMap

Diagram

ConcurrentNavigableMap: то же самое, но thread-safe?

  • ConcurrentSkipListMap

  • В комментариях к исходному коду CSLM обнаруживаются:

    • две научные статьи

    • книга

    • три докторских диссертации

ConcurrentSkipListMap: идея

Diagram

Sets

  • Коллекции, в которых объект может присутствовать только один раз.

  • Реализованы на базе соответствующих Maps:

    • HashSet,

    • LinkedHashSet,

    • TreeSet.

private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

Bitmap-based sets

  • EnumSet — uses a single long if there is less than 64 enum values. Use it for enums!

  • BitSet — array of `long`s.

Algorithms: sorting and shuffling

/*Implements Comparable*/
List<String> names = ...
Collections.sort(names);

/*We pass Comparator*/
List<Employee> staff = ...
Collections.sort(staff,
  Comparator.comparingLong(
    Employee::getSalary));

/*Иногда надо перемешать*/
List<Card> cards = ...
Collections.shuffle(cards);
/*Реализует Comparable*/
String[] names = ...
Arrays.sort(names);

/*We offer Comparator*/
Employee[] staff = ...
Arrays.sort(staff,
  Comparator.comparingLong(
    Employee::getSalary));

/*Arrays.shuffle отсутствует!*/

Algorithms: binary search

List<Employee> staff = ...

Collections.sort(staff,
  Comparator.comparing(
    Employee::getName));

Employee p = ...

int i =
  Collections.binarySearch(
    staff, p,
    Comparator.comparing(
      Employee::getName));
Employee[] staff = ...

Arrays.sort(staff,
  Comparator.comparing(
    Employee::getName));

Employee p = ...

int i =
  Arrays.binarySearch(
    staff, p,
    Comparator.comparing(
      Employee::getName));

Also already implemented

  • поиск min/max

  • копирование

  • разворачивание «задом наперёд»

  • объединение и разность

  • …​ — ищите и найдёте!