Реализация хешированных таблиц страниц

Цель работы: изучить основные методы организации таблиц идентификаторов, получить представление о преимуществах и недостатках, присущих различным методам организации таблиц идентификаторов, научиться

Индивидуальное задание:

Оборудование: ПК с операционной системой Windows XP/7/8.

Теоретические сведения

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

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

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

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

Существуют два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив H, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение i = \mbox{hash}(key) играет роль индекса в массиве H. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива H[i].

Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется коллизией. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50% (если каждый элемент может равновероятно попасть в любую ячейку) — см. парадокс дней рождения. Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.

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

Число хранимых элементов, делённое на размер массива H (число возможных значений хеш-функции), называется коэффициентом заполнения хеш-таблицы (loadfactor) и является важным параметром, от которого зависит среднее время выполнения операций.

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

Ход работы

1. Ознакомиться с теоретическими сведениями

2. Для ОС Linux. Осуществить защиту выбранного файла.

а. Правой кнопкой мыши щелкнуть по файлу и выбрать функцию Действия- Зашифровать файл.

б. Выбрать в разделе Параметры пункт Симметричное шифрование.

в. Ввести пароль

г. Удалить исходный файл

д. Проверить функционирование защиты.

3. Для ОС Windows. Установить программу Enciphering для шифровки необходимой информации (выбрать файл).

Установить LimBlockFolder для установки пароля на папку с файлом, обработанным программой Enciphering.

4. Самостоятельно найти, выбрать и установить бесплатную утилиту для защиты информации с открытым исходным кодом.

Содержание отчета

Отчет по практической работе должен содержать следующие пункты:

- название практической работы;

- цель работы;

- краткие теоретические сведения;

- индивидуальное задание для выполнения работы;

- краткое описание хода выполнения работы;

- результаты выполнения работы;

- выводы.

 

Практическая работа №23

Создание резервных копий

Цель работы: научиться выполнять архивирование данных и пользоваться службой восстановления системы.

Индивидуальное задание: п ровести архивирование данных

Оборудование: ПК с операционной системой Windows XP

Теоретические сведения

Архивация и восстановление

Мастер архивации и восстановления (BackuporRestoreWizard) создает копию файлов и папок на указанном пользователем носителе информации. В случае потери или повреждения пользовательских данных их можно восстановить из файла резервной копии. Специалисты рекомендуют выполнять регулярное создание резервных копий важных файлов и папок. Частота архивации (резервного копирования) зависит от частоты изменений файлов, так как в случае потери данных придется повторно создать то, что было сделано после последней архивации. По этой причине многие компании создают резервные копии важных файлов ежедневно. Пользователь может выбирать различные типы архивации в зависимости от его требований.

• Для типа Обычная (Normal) происходит архивация всех выбранных файлов и системных настроек для определенной папки или диска, и каждый файл маркируется как прошедший архивацию (имеющий резервную копию).
• Для типа Копирование (Copy) происходит архивация всех выбранных файлов и системных настроек для определенной папки или диска, но файлы не маркируются как прошедшие архивацию.
• Для типа Добавочная (Incremental) происходит архивация только тех файлов, которые были созданы или изменены вслед за последней обычной или добавочной архивацией, и каждый файл маркируется как прошедший архивацию.
• Для типа Разностная (Differential) происходит архивация только тех файлов, которые были созданы или изменены вслед за последней обычной или добавочной архивацией, но файлы не маркируются.
• Для типа Ежедневная (Daily) происходит архивация только тех файлов, которые были созданы или изменены в данный день, но файлы не маркируются.

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

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