Core Java. Лекция 7

Collections, lambdas, method references

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

tagir1
tagir2
tagir3

Коллекции: Разделение интерфейсов и реализаций

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);
}

Промежуточные итоги

  • Используйте интерфейсы для типов переменных и аргументов в методах. Не привязывайтесь к конкретным реализациям.

  • Помимо возможности подмены реализаций, существуют суррогатные коллекции, например, важные частные случаи:

//ИММУТАБЕЛЬНЫЕ
//Пустые                   //Из одного элемента
Collections.emptyList();   Collections.singletonList(o);
Collections.emptySet();    Collections.singleton(o);
Collections.emptyMap();    Collections.singletonMap(k,v);

Иммутабельные коллекции по заданным элементам

//Из заданных элементов
List.of(a, b, c...);
Set.of(a, b, c...);
Map.of(k1, v1, k2, v2...);

Но как они это сделали для мапы?

Суррогатные коллекции: защита (частичная) при публикации объекта

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

В классе Collections (как и в классе Arrays) вообще очень много всего полезного!

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

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

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

Свойства 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

List<String> list = new LinkedList<>();
list.add("foo"); list.add("bar"); list.add("baz");
linkedlist inside

Свойства 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 = 0main 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?

blochonlinkedlist

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

  • ArrayDeque

  • Circular array

  • Более быстрый, чем LinkedList.

arraydeque inside

PriorityQueue

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

  • Balanced binary heap: "the two children of queue[n] are queue[2*n+1] and queue[2*n+2] "

PriorityQueue<String> q = new PriorityQueue<>();
q.add("foo"); q.add("bar"); q.add("baz");
priority inside
  • Теоретическая асимптотика не полностью описывает пригодность той или иной структуры данных: вмешивается ряд обстоятельств, таких как

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

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

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

    • и т. п.

  • ArrayList и ArrayDeque являются предпочтительным выбором реализации List и Deque в подавляющем большинстве случаев.

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

Map<String, Integer> map = new HashMap<>();
map.put("foo", 1); map.put("bar", 2); map.put("baz", 3);
hm nocollisions

Коллизии хэша

hm collisions
Map<String,
  Integer> map
  = new HashMap<>();
map.put("foo", 1);
map.put("Aa", 2);
map.put("BB", 3);
  • При большом кол-ве коллизий на одной ячейке, если значение реализует Comparable, связный список заменяется на дерево.

  • Реализуйте Comparable!!

LinkedHashMap

hm lhm
Map<String,
  Integer> map =
  new LinkedHashMap<>();
map.put("foo", 1);
map.put("bar", 2);
map.put("baz", 3);
  • Помнит порядок вставки элементов.

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

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

Ещё вариации на тему хэш-таблицы

  • IdentityHashMap — ключи сравниваются по ==, а не по equals().

  • WeakHashMap — значения могут быть собраны сборщиком мусора, если не используются где-то ещё.

TreeMap

tm
Map<String,
  Integer> map =
  new TreeMap<>();
map.put("foo", 1);
map.put("bar", 2);
map.put("baz", 3);
  • Красно-чёрное дерево, ключи сравниваются по Comparable или Comparator.

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

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

Множества (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;
}

Множества на основе битовых масок

  • EnumSet — на базе единственного значения типа long. Используйте только его для enum-ов!

  • BitSet — массив long-ов.

Алгоритмы: сортировка и перемешивание

/*Реализует Comparable*/
List<String> names = ...
Collections.sort(names);

/*Предлагаем Comparator*/
List<Employee> staff = ...
Collections.sort(staff,
  Comparator.comparingLong(
    Employee::getSalary));

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

/*Предлагаем Comparator*/
Employee[] staff = ...
Arrays.sort(staff,
  Comparator.comparingLong(
    Employee::getSalary));

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

Алгоритмы: бинарный поиск

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));

Также уже реализованы

  • поиск min/max

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

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

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

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

Callbacks: До появления лямбд

public interface ActionListener {
  void actionPerformed(ActionEvent event);
}

// ----использование----
String text = ...
new Timer(1000, new ActionListener(){
  @Override
  public void actionPerformed(ActionEvent e) {
    ... //'text' var is available here
    }
  });

Callbacks: Comparator

String[] friends = {"Peter", "Paul", "Mary"};

Arrays.sort(friends,
  new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
      return o1.length() - o2.length();
  }
});

Предикат

