IX Международная студенческая научная конференция Студенческий научный форум - 2017

Согласно проведенным исследованиям, во время работы компилятора на этапе лексического анализа происходит распознавание лексических конструкций языка. Элементы, информация о которых будет использоваться в процессе компиляции хранятся в виде организованных наборов данных – таблиц идентификаторов. На различных фазах компиляции компилятор вынужден многократно обращаться к таблице для поиска информации и записи новых данных. В процессе заполнения таблиц каждый элемент однозначно идентифицируется своим именем в результате чего поиск осуществляется по имени элемента в таблице. Использование идентификаторов осуществляется чаще чем занесении информации о них в таблицы, поэтому можно сделать вывод о том, что таблицы идентификаторов должны быть организованы таким образом, чтобы компилятор имел возможность максимально быстрого поиска нужного ему элемента. [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

Код для цитирования: Скопировать