38. Проанализируйте хеш-таблицу как структуру данных.

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

Хорошая хеш-функция должна (приближенно) удовлетворять предположениям равномерного хеширования: для очередного ключа все 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), ..., куда можно поместить элемент х. Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное. Если свободных сегментов нет, то, следовательно, таблица заполнена, и элемент х добавить нельзя.

39. Охарактеризуйте линейные динамические структуры данных.

Список  — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности — кортежа. Экземпляры значений, находящихся в списке, называются элементами списка. если значение встречается несколько раз, каждое вхождение считается отдельным элементом. Линейный связный список – здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно. Двунаправленный связный список – здесь ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.

Кольцевой связный список – разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.

Стек – структура данных, представляющая из себя список элементов, организованных по принципу LIFO («последним пришёл — первым вышел»).

Очередь — информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой.

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

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

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

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