File[] hiddenFiles = new File(".").listFiles(
  new FileFilter() {
    public boolean accept(File file) {
      return file.isHidden();
    }
  }
);

Welcome lambda expressions!

//single-line
(String first, String second) ->
  first.length() - second.length()

//multi-line with int return
(String first, String second) -> {
  if (first.length() < second.length()) return -1;
  else if (first.length() > second.length()) return 1;
  else return 0;
}

//no-arg, void return
() -> System.out.println("Hello!");

Что из этого — валидные лямбда-выражения?

  1. () → {}

  2. () → "Raoul"

  3. () → {return "Mario";}

  4. (Integer i) → return "Alan" + i

  5. (String s) → {"Iron Man"}

Ответ: 1-3. Если лямбда с фигурными скобками, обязательно нужен return. Если без них, то return не нужен!

Чему можно присваивать лямбды?

  • Функциональный интерфейс — такой, у которого не более одного абстрактного метода (понятно, что запускать).

  • Может быть помечен аннотацией @FunctionalInterface, хотя это не обязательно.

  • Если метод интерфейса подходит по параметрам и возвращаемому значению лямбды — welcome.

//Типы аргументов лямбд указывать не надо: type inference!
ActionListener = e -> {...}
Comparator<String> c = (s1, s2) -> s1.length() - s2.length();

Void-compatibility

Оба варианта скомпилируются:

final List<String> list = ...

//Predicate.test возвращает boolean
Predicate<String> p = s -> list.add(s);

//Consumer.accept возвращает void!
Consumer<String> c = s -> list.add(s);

Object — не функциональный интерфейс!

//не скомпилируется
Object o = ()->{};

//Скомпилируется!
Runnable r = ()->{};

//Тоже скомпилируется
Object o = (Runnable) ()->{};

В итоге имеем

Anonymous Class

Lambda

new Timer(100, new ActionListener(){
 @Override
 public void
   actionPerformed(ActionEvent e) {
     ...
   }
});
new Timer(100, e -> {...});
Arrays.sort(friends,
 new Comparator<String>() {
   @Override
   public int compare(
     String o1, String o2) {
    return o1.length()-o2.length();
 }
});
Arrays.sort(friends, (s1, s2)->
  s1.length() - s2.length());

Замыкания (closures)

void repeatMessage(String text, int delay) {
  ActionListener  listener = event -> {
    //переменная text доступна внутри лямбды!
    System.out.println(text);
  }
  new Timer(delay, listener).start();

}
  • «Ингредиенты» лямбды:

    • Код

    • Параметры

    • Свободные («захваченные») переменные, которые должны быть effectively final

Effectively final only

int start = ...

for (int i = 0; i < count; i++) {
  ActionListener linstener = event -> {
    start--; //ERROR: Can't mutate captured value

    //ERROR: Cannot refer to changing i
    System.out.println(i);
  }
}

(Effectively final переменные — это такие, что они либо уже final, либо, если на них проставить final, код всё равно будет компилироваться)

Method references: ещё короче, ещё эффективнее

event -> System.out.println(event)
System.out::println
(s1,s2)->s1.compareToIgnoreCase(s2)
String::compareToIgnoreCase
(x, y) -> Math.pow(x,y)
Math::pow

Три способа определить Method reference

object::method

(x, y, z…​) → object.method(x, y, z…​)

Class::instanceMethod

(x, y, z…​) → x.instanceMethod(y, z…​)

Class::staticMethod

(x, y, z…​) → Class.staticMethod(x, y, z…​)

Constructor/Array Constructor Reference

Class::new

(x, y, z…​) → new Class(x, y, z…​)

Class[]::new

(int i) → new Class[i]

IDE поможет, но разница есть!

obj = null;

//NPE только в момент запуска лямбды!!
//obj должен быть effectively final!
doSmth(x -> obj.method(x));

//NPE здесь и сейчас
//obj не обязан быть effectively final
doSmth(obj::method)

Методы, специально созданные, чтобы быть method references

//Да ладно, разве трудно на null проверить??
Objects.isNull(Object obj)...
Objects.nonNull(Object ob)...


list.removeIf(Objects::isNull);

stream.filter(Objects::nonNull)...

Готовые функциональные типы

Functional InterfaceParameter TypesReturn TypeAbstract Method NameDefault Methods

Runnable

none

void

run

Supplier<T>

none

T

get

Consumer<T>

T

void

accept

andThen

