Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы

Нажмите для полного просмотра!

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №2

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №3

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №4

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №5

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №6

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №7

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №8

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №9

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №10

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №11

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №12

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №13

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №14

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №15

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №16

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №17

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №18

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №19

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №20

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №21

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №22

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №23

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №24

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №25

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №26

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №27

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №28

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №29

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №30

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №31

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №32

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №33

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №34

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №35

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №36

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №37

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №38

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №39

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №40

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №41

Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №42

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы. Доклад-сообщение содержит 42 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Linked lists Односвязный список

Слайд 2

Описание слайда:

Операции над списками

Слайд 3

Описание слайда:

Random Access Memory У каждой ячейки свой адрес Быстрый доступ к ячейке по адресу Поддержка адресной арифметики

Слайд 4

Описание слайда:

Array Сплошной массив элементов в памяти Задан адрес начального элемента Быстрое вычисление адреса элемента по индексу Невозможность расширения Сложность операций:

Слайд 5

Описание слайда:

Linked lists once again…. Произвольное расположение элементов Возможность расширения Медленный доступ по индексу:

Слайд 6

Описание слайда:

Формулировка проблемы Необходимость быстрого поиска данных в огромных массивах Где применить: Справочники Базы данных пользователей Реализация множеств Ассоциативные массивы Желаемая сложность выполнения операций:

Слайд 7

Описание слайда:

Создание баз данных логинов-паролей Огромное количество пользователей системы Время доступа – критический параметр Огромное количество возможных комбинаций Доступ по индексу не требуется Безопасность хранения данных

Слайд 8

Описание слайда:

База данных телефонных номеров Ограниченное количество всевозможных номеров Ключевой параметр – скорость поиска Каждый номер уникален Относительно небольшое количество номеров реально задействовано База данных постоянно пополняется

Слайд 9

Описание слайда:

База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив

Слайд 10

Описание слайда:

Слайд 11

Описание слайда:

База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив Проблемы: Массив занимает очень много места Большое количество полей массива не заполнено

Слайд 12

Описание слайда:

Концепция Хеш-таблицы Массив фиксированной длинны Положение элемента определяется хеш-функцией Отображение элементов на множество индексов не взаимно-однозначное Достоинства: Занимает относительно мало места Быстрый поиск элемента Недостатки: Не сохраняется порядок Не эффективны при малом количестве элементов В одну ячейку могут попасть много элементов

Слайд 13

Описание слайда:

Организация хеш-таблицы и проблема коллизий

Слайд 14

Описание слайда:

Решение проблемы коллизий Метод цепочек (закрытая адресация)

Слайд 15

Описание слайда:

Закрытая адресация В каждой ячейке хранится список значений При добавлении элемент с заданным хешом добавляется в конец списка Простое удаление элемента из списка При хорошей хеш-функции сложность поиска , где – коэффициент заполненности При большом коэффициенте заполненности необходима перестройка таблицы Тратится место на хранение ссылок в списках

Слайд 16

Описание слайда:

Закрытая адресация

Слайд 17

Описание слайда:

Открытая адресация Порядок вставки определяется последовательностью проб Последовательность проб должна содержать каждую ячейку таблицы не более одного раза При коэффициенте заполненности, близком к 1 поиск занимает , где N – размер таблицы Сложная операция удаления

Слайд 18

Описание слайда:

Открытая адресация

Слайд 19

Описание слайда:

Последовательность проб: пробивание Линейное пробирование

Слайд 20

Описание слайда:

Последовательность проб: double hashing Используются две хеш-функции и Последовательность просмотра: Просмотры в общем случае аналогичны линейному пробированию При правильном выборе хеш-функций работает быстрее

Слайд 21

Описание слайда:

Слайд 22

Описание слайда:

Хеширование Хеширование (англ. hashing) — преобразование массива входных данных произвольной длины в битовую строку фиксированной длины, выполняемое определённым алгоритмом. Хеш-функция – функция, реализующая алгоритм хеширования Хеш (хеш-сумма, хеш-код) – результат выполнения хеширования

Слайд 23

Описание слайда:

Хеш-функции

Слайд 24

Описание слайда:

Хеш-функции Результат применения хеш-функции имеет фиксированную длину При небольшом изменении входных данных существенно меняется результат Нет взаимно-однозначного соответствия между входными данными и ответом Ключевые свойства хеш-функций: Вычислительная сложность Разрядность Криптостойкость

Слайд 25

Описание слайда:

Хорошие хеш-функции Свойства «хорошоих» хеш-функций: Минимальное количество коллизий Равномерное распределение ответов Быстрое вычисление Идеальная хеш-функция – хеш-функция которая отображает каждый ключ из набора S во множество целых чисел без коллизий

Слайд 26

Описание слайда:

Применение хеш-функций Хранение и поиск данных Компьютерная графика Контрольные суммы Информационная безопасность

Слайд 27

Описание слайда:

Примеры хеш-функций Остаток от деления Не криптостойкий Отсутствует лавинный эффект При некоторых N возникает много коллизий

Слайд 28

Описание слайда:

Примеры хеш-функций Полиномиальный хеш Не криптостойкий При некоторых N возникает много коллизий

Слайд 29

Описание слайда:

Примеры хеш-функций XOR – хеширование Не криптостойкий Отсутствует лавинный эффект

Слайд 30

Описание слайда:

Примеры хеш-функций Cyclic redundancy check (CRC) Не криптостойкий

Слайд 31

Описание слайда:

Примеры хеш-функций Семейство MD (Message Digest) MD4 (взломан) MD5 (взломан) MD6 Семейство SHA (Secure Hash Algorithm) SHA-1 (взломан) SHA-2 (взломан) SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256, SHA-512/224 SHA-3 (Keccak)

Слайд 32

Описание слайда:

Слайд 33

Описание слайда:

Слайд 34

Описание слайда:

Слайд 35

Описание слайда:

Слайд 36

Описание слайда:

Сравнение производительности Добавление 10000 элементов

Слайд 37

Описание слайда:

Сравнение производительности Поиск несуществующего элемента

Слайд 38

Описание слайда:

Сравнение производительности Поиск 1000 случайных элементов

Слайд 39

Описание слайда:

Сравнение производительности Поиск 1000 существующих элементов

Слайд 40

Описание слайда:

Слайд 41

Описание слайда:

Встроенные хеш-таблицы в Python Словари (dict) Ассоциативный массив Хранит пары ключ-значение Быстрый поиск по ключам Множества (set) Операции над множествами Быстрый поиск элемента