Презентация на тему Collections and generics

поведения equals() и hashCode() существуют некоторые ограничения, которые указаны

в документации по Object. В частности, метод equals() должен обладать следующими свойствами:
1. Симметричность: Для двух ссылок, a и b, a.equals(b) тогда и только тогда, когда b.equals(a)
2. Рефлексивность: Для всех ненулевых ссылок, a.equals(a)
3. Транзитивность: Если a.equals(b) и b.equals(c), то тогда a.equals(c)
4. Совместимость с hashCode(): Два тождественно равных объекта должны иметь одно и то же значение hashCode()

Сгенерим в Idea и подумаем о магических числах.

31 * i == (i << 5) - i

симбиозом связанных списков и хэш-мапов. Действительно, LinkedHashMap расширяет класс

HashMap и реализует интерфейс Map, но что же в нем такого от связанных списков? Давайте будем разбираться.

String>();
public class LinkedHashMap extends HashMap implements Map
Только что созданный

объект linkedHashMap, помимо свойств унаследованных от HashMap (такие как table, loadFactor, threshold, size, entrySet и т.п.), так же содержит два доп. свойства:
header — «голова» двусвязного списка. При инициализации указывает сам на себя;
accessOrder — указывает каким образом будет осуществляться доступ к элементам при использовании итератора. При значении true — по порядку последнего доступа. При значении false доступ осуществляется в том порядке, в каком элементы были вставлены.

их работа сводится к вызову конструктора родительского класса и

установке значения свойству accessOrder. А вот инициализация свойства header происходит в переопределенном методе init() (теперь становится понятно для чего в конструкторах класса HashMap присутствует вызов этой, ничегонеделающей функции).

void init()
{
header = new Entry(-1, null, null, null);
header.before = header.after = header;
}

переходить к добавлению элементов.

метод createEntry(hash, key, value, bucketIndex) (по цепочке put() ->

addEntry() -> createEntry())

void createEntry(int hash, K key, V value, int bucketIndex)
{
HashMap.Entry old = table[bucketIndex];
Entry e = new Entry(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}

ссылки
Вообще, из-за того что всю основную работу на себя

берет родительский класс, серьезных отличий в реализации HashMap и LinkedHashMap не много. Можно упомянуть о парочке мелких:

Методы transfer() и containsValue() устроены чуть проще из-за наличия двунаправленной связи между элементами;
В классе LinkedHashMap.Entry реализованы методы recordRemoval() и recordAccess() (тот самый, который помещает элемент в конец при accessOrder = true). В HashMap оба этих метода пустые.

Допустим, Вы последовательно добавили в свой мэп значения с

ключами 4, 5, 6, 12, 1.

При итерации по ключам HashMap о порядке появления этих ключей судить большого смысла нет, в то время, как LinkedHashMap выдаст 4, 5, 6, 12, 1.

А в зависимости от значения accessOrder поддерживается либо порядок в котором элементы добавляются, либо порядок в котором они извлекаются

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

или чёрный. В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:

Узел либо красный, либо чёрный.
Корень — чёрный. ☺
Все листья(NIL) — чёрные.
Оба потомка каждого красного узла — чёрные.
Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число чёрных узлов.

Так как такие операции как вставка, удаление и поиск

значений требуют в худшем случае времени, пропорционального длине дерева, эта теоретическая верхняя граница высоты позволяет красно-чёрным деревьям быть более эффективными в худшем случае, чем обычные двоичные деревья поиска.

сортирует элементы по ключу в естественном порядке или на

основе заданного вами компаратора.TreeMap гарантирует скорость доступа log(n) для операций containsKey, get, put и remove.

new TreeMap();
treeMap.put("Bruce", "Willis");
treeMap.put("Arnold", "Schwarzenegger");
treeMap.put("Jackie", "Chan");
treeMap.put("Sylvester", "Stallone");
treeMap.put("Chuck", "Norris");

for(Map.Entry e : treeMap.entrySet()){

System.out.println(e.getKey()+" "+ e.getValue());
}

видим, элементы отсортированы по ключу (Chuck Norris не первый).
Чтобы

получить ключи и значения нужно использовать методы keySet() и values().
При попытке добавить null-элемент в TreeMap происходит исключение NullPointerException.

) , TreeMap(Comparator comp), TreeMap(Map m), TreeMap(SortedMap sm)

Первый конструктор

создает коллекцию, в которой все элементы отсортированы в натуральном порядке их ключей.
Второй конструктор создаст пустую коллекцию, элементы в которой будут отсортированы по закону, который определен в передаваемом компараторе.
Третий конструктор создаст TreeMap на основе уже имеющегося Map.
Четвертый конструктор создаст TreeMap на основе уже имеющегося SortedMap , элементы в которой будут отсортированы по закону передаваемой SortedMap .

Обратите внимание на то, что для сортировки используются ключи, а не значения.

соответствует математическому понятию множества.

описанию данных и алгоритмов, который позволяет их использовать с

различными типами данных без изменения их описания.

public class Box {
private Object object;

public void set(Object object) { this.object = object; }
public Object get() { return object; }
}

public class Box {
// T stands for "Type"
private T t;

public void set(T t) { this.t = t; }
public T get() { return t; }
}

by the Java Collections Framework)
K - Key
N - Number
T

- Type
V - Value

методы
package ru.spbstu.generics.methods
Java Generics – ограничение типизации
package ru.spbstu.generics.bounding

Box хотя Integer является подтипом Number.