Хешированные таблицы и функции хеширования - раздел Образование, СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Как Отмечалось Выше, В Каждой Реальной Таблице Фактическое
Множество...
Как отмечалось выше, в каждой реальной таблице фактическое
множество ключей является лишь небольшим подмножеством множества
всех теоретически возможных ключей. Поскольку память является од-
ним из самых дорогостоящих ресурсов вычислительной системы, из
соображений ее экономии целесообразно назначать размер пространс-
тва записей равным размеру фактического множества записей или
превосходящим его незначительно. В этом случае мы должны иметь
некоторую функцию, обеспечивающую отображение точки из пространс-
тва ключей в точку в пространстве записей, т.е., преобразование
ключа в адрес записи: r = H(k), где - r адрес записи, k - ключ.
Такая функция называется функцией хеширования (другие ее названия
- функция перемешивания, функция рандомизации).
При попытке отображения точек из некоторого широкого прост-
ранства в узкое неизбежны ситуации, когда разные точки в исходном
пространстве отобразятся в одну и ту же точку в целевом прост-
ранстве. Ситуация, при которой разные ключи отображаются в один и
тот же адрес записи, называется коллизией или переполнением, а
такие ключи называются синонимами. Коллизии - основная проблема
для хешированных таблиц, решение которой будет рассмотрено далее.
Если функция H, преобразующая ключ в адрес, может порождать
коллизии, то однозначной обратной функции: k = H`(r), позволяющей
восстановить ключ по известному адресу, существовать не может.
Поэтому ключ должен обязательно входить в состав записи хеширо-
ванной таблицы как одно из ее полей.
К функции хеширования в общем случае предъявляются следующие
требования:
- она должна обеспечивать равномерное распределение отобра-
жений фактических ключей по пространству записей;
- она должна порождать как можно меньше коллизий для данного
фактического множества записей;
- она не должна отображать какую-либо связь между значениями
ключей в связь между значениями адресов;
- она должна быть простой и быстрой для вычисления.
В [ ] приведен почти исчерпывающий обзор и анализ применяе-
мых на практике функций хеширования, мы же ограничимся лишь обзо-
ром некоторых наиболее простых.
Простейшей функцией хеширования является деление по модулю
числового значения ключа на размер пространства записи. Результат
интерпретируется как адрес записи. Хотя эт функцию и применяется
во всех приводимых ниже примерах данного раздела, следует иметь в
виду, что такая функция плохо соответствует первым трем требова-
ниям к функции хеширования и сама по себе может быть применена
лишь в очень ограниченном диапазоне реальных задач. Однако, опе-
рация деления по модулю обычно применяется как последний шаг в
более сложных функциях хеширования, обеспечивая приведение ре-
зультата к размеру пространства записей.
Функция середины квадрата. Значение ключа преобразуется в
число, это число затем возводится в квадрат, из него выбираются
несколько средних цифр и интерпретируются как адрес записи.
Функция свертки. Цифровое представление ключа разбивается на
части, каждая из которых имеет длину, равную длине требуемого ад-
реса. Над частями производятся какие-то арифметические или пораз-
рядные логические операции, результат которых интерпретируется
как адрес. Например, для сравнительно небольших таблиц с ключами
- символьными строками неплохие результаты дает функция хеширова-
ния, в которой адрес записи получается в результате сложения ко-
дов символов, составляющих строку-ключ.
Функция преобразования системы счисления. Ключ, записанный
как число в некоторой системе счисления P, интерпретируется как
число в системе счисления Q>P. Обычно выбирают Q=P+1. Это число
переводится из системы Q обратно в систему P, приводится к разме-
ру пространства записей и интерпретируется как адрес.
Все темы данного раздела:
СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Статические структуры относятся к разряду непримитивных
структур, которые, фактически, представляют собой структурирован-
ное множество примитивных, базовых, структур. Например, в
Векторы
ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура
данных с фиксированным числом элементов одного и того же типа ти-
па. Каждый элемент вектора имеет уникальный в рамках
Логическая структура
Массив - такая структура данных, которая характеризуется:
- фиксированным набором элементов одного и того же типа;
- каждый элемент имеет уникальный набор значений индексов;
Физическая структура
Физическая структура - это размещение элементов массива в
памяти ЭВМ. Для случая двумерного массива, состоящего из
(k1-n1+1) строк и (k2-n2+1) столбцов физическая структура предс-
Адресация элементов с помощью векторов Айлиффа
Из выше приведенных формул видно, что вычисление адреса эле-
мента многомерного массива может потребовать много времени, пос-
кольку при этом должны выполняться операции сложения
Специальные массивы
На практике встречаются массивы, которые в силу определенных
причин могут записываться в память не полностью, а частично. Это
особенно актуально для массивов настолько больших раз
МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ
ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых
местоположения элементов со значениями отличными от фонового, мо-
гут быть математически описаны,
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОГО
РАЗМЕЩЕНИЯ. Один из основных способов хранения подобных разрежен-
ных матриц заключается в запоминании ненулевых элементов в одно-
мерном массиве и идентификации
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
Методы последовательного размещения для представления разреженных
матриц обычно позволяют быстрее выполнять операции над матрицами
и более эффективно использовать память, чем мето
Множества
ЛОГИЧЕСКАЯ СТРУКТУРА. Множество - такая структура, которая
представляет собой набор неповторяющихся данных одного и того же
типа. Множество может принимать все зн
Числовые множества
Стандартный числовой тип, который может быть базовым для
формирования множества - тип byte.
Множество хранится в памяти как показано в таблице 3.3.
Таблица 3.3
&
Множество из элементов перечислимого типа
Множество, базовым типом которого есть перечислимый тип,
хранится также, как множество, базовым типом которого является
тип byte. Однако, в памяти занимает место, которое зависит
Множество от интервального типа
Множество, базовым типом которого есть интервальный тип,
хранится также, как множество, базовым типом которого является
тип byte. Однако, в памяти занимает место, которое зависит
Логическое и машинное представление записей
Запись - конечное упорядоченное множество полей, характери-
зующихся различным типом данных. Записи являются чрезвычайно
удобным средством для представления программных моделей ре
Таблицы
Когда речь шла о записях, было отмечено, что полями записи
могут быть интегрированные структуры данных - векторы, массивы,
другие записи. Аналогично и элементами векторов и массив
Структурами. Поиск
В этом и следующих разделах представлен ряд алгоритмов поис-
ка данных и сортировок, выполняемых на статических структурах
данных, так как это характерные операции логического уро
Последовательный или линейный поиск
Простейшим методом поиска элемента, находящегося в неупоря-
доченном наборе данных, по значению его ключа является последова-
тельный просмотр каждого элемента набора, который про
Бинарный поиск
Другим относительно простым методом доступа к элементу явля-
ется метод бинарного (дихотомического, двоичного) поиска, который
выполняется в заведомо упорядоченной последовательно
Структурами. Сортировка
Для самого общего случая сформулируем задачу сортировки та-
ким образом: имеется некоторое неупорядоченное входное множество
ключей и должны получить выходное множество тех же клю
Сортировки выборкой
СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практи-
чески "дословно" сформулированную выше стратегию выборки. Порядок
алгоритма простой выборки
Еще одна модификация пузырьковой сортировки носит название
шейкер-сортировки. Суть ее состоит в том, что направления прос-
мотров чередуются: за просмотром от начала к концу следует прос-
мотр от конца к началу входного м
Сортировки включением
СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реа-
лизации стратегии включения. Порядок алгоритма сортировки просты-
ми вставками - O(N^2), ес
Сортировки распределением.
ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА.Алгоритм требует представ-
ления ключей сортируемой последовательности в виде чисел в неко-
торой системе счисления P. Число прохо
Таблицы прямого доступа
Простейшей организацией таблицы, обеспечивающей идеально
быстрый поиск, вляется таблица прямого доступа. В такой таблице
ключ является адресом записи в таблице или может быть прео
Таблицы со справочниками
Одним из способов устранения этого недостатка является метод
справочников. Основная таблица содержит записи в произвольном по-
рядке. В дополнение к основной строится справочная и
Новости и инфо для студентов