Василий Орлов, учебный центр NetCracker при МФТИ

в Java
Реализации интерфейсов коллекций в Java
Специальные утилитные классы для работы

с коллекциями в Java

Понятие настраиваемого типа(generic)
Различные примеры кода с generics
Generics с ограничениями
Маски

с целью обеспечения возможностей эффективного доступа к ним.

Массив — набор

однотипных элементов, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу.

к нему можно в любой момент обратиться
Как правило, в качестве

индексов выступают последовательные целые числа
Для обращения к элементу используется имя вектора и значение индекса
Удаление элемента из вектора приводит к образованию пустого элемента

производится по ключу
Тип ключа должен допускать сравнение на равенство
Любая пара

может быть в любой момент удалена

операции добавления, удаления и определения вхождения
По сути является ассоциативным массивом(map),

где роль ключа играет сам элемент

за другом, доступ к которым осуществляется по индексу.

Сложность:
Вернуть значение по

индексу: O(1)
Поиск: O(n)
Вставка: O(n)
Удаление: O(n)

из которых содержит как собственно данные, так и одну или

две ссылки на следующий и/или предыдущий узел списка
Сложность:
Вернуть значение по индексу: O(n)
Поиск: O(n)
Вставка: O(1)
Удаление: O(1)

и выполнять три операции: добавления новой пары, операцию поиска и

операцию удаления пары по ключу.
Cодержит некоторый массив, элементы которого есть списки пар.
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение играет роль индекса в массиве . Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива.

с коллекциями, и классы, реализующие конкретную функциональность

Не все методы, заявленные

в интерфейсах, должны в действительности реализовываться классами. Часть методов может просто выбрасывать исключение UnsupportedOperationException

добавление, удаление, выбор элементов в коллекции

Допускает дубликаты и пустые элементы

элементов boolean remove(Object o), boolean removeAll(Collection c), boolean retainAll(Collection c),
Состояние

коллекции boolean contains(Object o), boolean containsAll(Collection c), boolean isEmpty(), int size()
Вспомогательные методы Object[] toArray(), Iterator iterator()

ссылки null

Объекты коллекции должны корректно реализовывать метод equals()

порядком добавления элементов

Позволяет обращаться к элементам по их номеру

boolean addAll(int index, Collection c)
Адресные операции с элементами Object get(int

index), Object set(int index, Object o), Object remove(int index)
Операции поиска int indexOf(Object o), int lastIndexOf(Object o)
Специальные операции List subList(int from, int to)

следующий объект Object next()
Проверять наличие следующего объекта boolean hasNext()

должны быть уникальными
Порядок следования пар ключ/значение не определен
Имеет расширение SortedMap, требующее

упорядоченности по значениям ключей

t)
Исключение объектов Object remove(Object key), void clear()
Доступ к объекту по ключу Object

get(Object key)
Состояние boolean containsValue(Object value), boolean containsKey(Object key), int size(), boolean isEmpty()

порядке, требует чтобы объекты, которые содержит коллекция реализовывали интерфейс Comaprable

либо требует задать специальный Comparator, который умел бы сравнивать объекты из коллекции.

SortedMap расширяет Map храня значения в отсортированном по ключам порядке, требует чтобы ключи реализовывали интерфейс Comaprable либо требует задать специальный Comparator, который умел бы сравнивать ключи.

(Set)

a)
Поиск элемента в массиве int binarySearch(…[] a, … key)
Сравнение массивов по

элементам boolean equals(…[] a1, …[] a2)
Заполнение массива элементами fill(…[] a, int from, int to, … val)
Сортировка массива sort(…[] a, int from, int to)

методов и типы возвращаемых методами значений могут меняться
class Gen {
private

T value;
public Gen(T v) { value = v;}
public T getValue() { return value;}
public void setValue (T v) { value = v;}
}

public class GenTest
{
public static void main(String[] args)
{
Gen intObj = new Gen(777);
Gen strObj = new Gen(“Some text”);
Gen strObj1 = new Gen(555); // ошибка компилятора
int i = intObj.getValue() + 2;
String s = strObj.getValue ().substring(2);
intObj = strObj; // ошибка компилятора
}
}

intObj = new Gen(777);
Gen strObj = new Gen(“Some text”);
Gen

strObj1 = new Gen(555); // ошибка компилятора
int i = intObj.getValue () + 2;
String s = strObj.getValue ().substring(2);
intObj = strObj; // ошибка компилятора
}
}

public class GenTest
{
public static void main(String[] args)
{
Gen strObj = new Gen(“Some text”);
strObj.setValue(555); // сообщения об ошибке нет
strObj.setValue(“Some text”);
String s = (String)strObj.getValue();
Integer i = (Integer)intObj.getValue(); // ошибка runtime
}
}

V ob2;
public Gen(T ob1, V ob2)
{
this.ob1= ob1;
this.ob2= ob2;
}
}

public class

GenTest
{
public static void main(String[] args)
{
Gen data = new Gen(10, “Test”);
int i = data.ob1 + 2;
String s = data.ob2.substring(1);
Gen object = new Gen(10, “Test”);
int k = object.ob1 + 2;
String s = object.ob2.substring(1); // Ошибка.
s = ((String)object.ob2).substring(1);
}
}

{
this.t=t;
}
}

public static void main(String[] args)
{
GenTest genTest1 = new GenTest(new Dog());

/*

ошибка */
GenTest genTest2 = new GenTest(new Cat());

/* ошибка */
GenTest genTest3 = new GenTest(new Dog());
}
}

glyphs) {…}


static void doSomeWork(Map