21. Хеширование. Разрешение коллизий. Виды хеш-функций.

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

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

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

Разрешение коллизий в хеш-таблицах:

1) Метод цепочек: Технология сцепления элементов (chaining) состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i; если таких элементов в множестве нет, в позиции i записан NULL;

2) Открытая адресация: В отличие от хеширования с цепочками, при открытой адресации никаких списков нет, а все записи хранятся в самой хеш-таблице. Каждая ячейка таблицы содержит либо элемент динамического множества, либо NULL;

Виды хеш-функций:

SHA-1: Secure Hash Algorithm 1 – алгоритм криптографического хеширования. Для входного сообщения произвольной длины (максимум 264 − 1 бит, что равно 2 эксабайта) алгоритм генерирует 160-битное хеш-значение. Используется во многих криптографических приложениях и протоколах.

MD4: Message Digest 4 – хеш-функция. Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение. Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверки подлинности удаленных рабочих станций Windows. Является предшественником MD5.

MD5: Message Digest 5 – 128-битный алгоритм хеширования. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Является улучшенной в плане безопасности версией MD4. Зная MD5-образ (называемый также MD5-хеш), невозможно восстановить входное сообщение, так как одному MD5-образу могут соответствовать разные сообщения. Используется для проверки подлинности опубликованных сообщений путём сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck).

22. TransRelation модель данных.

Модель TransRelational(TR) как таковая представляет собой конкретное приложение более общей технологии, получившей название преобразования Тарена в честь ее разработчика. Метод преобразования Тарена, предназначен для использования в качестве технологии реализации для систем хранения и выборки данных многих типов (а не только для СУБД), включая, например, системы хранилищ данных, инструментальные средства разработки данных, системы SQL, машины поиска Web, системы, основанные на использовании языка XML и т.д. В отличие от этого, тема данного приложения (т.е. модель TransRelational как таковая) просто представляет собой пример применения этой более общей технологии для реализации, в частности, реляционных систем. Но, как вскоре станет очевидно, эта общая технология особенно хорошо приспособлена для реализации именно реляционных систем; в действительности, она разрабатывалась в основном с учетом данной конкретной цели.

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

В модели TR используются намного более совершённые средства преобразо­вания:

1) Модель TR обеспечивает гораздо большую независимость от данных по сравнению с той, которая достигнута или может быть достигнута в системах с непосредственным отображением;

2) В модели TR данные по существу хранятся во многих разных физических последовательностях одновременно, поэтому исключается необходимость в использовании индексов и тому подобных структур;

3) При использовании модели TR оптимизация осуществляется значительно проще, чем при использовании систем с непосредственным отображением; зачастую существует только один очевидный и при этом наилучший способ реализации любой конкретной реляционной операции;

4) Производительность модели TR на несколько порядков выше по сравнению с системами непосредственного отображения, иными словами, система приобретает способность к масштабированию;

5) Администрирование системы в значительной степени упрощается, поскольку гораздо реже приходится принимать субъективные решения;

6) На физическом уровне системы вообще отсутствует такое понятие, как "хранимая переменная отношения", или "хранимый кортеж".