structure

стек: достаём только с одного конца, FILO
очередь: кладём и достаём с разных концов, FIFO

массив: случайный доступ, доступ O(1), вставка/удаление O(N)
связанный список: случайный доступ, доступ O(N), вставка/удаление O(1) (1, next2) (2, null) -> (1, next3) (3, next2) (2, null)

хэш-мэп: пара ключ-значение, O(1), вычисляем хэш –> смещение, внутри хэш-мапа

hash(Obj1) = 10, 10 mod 4 = 2
hash(Obj2) = 13, 13 mod 4 = 1
hash(Obj3) = 7,   7 mod 4 = 3
hash(Obj4) = 10 <- коллизия

if a == b -> hash(a) == hash(b)
if hash(a) == hash(b) -/> a==b
Идеальная хэш функция
if hash(a) = X
   hash(a + delta) = Y
   X >> Y

0 ->
1 -> Obj2
2 -> Obj1
3 -> Obj3

Вариант 1 связанный список

0 ->
1 -> (Obj4, 40)
2 -> [(Obj1, 10), (Obj2, 20)]
3 -> (Obj3, 30)

Вариант 2

0 -> Obj4 первая свободная ячейка
1 -> Obj2
2 -> Obj1 \/
3 -> Obj3 \/

Переполнение хэш-таблицы
максимальное наполнение (load factor) 3/4

линейное хэширование – вариант динамической хэш-таблицы используется в субд

простой вариант: увеличиваем место в два раза и перехэшируем таблицу

Вырожденные случаи hash(x) = 1 время доступа O(N)

0
1 -> [Obj1, Obj2, Obj3, Obj4]
2
3

Хэш и коллизии

Hash(Obj1) = X
Hash(Obj2) = X

map.put(Obj1, 1)
map.put(Obj2, 2)

map.get(Obj1) = 1

====
map.put(Obj1, 1)
map.put(Obj1, 2)

map.get(Obj1) = 2

Set множество: неупорядоченное множество уникальных элементов
0 ->
1 -> (Obj2, true)
2 -> (Obj1, true)
3 -> (Obj3, true)

деревья
- двоичные -> 0-2 потомков,
- бинарное дерево поиска (частный случай двоичного дерева) ->
    правый потомок всегда >= левому потомку
    для сбалансированного дерева время доступа O(log n), для несбалансированного в худшем случае O(N)
- самобалансирующиеся деревья (частный случай БДП): глубина левого и правого потомков не превышает 1
    красно-черное дерево
    AVL дерево

графы – домашнее задание
  алгоритмы
    поиск кратчайшего пути из узла А в Б
    задача коммивояжёра NP класс задач Travelling salesman problem

tree map – упорядоченный ассоциативный массив, внутри красно-черное дерево
tree set – упорядоченное множество уникальных элементов

linked hash map – ассоциативный массив, который перебирает элементы в порядке добавления
    (храним рядом связанный список элементов в который добавляем элементы в порядке добавления в hash map)
linked hash set

блум-фильтр
trie, префиксное дерево

мама
машина
магазин
магнитофон

ма
  шина!
  г
   азин!
   нит!
    офон!
  м
   а!
   онт!
===
SOLID
Generics
Covariance vs contravariance

S – single responsibility
принцип единственной ответственности

O – open/closed класс открыт для расширения, закрыт для изменения (с точки зрения контрактов)

L – Liscov's substitution principle
    поведение программы не должно меняться если мы в места использования родительского класса подставим потомка
I – interface segregation мы не должны требовать от программы реализации избыточных методов

D - Dependency inversion – сервисы не должны инстанциировать другие сервисы, а только получать через конструкторы

Метрики кода:
coupling связанность (чем меньше тем лучше) насколько сильно одни классы зависят от других
cohesion связность (чем больше тем лучше) насколько сильно методы одного класса связаны друг с другом
cyclomatic complexity – домашнее задание

Diamond inheritance
                 дл сторон  углы
Четырехугольник      -        -
Квадрат          a=b=c=d     α=β=ɣ=δ=90
Прямоугольник    a=c b=d     α=β=ɣ=δ=90
Параллелограмм   a=c b=d     α=ɣ β=δ
Ромб             a=b=c=d     α=ɣ β=δ

A совместим с B

A\B кв пр пг ро
кв   +  +  +  +
пр   -  +  +  -
пг   -  -  +  -
ро   -  -  +  +

интерфейс Четырехугольник{
    fun geta(): Int
    fun getb(): Int
    fun getc(): Int
    fun getd(): Int
    fun getα(): Int
    fun getβ(): Int
    fun getɣ(): Int
    fun getδ(): Int

    // fun seta(): Int
    // fun setb(): Int
    // fun setc(): Int
    // fun setd(): Int
    // fun setα(): Int
    // fun setβ(): Int
    // fun setɣ(): Int
    // fun setδ(): Int
}

класс Параллелограмм(a, b, α, β) : Четырехугольник{
    val a = a
    val b = b
    val c = a
    val d = b
    val α = α
    val β = β
    val ɣ = α
    val δ = β
}

класс Квадрат(a) : Параллелограмм{
    val a = a
    val b = a
    val c = a
    val d = a
    val α = 90
    val β = 90
    val ɣ = 90
    val δ = 90
}

val fig1 : Параллелограмм = Параллелограмм(1, 2, 30, 150)

val fig2 : Параллелограмм = Квадрат(1)

fig2.seta(1)
fig2.setb(2)
println(fig2.geta())


ч - пг - пр - кв
       - р

ч - пг - пр
       - р - кв

ч - пг - пр - р - кв

ч
  - пг
  - пр
  - р
  - кв

ч - кв - р
  - пр - пг

ковариантность и контравариантность