ЛК8 (1)

1. 8. Динамические структуры данных

8. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Организация динамических структур данных.
Списки. Стеки. Очереди. Кольца.
Организация данных в виде древовидных динамических структур.
Двоичные деревья. Алгоритмы обработки динамических структур данных. Алгоритмы хеширования.

2. 8.1. Организация динамических структур данных

8.1. ОРГАНИЗАЦИЯ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ
Динамические структуры данных – это структуры данных, память под которые
выделяется и освобождается по мере необходимости.
Динамическая структура данных характеризуется тем что:
она не имеет имени;
ей выделяется память в процессе выполнения программы;
количество элементов структуры может не фиксироваться;
размерность структуры может меняться в процессе выполнения программы;
в процессе выполнения программы может меняться характер взаимосвязи
между элементами структуры.

3.

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

4.

Каждой динамической структуре данных сопоставляется статическая переменная
типа указатель (ее значение – адрес этого объекта).
Сами динамические величины не требуют описания в программе, поскольку во
время компиляции память под них не выделяется. Во время компиляции память
выделяется только под статические величины. Указатели – это статические
величины, поэтому они требуют описания.
Необходимость в динамических структурах данных обычно возникает в
следующих случаях.
Используются переменные, имеющие довольно большой размер,
необходимые в одних частях программы и совершенно не нужные в других.
В процессе работы программы нужен массив, список или иная структура,
размер которой изменяется в широких пределах и трудно предсказуем.
Когда размер данных, обрабатываемых в программе, превышает объем
сегмента данных.

5.

Классификация динамических структур данных
Во многих задачах требуется использовать данные, у которых конфигурация,
размеры и состав могут меняться в процессе выполнения программы. Для их
представления используют динамические информационные структуры. К таким
структурам относят:
однонаправленные (односвязные) списки;
двунаправленные (двусвязные) списки;
циклические списки;
стек;
дек;
очередь;
бинарные деревья.

6.

Стек
Стек, обычно, описывают как некий набор объектов, который сгруппирован
вместе, где каждый элемент общего набора идет друг за другом — стопка книг
или же подносы, сложенные между собой.
В информатике же, стек — это набор объектов, имеющий общее правило
образования: последний объект, помещенный в стек, извлекается первым из
общего списка. Такое правило еще называют «Последний вошел, первый вышел»
или LIFO. Есть и обратное правило — первый вошел, первый вышел (FIFO), но об
этом чуть позже.
Данное правило, LIFO, используется, например, в автоматах по продаже сигарет,
конфет — последний загруженный туда объект будет выдан первым.

7.

Абстрактное определение стека — список, все операции для которого
определены относительно одного конца, т.е. вершина стека.
Базовые операции, определяющие стек:
init – создать стек.
push – добавить элемент в начало (верх) стека, сдвинув остальные на 1 позицию
вниз.
pop – извлечь (и удалить) элемент из стека (из вершины).
top – получить значение на первый элемент стека (не удаляя).
isEmpty – проверка стека на пустоту.

8.

Также можно определить стек с максимально возможным количеством
элементов, но это уже мелочи. Однако когда стек больше не может принимать
элементы, то стек является переполненным и он возвращает сообщение об этом
(stack overflow). Ну и обратная ситуация — изъятие элемента из пустого стека
(stack underflow).
Зная то, что стек определен как LIFO и его базовые операции, можно написать
стек через массив используя для этого базовые операции push и pop. Пример
будет таким:

9.

<?php
class ReadingList
{
protected $stack;
protected $limit;
public function __construct($limit = 10) {
// инициализация стека
$this->stack = array();
// устанавливаем ограничение на количество элементов в
стеке
$this->limit = $limit;
}

10.

public function push($item) {
// проверяем, не полон ли наш стек
if (count($this->stack) < $this->limit) {
// добавляем новый элемент в начало массива
array_unshift($this->stack, $item);
} else {
throw new RunTimeException('Стек переполнен!');
}
}
public function pop() {
if ($this->isEmpty()) {
// проверка на пустоту стека
throw new RunTimeException('Стек пуст!');
} else {

11.

} else {
// Извлекаем первый элемент массива
return array_shift($this->stack);
}
}
public function top() {
return current($this->stack);
}
public function isEmpty() {
return empty($this->stack);
}
}

12.

Добавление нескольких элементов в стек:
<?php
$myBooks = new ReadingList();
$myBooks->push('A Dream of Spring');
$myBooks->push('The Winds of Winter');
$myBooks->push('A Dance with Dragons');
$myBooks->push('A Feast for Crows');
$myBooks->push('A Storm of Swords');
$myBooks->push('A Clash of Kings');
$myBooks->push('A Game of Thrones');

13.

