Результатом положительных испытаний является сертификат

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

Хеш-таблица как структура данных.

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

Хорошая хеш-функция должна (приближенно) удовлетворять предположениям равномерного хеширования: для очередного ключа все m хеш-значений должны быть равновероятны. Заметим, что иногда желательно, чтобы хеш-функция удовлетворяла условиям, выходящим за пределы требования равномерного хеширования. Например, можно стараться, чтобы «близким» в каком-либо смысле ключам соответствовали «далёкие» хеш-значения. Обычно предполагают, что область определения хеш-функции (ключи) — множество целых неотрицательных чисел. Если ключи не являются натуральными числами, их обычно можно преобразовать к такому виду (хотя числа могут получиться большими).

Деление с остатком. Построение хеш-функции методом деления с остатком (division method) состоит в том, что ключу k ставится в соответствие остаток от деления k на m, где m— число возможных хеш-значений:h(k) = k mod m

Умножение. Построение хеш-функции методом умножения (multiplication method) состоит в следующем. Пусть количество хеш-значений равно m. Зафиксируем константу А в интервале 0 < А < 1, и положим h(k) = [m(kAmod 1)]где (k A mod 1)—дробная часть kА.

Универсальное хеширование. Если недоброжелатель будет специально подбирать данные для хеширования, то (зная функцию h) он может устроить так, что все m ключей будут соответствовать одной позиции в таблице, в результате чего время поиска будет равно O(m). Основная идея универсального хеширования — выбирать хеш-функцию во время исполнения программы случайным образом из некоторого множества.

Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется коллизией.

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

При закрытом (внутреннем) хешировании в хеш-таблице хранятся непосредственно сами элементы, а не заголовки списков элементов. Поэтому в каждой записи (сегменте) может храниться только один элемент. При закрытом хешировании применяется методика повторного хеширования. Если осуществляется попытка поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов h1(x), h2(x),..., куда можно поместить элемент х. Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное. Если свободных сегментов нет, то, следовательно, таблица заполнена, и элемент х добавить нельзя.

Дата добавления: 2015-11-14