Лабораторная работа № Ознакомление с фундаментальными типами данных План: Целые типы данных

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

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

1. 
   В настоящее время используется широко распространенный метод обеспечения быстрого доступа к большим объемам информации – хеширование.
   
2. 
   Для установления соответствия ключей и данных строится хеш-таблица.
   
3. 
   Хеш-таблица строится при помощи хеш-функций. Практическое применение получили функции прямого доступа, остатков от деления, середины квадрата, свертки.
   
4. 
   При построении хеш-таблиц могут возникать коллизии, то есть ситуации неоднозначного соответствия данных ключу.
   
5. 
   Разрешение коллизий проводится методом цепочек (открытое или внешнее хеширование) или методом открытой адресации (закрытое хеширование).
   
6. 
   Поиск свободных ключей в методе открытой адресации может проводиться методом повторного хеширования с помощью линейного опробования, квадратичного опробования или двойного хеширования.
   
7. 
   Идентификация данных в таблицах может осуществляться как по первичному, так и по вторичному ключу.
   
8. 
   Хеширование имеет широкое практическое применение в теории баз данных, кодировании, банковском деле, криптографии и других областях.