Заполнение таблиц идентификаторов с использованием алгоритма хэш-адресации
Один из наиболее эффективных способов реализации таблиц идентификаторов - использование хэш-функции. Построение хэш-функции методом деления. Реализация в программном коде хэш-функции и рехэширования. Организация таблицы идентификаторов в виде массива.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 18.03.2019 |
| Размер файла | 211,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Тюменский индустриальный университет
Заполнение таблиц идентификаторов с использованием алгоритма хэш-адресации
Верхотуров И.А.
Основное содержание исследования
Согласно проведенным исследованиям, во время работы компилятора на этапе лексического анализа происходит распознавание лексических конструкций языка. Элементы, информация о которых будет использоваться в процессе компиляции хранятся в виде организованных наборов данных - таблиц идентификаторов. На различных фазах компиляции компилятор вынужден многократно обращаться к таблице для поиска информации и записи новых данных. В процессе заполнения таблиц каждый элемент однозначно идентифицируется своим именем в результате чего поиск осуществляется по имени элемента в таблице. Использование идентификаторов осуществляется чаще чем занесении информации о них в таблицы, поэтому можно сделать вывод о том, что таблицы идентификаторов должны быть организованы таким образом, чтобы компилятор имел возможность максимально быстрого поиска нужного ему элемента. [1-2]
Один из наиболее эффективных способов реализации таблиц идентификаторов - использование хэш-функции. Среднее время поиска элемента в ней есть O (1), время для наихудшего случая - O (n). Основным требованием к функции можно считать высокую скорость нахождения хэш-значения для размещения элемента в таблице.
В данной работе построение хэш-функции осуществлено методом деления, который заключается в отображении ключа k в одну из m ячеек путем получения остатка от деления k на m.
Поскольку для вычисления хэш-функции требуется только одна операция деления, хэширование методом деления достаточно быстрое. Хэш-функция имеет вид: h (k) = k mod m.
При заполнении таблиц может возникнуть коллизия - ситуация, когда два ключа могут быть хэшированы в одну ячейку. [3-4]
В представленной работе проблема коллизий решается методом "рехэширования".
Рехэширование имеет вид: h (k) = h (k) +1.
Реализация в программном коде хэш-функции и рехэширования:
void HashFunc (String a, String *
A) { int n=0; int j=1; int res=0;
for (int i = 1; i <=a. Length (); i++)
{ n=a [i];
res=res+ n; }
if (A [res%40] =="")
{ A [res%40] =a; }
while (A [res%40]! = a && A [res%40]! = "")
{ res=res+1;
A [res%40] =a; }
}
В представленной работе таблица идентификаторов организована в виде массива. На вход функции HashFunc подаётся элемент и массив, в который этот элемент нужно разместить. Поскольку размер каждого массива - 40 элементов, Хэш-функция имеет вид: h (res) = res mod 40. Параметр res вычисляется как сумма ASCII-кодов литер, входящих в состав названия идентификатора. Так как метод деления подразумевает использование остатка от деления - переполнение массива исключено.
Графическое представление таблиц идентификаторов реализовано с использованием библиотеки визуальных компонентов программного средства - RAD Studio XE8, поддерживающего технологию объектно-ориентированного программирования [5]. Графическая реализация представлена на рисунке 1.
алгоритм таблица идентификатор рехэширование
Рис.1. Графическая реализация таблиц идентификаторов
Алгоритм заполнения таблиц идентификаторов, реализованный с помощью графического языка UML представлен на рисунке 2 [6].
Данный алгоритм хэш-адресации может иметь широкое применение в реализации телефонных справочников, хранении каталогов книг, и других областях, в которых хранение данных осуществляется в табличной форме.
Рис.2. Алгоритм заполнения таблиц идентификаторов
Литература
1. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. - СПб.: Питер, 2001. - 736 с.
2. Жаков В.И., Корсакова Н.В., Никитин А.В., Фильчаков В.В. Структуры данных: Учебное пособие. - Л.: ЛИАП, 1989. - 76 с.
3. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. - М.: Издательский дом "Вильямс", 2012. - 1296c
4. Клочко В.И. Теория вычислительных процессов и структур: Учебное пособие. - Краснодар: Изд-во КубГТУ, 1999. - 118 с.
5. Архангельский А.Я. Программирование в С++ Builder.7-е изд. - М.: ООО "Бином-Пресс", 2010. - 1230 с.: ил.
6. Буч Г., Рамбо Д., Якобсон И. Язык UML. Руководство пользователя.2-е издание. - М.: ДМК Пресс, 2006. - 496 с.: ил.
Размещено на Allbest.ru
...Подобные документы
Назначение, принципы и методы построения таблиц идентификаторов. Метод простого рехэширования с помощью произведения. Назначение лексического анализатора. Таблица лексем и содержащаяся в ней информация. Построение лексических анализаторов (сканеров).
курсовая работа [703,1 K], добавлен 08.02.2011Сравнение методов деления отрезка пополам, хорд, касательных и итераций, поочередно используя их для решения одного и того же уравнения. Построение диаграммы и графика изменения числа. Исследование алгоритма работы программы, перечня идентификаторов.
курсовая работа [1,3 M], добавлен 06.08.2013Вычисление значения функции с помощью программирования. Рабочий набор исходных данных. Таблица идентификаторов, текст программы, контрольный расчет. Подключение модуля, объявление константы и переменных вещественного типа. Шаг изменения аргумента.
контрольная работа [118,4 K], добавлен 28.09.2012Организация таблицы идентификаторов, ее содержание и назначение. Метод бинарного дерева и цепочек. Проектирование лексического анализатора и схема распознавателя. Построение дерева вывода, синтаксический анализатор. Анализ результатов работы программы.
курсовая работа [1,0 M], добавлен 25.12.2014Создание базы данных "Компьютерные игры": разработка и дизайн интерфейса, наполнение таблиц информацией, формирование идентификаторов. Использование системы управления базами данных Microsoft Access для составления стандартных запросов, форм и отчетов.
курсовая работа [715,7 K], добавлен 29.01.2011Разработка граф-схемы алгоритма раскраски на языке Object Pascal. Формат файла для хранения графов. Выбор удобочитаемых идентификаторов. Переменные, константы, типы, компоненты, процедуры и функции модулей uMain, uInputk, uFiling, uColoring, uHelp.
курсовая работа [1,3 M], добавлен 22.11.2013Построение графика функции. Поиск корней уравнения методом половинного деления. Определение минимума функции методом перебора и значения аргумента. Вычисление определенного интеграла на заданном отрезке с использованием метода правых прямоугольников.
контрольная работа [316,1 K], добавлен 13.11.2014Вычисление значения входного и выходного сигналов в n-равноотстоящих точках, вывод на экран таблицы. Структура программы: модули, список идентификаторов функций, интерфейс. Исходный код программы. Проверка расчетов в Maxima и построение графиков.
курсовая работа [1,4 M], добавлен 14.07.2012Общая характеристика языка программирования Турбо Паскаль: операторы, циклы, файлы. Процедуры и функции модуля Crt. Структурная и функциональная схема программы учета учащихся, таблица идентификаторов. Список и описание использованных подпрограмм.
курсовая работа [702,9 K], добавлен 29.01.2011Определение нормального усилия, поперечной силы и изгибающего момента. Построение графиков зависимостей в одной системе координат. Математическая модель решения задачи. Схема алгоритма. Таблица идентификаторов. Текст программы и результаты ее работы.
контрольная работа [706,9 K], добавлен 08.03.2013Общая характеристика и функциональные особенности, основные требования к интерфейсу разрабатываемого программного продукта. Описание алгоритмов, таблица идентификаторов, организация интерфейса пользователя, инструментальные средства реализации проекта.
курсовая работа [587,7 K], добавлен 12.01.2014Стандартные функции MS SQL-сервера. Состав и структура таблиц базы данных. Диалог пользователя с приложением. Корректировка таблиц-справочников. Построение печатных форм. Использование представлений, хранимых процедур и функций, курсоров, триггеров.
курсовая работа [609,2 K], добавлен 28.01.2016Создание программы "компьютерная игра "баскетбол", с упрощенным изображением баскетбольного щита и игрока, с возможностью изменять положение игрока, направление броска и его силу. Построение алгоритма, описание процедур и функций, таблица идентификаторов.
дипломная работа [72,7 K], добавлен 29.11.2011Выполнение заданий на вычисление функции на указанном диапазоне и построение графика функции. Нахождение суммы числового ряда. Нахождение корней уравнения командой "Подбор параметра". Описание технологии работы со списками в электронной таблице Excel.
контрольная работа [35,3 K], добавлен 15.11.2010Системный анализ предметной области. Нормальные формы таблиц. Физическое проектирование базы данных. Реализация структуры БД в СУБД MySQL. Запросы на создание таблиц, добавление и выборку данных. Реализация триггера и функции. Программный код WEB-страниц.
курсовая работа [748,9 K], добавлен 01.11.2014Изучение возможностей, достоинств и недостатков программного продукта Microsoft Excel, который является одним из наиболее известных программ обработки электронных таблиц. Алгоритм установки, порядок ввода формул. Имена ячеек для абсолютной адресации.
курсовая работа [1,5 M], добавлен 16.06.2011Элементы языка программирования. Описание программы по нахождению всех источников орграфа. Таблицы идентификаторов комплекса, глобального и локального контекстов. Постановка проблемных подпрограмм. Инструкция пользователю по работе с программой.
курсовая работа [601,4 K], добавлен 19.02.2012Основные операции, связанные с созданием и форматированием таблиц. Создание таблицы, внесение в нее текстовой информации и выполнение обрамления таблицы. Задание фиксированных размеров ячеек, слияние ячеек, использование автоматической нумерации.
лабораторная работа [165,9 K], добавлен 10.03.2007Построение схемы алгоритма и программы для создания графика временной функции, работающей в машинном и реальном времени. Выбор методов решения и их обоснование. Значение коэффициентов и временной функции. Реализация временных задержек в программе.
курсовая работа [6,2 M], добавлен 09.03.2012Обзор встроенных функции табличного процессора Microsoft Excel, особенности их практического использования. Создание таблиц и их заполнение данными, построение графиков. Применение математических формул для выполнения запросов пакетов прикладных программ.
курсовая работа [3,9 M], добавлен 25.04.2013
