Core Java. Лекция 7

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

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

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

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

Интерфейсы коллекций: потомки 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);
...

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

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

Свойства ArrayList

LinkedList

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

Свойства LinkedList

Does anyone use LinkedList?

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

PriorityQueue

PriorityQueue<String> q = new PriorityQueue<>();
q.add("foo"); q.add("bar"); q.add("baz");

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

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

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

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

LinkedHashMap

Map<String, Integer> map = new LinkedHashMap<>(); map.put("foo", 1); map.put("bar", 2); map.put("baz", 3); Помнит порядок вставки элементов. Хорош для LRU-кэширования. Хорош для хранения настроек вида «ключ-значение», задаваемых текстом.

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

TreeMap

Map<String, Integer> map = new TreeMap<>(); map.put("foo", 1); map.put("bar", 2); map.put("baz", 3); Красно-чёрное дерево, ключи сравниваются по Comparable или Comparator. Как обычный Map уступает HashMap-у, Незаменим в ситуациях, когда ключ известен только приблизительно.

Множества (Sets)

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

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

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

/*Реализует 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));

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

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

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

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

//Типы аргументов лямбд указывать не надо: 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) ()->{};

В итоге имеем

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

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

Constructor/Array Constructor Reference

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

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

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

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

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

Функции

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

Операторы

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

​Предикаты​

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

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)

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

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

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

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)