BiConsumer<T, U>

T, U

void

accept

andThen

Комбинирование консьюмеров

Consumer<String> foo = ...
List<String> list = ...

//Составной консьюмер, отправляющий
//объект сначала в первый, потом во второй
Consumer<String> bar = foo.andThen(list::add);

Функции

Functional InterfaceParameter TypesReturn TypeAbstract Method NameDefault Methods

Function<T, R>

T

R

apply

compose, andThen, identity

BiFunction<T, U, R>

T, U

R

apply

andThen

Композиция функций и identity

f.andThen(g)

g(f(x))

f.compose(g)

f(g(x))

Function.identity()

x → x

Почему у BiFunction нет compose, только andThen?

Операторы

Functional InterfaceParameter TypesReturn TypeAbstract Method NameDefault Methods

UnaryOperator<T>

T

T

apply

compose, andThen, identity

BinaryOperator<T>

T, T

T

apply

andThen, maxBy, minBy

Композиция операторов

  • UnaryOperator<T> extends Function<T,T>, поэтому compose, andThen и identity работают так же.

  • BinaryOperator<T> extends BiFunction<T,T,T>, поэтому andThen работает так же

  • Статические методы minBy и maxBy формируют операторы min(x,y) и max(x,y) из компаратора.

​Предикаты​

Functional InterfaceParameter TypesReturn TypeAbstract Method NameDefault Methods

Predicate<T>

T

boolean

test

and, or, negate, isEqual

BiPredicate<T, U>

T, U

boolean

test

and, or, negate

Композиция предикатов

Predicate<T> a = ...
Predicate<T> b = ...

a.and(b).negate(); // ! (a(x) & b(x)

//Двуместный предикат (x,y)-> Objects.equals(x, y)
Objects::equals

//Одноместный предикат y -> Objects.equals(x, y)
Predicate.isEqual(x)

Функциональные интерфейсы для примитивных типов

p, q is int, long, double; P, Q is Int, Long, Double

Functional InterfaceParameter TypesReturn TypeAbstract Method Name

BooleanSupplier

none

boolean

getAsBoolean

PSupplier

none

p

getAsP

PConsumer

p

void

accept

ObjPConsumer<T>

T, p

void

accept

PFunction<T>

p

T

apply

PToQFunction

p

q

applyAsQ

ToPFunction<T>

T

p

applyAsP

ToPBiFunction<T, U>

T, U

p

applyAsP

Функциональные интерфейсы для примитивных типов (продолжение)

Functional InterfaceParameter TypesReturn TypeAbstract Method Name

PUnaryOperator

p

p

applyAsP

PBinaryOperator

p, p

p

applyAsP

PPredicate

p

boolean

test

Дефолтные методы Map interface

Работают атомарно в ConcurrentHashMap!

V computeIfAbsent(K key,
  Function<? super K, ? extends V> mappingFunction)

V computeIfPresent(K key,
  BiFunction<? super K, ? super V, ? extends V> remappingFunction)

V compute(K key,
  BiFunction<? super K, ? super V, ? extends V> remappingFunction)

V merge(K key, V value,
  BiFunction<? super V, ? super V, ? extends V> remappingFunction)

Компараторы

@AllArgsConstructor
public class Person {
    @Getter
    private final String firstName;
    @Getter
    private final String lastName;
}
List<Person> people = new ArrayList<>();

Сортируем по фамилии

/*НЕПРАВИЛЬНО*/
Collections.sort(people,
 (p1, p2) ->
   p1.getLastName()
   .compareTo(
     p2.getLastName());
);
/*ПРАВИЛЬНО*/
Collections.sort(people,
  Comparator.comparing
   (Person::getLastName));
);

​Сортируем по фамилии, потом по имени​

//НЕ ПИШИТЕ ВЕСЬ ЭТОТ КОШМАР
Collections.sort(people,
  (p1, p2) -> {
    int result = p1.getFirstName().compareTo(p2.getFirstName());
    if (result == 0) {
      result = p2.getLastName().compareTo(p2.getLastName());
    }
    return result;
  }
);

Правильно так:

Collections.sort(people,
  Comparator
    .comparing(Person::getLastName)
    .thenComparing(Person::getFirstName));
);

Также:

Comparator.comparing(keyExtractor, keyComparator)
Comparator.comparingInt/Double(...)
Comparator.reversed()
Comparator.nullsFirst/nullsLast(Comparator c)
doctor