Очередь
Далее перейдем к «первый вошел, первый вышел» или же FIFO. Любой, кто стоял
в реальной очереди — знает, что тот, кто занял место первым, первым из нее и
уйдет. Исключение — объекты, которым только подписать, спросить, etc.
Базовые операции для очередей такие:
init – создать очередь.
enqueue – добавить элемент в конец (хвост) очереди.
dequeue – удалить элемент из начала очереди (голова).
isEmpty – проверка очереди на пустоту.

14.

PHP предоставляет нам класс SplQueue (двусвязный список), только в данном
случае голова списка — последний элемент. Определим ReadingList как очередь:
<?php
class ReadingList extends SplQueue
{
}
$myBooks = new ReadingList();
// добавим несколько элементов в нашу очередь
$myBooks->enqueue('A Game of Thrones');
$myBooks->enqueue('A Clash of Kings');
$myBooks->enqueue('A Storm of Swords');

15.

Повторение старых материалов

16. 8.2. Организация данных в виде древовидных динамических структур

8.2. ОРГАНИЗАЦИЯ ДАННЫХ В ВИДЕ ДРЕВОВИДНЫХ
ДИНАМИЧЕСКИХ СТРУКТУР
Дерево является одним из важнейших и интересных частных случаев графа.
Древовидная модель оказывается довольно эффективной для представления
динамических данных с целью быстрого поиска информации.
Деревья являются одними из наиболее широко распространенных структур
данных в информатике и программировании, которые представляют собой
иерархические структуры в виде набора связанных узлов.

17.

Дерево – это структура данных, представляющая собой совокупность элементов
и отношений, образующих иерархическую структуру этих элементов.

18.

Каждый элемент дерева называется вершиной (узлом) дерева. Вершины дерева
соединены направленными дугами, которые называют ветвями дерева.
Начальный узел дерева называют корнем дерева, ему соответствует нулевой
уровень. Листьями дерева называют вершины, в которые входит одна ветвь и не
выходит ни одной ветви.
Каждое дерево обладает следующими свойствами:
существует узел, в который не входит ни одной дуги (корень);
в каждую вершину, кроме корня, входит одна дуга.
Деревья особенно часто используют на практике при изображении различных
иерархий. Например, популярны генеалогические деревья.

19.

Все вершины, в которые входят ветви, исходящие из одной общей вершины,
называются потомками, а сама вершина – предком.
Для каждого предка может быть выделено несколько потомков. Уровень потомка
на единицу превосходит уровень его предка. Корень дерева не имеет предка, а
листья дерева не имеют потомков.
Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждой
вершины, упорядочены по определенному критерию.
Деревья являются рекурсивными структурами, так как каждое поддерево также
является деревом. Таким образом, дерево можно определить как рекурсивную
структуру, в которой каждый элемент является:
либо пустой структурой;
либо элементом, с которым связано конечное число поддеревьев.

20.

Списочное представление деревьев основано на элементах, соответствующих
вершинам дерева. Каждый элемент имеет поле данных и два поля указателей:
указатель на начало списка потомков вершины и указатель на следующий
элемент в списке потомков текущего уровня. При таком способе представления
дерева обязательно следует сохранять указатель на вершину, являющуюся
корнем дерева.
Для того, чтобы выполнить определенную операцию над всеми вершинами
дерева необходимо все его вершины просмотреть. Такая задача называется
обходом дерева.
Обход дерева – это упорядоченная последовательность вершин дерева, в которой
каждая вершина встречается только один раз.

21.

При обходе все вершины дерева должны посещаться в определенном порядке.
Существует несколько способов обхода всех вершин дерева. Выделим три
наиболее часто используемых способа обхода дерева:
прямой;
симметричный;
обратный.

22.

Бинарное (двоичное) дерево – это динамическая структура данных,
представляющее собой дерево, в котором каждая вершина имеет не более двух
потомков.
Таким образом, бинарное дерево состоит из элементов, каждый из которых
содержит информационное поле и не более двух ссылок на различные бинарные
поддеревья. На каждый элемент дерева имеется ровно одна ссылка.

23.

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

24.

Рассмотрим на примере
поиска элемента (10)
сравнение операций поиска
в отсортированном
массиве, списке и бинарном
дереве поиска:

25.

<?php
class BinaryTreeNode {
public ?BinaryTreeNode $left = null; // ссылка на левый дочерний узел
public ?BinaryTreeNode $right = null; // ссылка на правый дочерний узел
public ?BinaryTreeNode $parent = null; // ссылка на родителя
public $value; // полезная нагрузка
public function __construct($value, BinaryTreeNode $parent)
{
$this->parent = $parent;
$this->value = $value;
}
}

26.

<?php
class BinaryTreeNode
{
// ...
public function findNode($value)
{
$node = $this;
while ($node) {
if ($value == $node->value) {
return $node;
}
if ($value < $node->value) {
$node = $node->left;
}
if ($value > $node->value) {
$node = $node->right;
}
}
return null;
}}
Поиск узла

