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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-04