Краткие итоги

Ключевые термины

Вторичные ключи – это ключи, не позволяющие однозначно идентифицировать запись в таблице.

Закрытое хеширование или Метод открытой адресации – это технология разрешения коллизий, которая предполагает хранение записей в самой хеш-таблице.

Коллизия– это ситуация, когда разным ключам соответствует одно значение хеш-функции.

Коэффициент заполнения хеш-таблицы – это количество хранимых элементов массива, деленное на число возможных значений хеш-функции.

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

Первичные ключи – это ключи, позволяющие однозначно идентифицировать запись.

Повторное хеширование – это поиск местоположения для очередного элемента таблицы с учетом шага перемещения.

Пространство записей – это множество тех ячеек памяти, которые выделяются для хранения таблицы.

Пространство ключей – это множество всех теоретически возможных значений ключей записи.

Синонимы– это совпадающие ключи в хеш-таблице.

Хеширование– это преобразование входного массива данных определенного типа и произвольной длины в выходную битовую строку фиксированной длины.

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

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

1.В настоящее время используется широко распространенный метод обеспечения быстрого доступа к большим объемам информации – хеширование.

2.Для установления соответствия ключей и данных строится хеш-таблица.

3.Хеш-таблица строится при помощи хеш-функций. Практическое применение получили функции прямого доступа, остатков от деления, середины квадрата, свертки.

4.При построении хеш-таблиц могут возникать коллизии, то есть ситуации неоднозначного соответствия данных ключу.

5.Разрешение коллизий проводится методом цепочек (открытое или внешнее хеширование) или методом открытой адресации (закрытое хеширование).

6.Поиск свободных ключей в методе открытой адресации может проводиться методом повторного хеширования с помощью линейного опробования, квадратичного опробования или двойного хеширования.

7.Идентификация данных в таблицах может осуществляться как по первичному, так и по вторичному ключу.

8.Хеширование имеет широкое практическое применение в теории баз данных, кодировании, банковском деле, криптографии и других областях.