27.

<?php
class BinaryTreeNode
{
// ...
Вставка узла
public function insertNode($value) {
$this->_innerInsertNode($value, $this);
}
public function _innerInsertNode($value, ?BinaryTreeNode $parentNode = null) {
$parentNode = $parentNode ?? $this;
if ($value < $parentNode->value) {
if ($parentNode->left == null) {
$parentNode->left = new BinaryTreeNode($value, $parentNode);
} else {
$this->_innerInsertNode($value, $parentNode->left);
}
}
if ($value > $parentNode->value){
if ($parentNode->right == null){
$parentNode->right = new BinaryTreeNode($value, $parentNode);
} else {
$this->_innerInsertNode($value, $parentNode->right);
}
}
}

28.

<?php
class BinaryTreeNode
{
// ...
public function removeNode($value, ?BinaryTreeNode $node = null) {
if ($node == null) {
return null;
}
if ($value < $node->value) {
$node->left = $this->removeNode($value, $node->left);
}
else if ($value > $node->value) {
$node->right = $this->removeNode($value, $node->right); }
else {
if ($node->left == null) {
return $node->right;
}
if ($node->right == null) {
return $node->left;
}
}
$original = $node;
$node = $node->right;
while ($node->left != null) {
$node = $node->left;
}
$node->right = $this->removeNode($original->right);
$node->left = $original->left;
return $node->right;
}
}
Удаление узла

29.

<?php
class BinaryTreeNode
{
// ...
public function traverseRecursive()
{
$this->traverseRecursiveInner($this);
}
Обход деревьев
private function traverseRecursiveInner($node)
{
if ($node != null) {
echo "node = {$node->value}\n";
$this->traverseRecursiveInner($node->left);
$this->traverseRecursiveInner($node->right);
}
}

30.

<?php
public function traverseWithStack()
{
$stack = new SplStack();
$stack->push($this);
while (!$stack->isEmpty()) {
$currentNode = $stack->pop();
Обход деревьев
echo "node = {$currentNode->value}\n";
if ($currentNode->right != null) {
$stack->push($currentNode->right);
}
if ($currentNode->left != null) {
$stack->push($currentNode->left);
}
}
}

31.

<?php
public function traverseWithQueue()
{
$queue = new SplQueue();
$queue->enqueue($this);
while (!$queue->isEmpty()) {
$currentNode = $queue->dequeue();
echo "node = {$currentNode->value}\n";
if ($currentNode->left != null) {
$queue->enqueue($currentNode->left);
}
if ($currentNode->right != null) {
$queue->enqueue($currentNode->right);
}
}
}
Обход деревьев

32. 8.3. Алгоритмы хеширования

8.3. АЛГОРИТМЫ ХЕШИРОВАНИЯ
Хеширование — это процесс преобразования произвольных данных (текста, файла,
пароля) в фиксированную строку символов (хеш) с помощью специальной
математической функции — хеш-функции.
Основные свойства хеш-функций:
детерминированность: один и тот же вход всегда даёт одинаковый хеш;
фиксированная длина вывода;
быстрое вычисление;
необратимость (однонаправленность);
устойчивость к коллизиям: сложно найти два разных входа с одинаковым хешем.

33.

Сферы использования алгоритмов хеширования:
Хранение паролей. Пароли хранятся в виде хешей (например, bcrypt, Argon2),
чтобы даже при утечке базы данных злоумышленник не смог их восстановить.
Целостность данных. Хэши используются для проверки, что файл не был
изменён (например, SHA-256 для проверки скачанных программ).
Цифровые подписи и блокчейн. В криптовалютах (Bitcoin) хеши (SHA-256)
используются для создания блоков и проверки транзакций.
Поиск дубликатов.
Аутентификация сообщений (HMAC). Гарантирует, что сообщение не было
подменено (используется в протоколах HTTPS, API).

34.

Популярные алгоритмы хеширования:
Алгоритм
Длина хеша
Применение
MD5
128 бит
Устарел (ненадёжен из-за коллизий)
SHA-1
160 бит
Устарел (небезопасен)
SHA-256
256 бит
Bitcoin, SSL, проверка файлов
SHA-3
Переменная
Новый стандарт (более безопасный)
bcrypt
Переменная
Хранение паролей
Переменная
Рекомендуемый для паролей (устойчив к
брутфорсу)
Argon2
MD5("hello") → 5d41402abc4b2a76b9719d911017c592
SHA-256("hello") →
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

35.

md5
Это один из самых старых и широко используемых методов хеширования. Он
создает 128-битный хеш в виде 32-символьной шестнадцатеричной строки.
md5 был одним из первых широко используемых алгоритмов хеширования, но на
сегодняшний день он считается устаревшим и небезопасным для большинства
криптографических приложений, особенно для хеширования паролей. Это
связано с тем, что были обнаружены уязвимости, позволяющие проводить
коллизионные атаки (когда два разных ввода дают одинаковый хеш).
$hash = md5('Мой человек меня понимает');
# Возвращает необработанный двоичный хеш
$hash = md5('Мой человек меня понимает', true);

36.

sha1
Этот метод создает 160-битный хеш в виде 40-символьной шестнадцатеричной
строки. Он считается более безопасным, чем MD5.
sha1 является более безопасным, чем MD5, но он также считается устаревшим
для многих криптографических приложений из-за возможности коллизионных
атак. Google в 2017 году продемонстрировал успешную коллизионную атаку на
sha1.
$hash = sha1('Мой человек меня понимает');
// Возвращает необработанный двоичный хеш
$hash = sha1('Мой человек меня понимает', true);

37.

hash()
Эта функция PHP позволяет использовать различные алгоритмы хеширования,
такие как sha256, sha512, ripemd160, whirlpool и другие.
Алгоритмы хеширования sha256 и sha512 считаются достаточно безопасными для
большинства приложений на текущий момент.
$hash = hash('sha256', 'Мой человек меня понимает');
$hash = hash('sha512', 'Мой человек меня понимает');
$hash = hash('md5', 'Мой человек меня понимает');
$hash = hash('crc32', 'Мой человек меня понимает');
# Возвращает необработанный двоичный хеш
$hash = hash('sha256', 'Мой человек меня понимает', true);
print_r( hash_algos() ); # Список поддерживаемых алгоритмов

38.

password_hash() и password_verify()
Эти функции PHP предназначены специально для хеширования паролей.
Эти функции представляют собой современный и рекомендуемый подход к
хешированию паролей в PHP. Они используют сильные алгоритмы хеширования
(BCrypt, Argon2), автоматически добавляют соль к хешу и поддерживают "cost
factor", который делает атаку перебором непрактичной. Это на данный момент
самый безопасный вариант для хеширования паролей в PHP.
# PASSWORD_DEFAULT - используется алгоритм bcrypt
# PASSWORD_BCRYPT - использует алгоритм CRYPT_BLOWFISH
# PASSWORD_ARGON2I - использует алгоритм Argon2i
# PASSWORD_ARGON2ID - использует алгоритм Argon2id

39.

$hash = password_hash('mypassword', PASSWORD_DEFAULT);
# password_hash() возвращает алгоритм, стоимость и соль как
части хеша.
# Таким образом, вся необходимая для проверки информация
включена в него
if( password_verify('mypassword', $hash) )
{
echo 'Пароль верный.';
}
else
{
echo 'Неверный пароль.';
}

40.

crypt()
Это функция, которая может использовать различные алгоритмы хеширования в
зависимости от указанного префикса. Она может использовать алгоритмы, такие
как Standard DES, Extended DES, Blowfish, MD5 и другие. Однако на сегодняшний
день рекомендуется использовать функцию password_hash() для хеширования
паролей, так как она обеспечивает большую безопасность и легкость
использования.
# Алгоритм хеширования в функции crypt() в PHP задается через
второй параметр, который является солью
# https://www.php.net/manual/ru/function.crypt.php
$hash = crypt( 'mypassword', 'salt' );

41.

# Пример вычисления хеша с использованием алгоритма CRYPT_SHA256
для пароля password123
# Генерируем соль
$salt = substr( str_replace( '+', '.', base64_encode(
random_bytes(16) ) ), 0, 16 );
# Создаем строку соли с указанием количества раундов и алгоритма
$full_salt = sprintf( '$5$rounds=5000$%s$', $salt );
# Хэшируем пароль
$hashed_password = crypt( 'password123', $full_salt );
echo $hashed_password;

42.

hash_hmac()
Эта функция генерирует хеш-значение с использованием алгоритма HMAC
(Hash-based Message Authentication Code). HMAC используется для проверки
целостности и подлинности сообщения с секретным ключом.
$hash = hash_hmac('sha256', 'Мой человек меня понимает',
'secret');
# Возвращает необработанный двоичный хеш
$hash = hash_hmac('sha256', 'Мой человек меня понимает',
'secret', true);
# Список поддерживаемых алгоритмов хеширования
print_r( hash_hmac_algos() );

43.

hash_pbkdf2()
Эта функция генерирует производный ключ из указанного пароля и соли,
используя алгоритм PBKDF2 (Password-Based Key Derivation Function 2 - Функция
получения ключа на основе пароля 2). PBKDF2 используется в криптографии для
генерации и усиления ключей.
openssl_digest() и openssl_encrypt()
Эти функции предоставляют набор криптографических операций, включая
хеширование и шифрование, и поддерживают множество алгоритмов.