Организация таблиц лексического анализатора и поиска в них

3.1. Поиск в таблицах

3.1.1. Постановка задачи поиска

ЛА в процессе своей работы многократно обращается к таблицам (имен, констант и т.п.) для выполнения следующих действий:

а) поиска информации;

б) записи новых данных.

Поэтому таблицы должны быть так организованы, чтобы ЛА мог максимально эффективно выполнить эти задачи.

В общем случае задача поиска ставится следующим образом: в заданной области памяти хранится множество R из N записей. Каждая из них имеет некое специальное поле, называемое ключом записи. Ключи принимают значения К₁, К₂,...,К_n.

Задаче поиска задается аргумент поиска (критерий поиска), представляющий собой некоторое значение ключа (К).

Задача поиска состоит в отыскании во множестве R такой записи (R_i) которая имеет К_i=К, то есть задача поиска сводится к отысканию записи, для которой аргумент поиска совпадает с ее ключом К_i=К (К – условие поиска).

Процедура поиска может иметь два исхода:

1) удачный – в этом случае удается определить положение соответствующей записи во множестве R, содержащей ключ К;

2) неудачный – когда ключ К не может быть найден ни в одной из записей множества R.

В общем случае поиск возможен либо в неупорядоченном (по значению поля ключа) множестве записей, либо в упорядоченном.

3.1.2. Последовательный поиск на неупорядоченном множестве записей

Простейшим методом поиска является последовательный поиск, иначе называемый поиском методом последовательного просмотра и последовательного перебора.

Он является универсальным в том смысле, что применим как к неупорядоченному множеству R, так и к упорядоченному. Суть метода в том, что выполняется последовательный просмотр записей R_i с целью отыскания таких записей, для которых выполняется условие поиска k=k_i. Алгоритм поиска можно описать следующим образом

Шаг 1 Начальная установка i:=1, где i – номер текущей записи из множества R.

Шаг 2 Сравнение ключа k_i с аргументом поиска k, т.е. проверка k_i=k?

Если условие поиска выполняется, то запись R_i переносится в поле результата. Если условие поиска не выполняется, то осуществляется переход к шагу 3.

Шаг 3 Увеличение номера текущей записи i:=i+1.

Шаг 4 Проверка условия окончания поиска i≤N? Если просмотрены не все записи, то выполняется переход к шагу 2 или процедура поиска заканчивается.

3.1.3. Бинарный поиск на упорядоченном множестве записей

Метод обычного последовательного просмотра при поиске прост в реализации и эффективно может быть использован в случае, когда требуется однократное или нечастое обращение к исходному множеству R, а само это множество невелико. Если же частота обращений достаточно высока, то гораздо эффективнее оказывается предварительное упорядочение множества R с последующим выполнением поиска на упорядоченном множестве. Предполагается, что множество R упорядоченно по ключам

k₁< k₂ <k₃ <k_N

R₁< R₂ <R₃ <R_N

Двоичный поиск ориентирован на сравнение некоторого эталона (аргумента) поиска K с ключом текущей записи K_i. По результату такого сравнения процедура поиска может быть продолжена по одному из трех исходов:

а) если k<k_i, то все записи R_i, R_i+1, …, R_N исключаются из дальнейшего рассмотрения и поиск продолжается среди записей, у которых значение ключа меньше, чем у текущей записи;

б) k=k_i поиск завершается с удачным исходом;

в) k>k_i записи R₁, R₂, …, R_i исключаются из дальнейшего поиска.

На основе этих простых предположений разработана целая группа методов поиска. На практике широкое распространение получил метод деления пополам или метод бинарного поиска. Основная идея бинарного поиска заключается в том, что на каждом шаге направление (диапазон) поиска сужается вдвое. Для этого надо сравнить заданный аргумент k с ключом средней (по номеру в оставшемся после сужения множестве записей) записи во множестве R. Результат сравнения позволяет определить, в какой половине множества, левой или правой, можно продолжать поиск, применяя затем к этой половине аналогичную процедуру. В результате оказывается, что после числа сравнений, равного log₂N, либо найден ключ k, либо будет установлено отсутствие записи с таким ключом.

Для организации бинарного поиска в исходном упорядоченном множестве R задаются два индекса (указателя):

а) U (upper) – указатель, соответствующий верхней границе области поиска, то есть он имеет большее (верхнее) значение номера записи в текущем интервале поиска;

б) L (low) – указатель нижней границы области поиска, имеющий среди всех записей меньшее (нижнее) значение номера записи.

Если запись с ключом k находится во множестве R, то должно выполняться неравенство k_L≤k≤k_U. Описание алгоритма бинарного поиска:

Шаг 1 Начальная установка. L:=1, U:=N. Охватываем все множество записей.

Шаг 2 Определение середины интервала поиска. Если для текущих значений U и L выполняется соотношение U<L, то алгоритм завершается неудачно, в противном случае номер текущей записи устанавливается i:= é (L+U)/2 ù, где ëiû – ближайшее меньшее целое для i, éiù – ближайшее большее целое для i.

Шаг 3 Сравнение ключа поиска K со значением ключа записи с вычисленным номером i. Возможны три варианта результата такого сравнения:

а) если k<k_i, то переход к шагу 4 (надо откорректировать верхнюю границу текущего интервала поиска);

б) если k>k_i, то переход к шагу 5 (надо откорректировать нижнюю границу текущего интервала поиска);

в) если k=k_i, то алгоритм завершается удачно, запись с ключом k найдена.

Шаг 4 Корректировка указателя U. Установить U:=i-1 и перейти к шагу 2 (поиск продолжается среди записей с меньшими, чем у середины, номерами).

Шаг 5 Корректировка указателя L. Установить L:=i+1 и перейти к шагу 2 (поиск продолжается среди записей с большими, чем у середины, номерами).

Прежде чем начинать поиск по данному алгоритму, надо проверить, находится ли то, что мы ищем, в интервале поиска. То есть надо проверить, выполняется ли условие:

(k k_l) и (k k_u).

В обобщенном виде работу этого алгоритма можно представить следующим образом:

Да

Нет

Да

Нет

Да Нет

Нашли

Не нашли

3.2. Организация таблиц для быстрого поиска без сортировки

3.2.1. Организация таблиц в виде бинарных деревьев

Метод бинарного поиска оказывается эффективным по быстродействию для тех случаев, когда исходное множество записей R упорядоченно и остается неизменным по своему составу в ходе выполнения процедуры поиска (как таблица терминальных символов). Если же заданное множество R динамически изменяется за счет вставок новых записей и удаления прежних (как в таблицах имен и констант, например), то этот метод теряет свою эффективность вследствие необходимости дополнительных затрат на поддержание множества R в упорядоченном состоянии. В подобных случаях оказывается удобным представлять элементы исходного множества R в виде структуры данных типа бинарного дерева. Это позволяет относительно быстро и легко вставлять и удалять записи и выполнять эффективный (быстрый) поиск. Известно, что каждый узел бинарного дерева представляет собой следующую структуру:

где L — указатель на левое поддерево данного узла, R — указатель на правое поддерево.

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

Рассмотрим алгоритм заполнения бинарного дерева. Будем считать, что алго­ритм работает с потоком идентификаторов (имен). Первый идентификатор, как уже было сказано, помещается в вер­шину дерева. Все дальнейшие идентификаторы попадают в дерево по следующе­му алгоритму

Шаг. Выбрать очередной идентификатор из входного потока данных. Если оче­редного идентификатора нет, то построение дерева закончено.

Шаг 2 Сделать текущим узлом дерева корневую вершину.

Шаг 3 Сравнить (по тем же правилам, что сравниваются строки в Паскале) очередной идентификатор с идентификатором, содержащимся в текущем узле дерева.

Шаг 4 Если очередной идентификатор меньше, то перейти к шагу 5, если ра­вен — сообщить об ошибке и прекратить выполнение алгоритма (двух одинако­вых идентификаторов в таблице быть не должно), иначе — перейти к шагу 7.

Шаг 5 Если у текущего узла уже существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе перейти к шагу 6.

Шаг 6 Создать новую вершину, поместить в нее очередной идентификатор, сде­лать эту новую вершину левой вершиной текущего узла и вернуться к шагу 1 (за новым именем).

Шаг 7 Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе перейти к шагу 8.

Шаг 8 Создать новую вершину, поместить в нее очередной идентификатор, сде­лать эту новую вершину правой вершиной текущего узла и вернуться к шагу 1.

При организации таблицы имен в виде дерева сравнения строк (имен) выполняются по следующим четырем правилам

1). Строки слева направо посимвольно сравниваются (первый символ в первой строке с первым символом во второй строке, второй – со вторым и т.д.) до обнаружения первой же (слева направо) пары несовпадающих символов в одной и той же позиции в строках.

2). Строки считаются равными, если они имеют одинаковую длину и посимвольно эквивалентны.

верхняя больше нижней, т.к ord(‘d’) > ord(‘D’)

S1:= ‘abcd’;

S2:= ‘abcD’;

3). Если при посимвольном сравнении строк обнаруживаются несовпадающие в текущей позиции символы, то по соотношению этих символов делается вывод, какая из них больше. Строка s1 больше s2, если из двух несовпадающих символов в ней имеется символ, у которого код ASCII больше, чем у соответствующего по позиции символа в строке s2.

4). Если длина сравниваемых строк неодинакова, то пустое место считается меньшим,чем любой другой символ (код в таблице):

верхняя меньше нижней

‘abc’

‘abcd’

Рассмотрим в качестве примера последовательность идентификаторов GA, Dl, M22, Е, А12, ВС, F. На рисунке показан процесс построения бинарного дерева для этой последовательности идентификаторов.

На этом рисунке пунктиром показан узел A11 – он соответствует отсутствующему (и не найденному) идентификатору.

Поиск нужного элемента в дереве выполняется по алгоритму, схожему с алго­ритмом заполнения дерева. Часто используется не просто поиск, а так называемый поиск со вставкой. Он основывается на том, что если узел с ключом k отсутствует в дереве, то в дерево вставляется новый узел, содержащий ключ k. Алгоритм поиска можно описать следующим образом

Шаг 1 Сделать текущим узлом дерева корневую вершину.

Шаг 2 Сравнить искомый идентификатор с идентификатором, содержащимся в текущем узле дерева.

Шаг 3 Если идентификаторы совпадают, то искомый идентификатор найден, ал­горитм завершается, иначе надо перейти к шагу 4.

Шаг 4 Если очередной идентификатор меньше, то перейти к шагу 5, иначе — пе­рейти к шагу 6.

Шаг 5 Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе (если у текущего узла отсутствует левая вершина) возможны два варианта действий:

- если выполняется простой поиск (без вставки), то искомый идентификатор не найден и алгоритм завершается;

- если выполняется поиск со вставкой, то к текущему узлу в качестве левой вершины вставляется новый узел, содержащий ключ k, и алгоритм завершается.

Шаг 6 Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе (если у текущего узла отсутствует правая вершина) возможны два варианта действий:

- если выполняется простой поиск (без вставки), то искомый идентификатор не найден и алгоритм завершается;

- если выполняется поиск со вставкой, то к текущему узлу в качестве правой вершины вставляется новый узел, содержащий ключ k, и алгоритм завершается.

Например, произведем поиск в дереве, изображенном на рисунке, идентификато­ра А12. Берем корневую вершину (она становится текущим узлом), сравниваем идентификаторы GA и А12. Искомый идентификатор меньше — текущим узлом становится левая вершина D1. Опять сравниваем идентификаторы. Искомый идентификатор меньше — текущим узлом становится левая вершина А12. При следующем сравнении искомый идентификатор найден.

Если искать отсутствующий идентификатор, например А11, то поиск опять пойдет от корневой вершины. Сравниваем идентификаторы GA и A11. Искомый идентификатор меньше — текущим узлом становится левая вершина D1. Опять сравниваем идентификаторы. Искомый идентификатор меньше — текущим узлом становится левая вершина А12. Искомый идентификатор меньше, но левая вер­шина у узла А12 отсутствует, поэтому в данном случае искомый идентификатор не найден.

Затраты времени на поиск по бинарному дереву в среднем оказываются такими же, как и при обычном бинарном поиске в упорядоченном массиве, но применение более эффективно, т.к. не требуется каждый раз при добавлении элемента в таблицу выполнять ее сортировку.

3.2.2. Организация таблиц с хэш-адресацией

3.2.2.1. Размещение информации в хэш-таблицах и поиск в них

Рассмотрим ситуацию, когда исходные данные (записи) хранятся неотсортированными по значению ключевого поля. В этом случае для данного исходного множества записей R = {R₁, R₂,…,R_N}, размещенных в оперативной памяти, может быть выбрана любая конкретная структура хранения соответственно поставленной задачи. Не уменьшая общности можно считать, что такой структурой является таблица записей, в которой записи с ключами К_i располагаются в произвольном порядке.

Суть метода хэширования состоит в следующем. Каждой из N записей таблицы можно однозначно (обычно) поставить в соответствие некоторое целое число а >=0 из диапазона чисел [0,N-1]. В широком смысле это число может быть рассмотрено как адрес или номер записей в таблице.

Например, если ключ К_i в каждой записи представляет собой целое неотрицательное число, то областью определения такого адреса будет интервал целых чисел [0,M-1], где М=2ⁿ, а n – разрядность (число двоичных разрядов) ключа К. В общем случае эта область определения по размеру может быть весьма большой и значительно превышать количество различных ключей N.

Для реализации метода хэширования различными способами находится некоторая функция (хэш-функция) h(К) преобразования заданного множества ключей К_i в их адреса в таблице. Если эта функция найдена, то адрес любой записи из исходного множества может быть вычислен как значение этой функции при известном значении аргумента К, который одновременно является аргументом поиска.

Функция h(К) называется иначе хэш-функцией. Множество допустимых значений ключа К называется областью определения хэш-функции. Процесс нахождения значения h(К) называется хэшированием. Структура данных для поиска, в которой используется хэш-функция, называется хэш-таблицей.

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

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

Метод организации таблиц идентификаторов, основанный на использовании хэш-адресации, заключается в размещении каждого элемента таблицы в ячейке, адрес которой возвращает хэш-функция, вычисленная для этого элемента. Тогда в идеальном случае для размещения любого элемента в таблице идентификаторов достаточно только вычислить его хэш-функцию и обратиться к нужной ячейке массива данных. Для поиска элемента в таблице необходимо вычислить хэш-функцию для искомого элемента и проверить, не является ли заданная ею ячейка массива пустой (если она не пуста — элемент найден, если пуста — не найден). Первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми.

На рисунке проиллюстрирован метод организации таблиц идентификаторов с использованием хэш-адресации. Трем различным идентификаторам И_l, И₂, И₃ соответствуют на рисунке три значения хэш-функции A₁, A₂, A_З. В ячейки, адресуемые A₁, A₂, A_З, помещается информация об идентификаторах И_l, И₂, И₃. При поиске идентификатора И₃ вычисляется значение адреса A_З и выбираются данные из соответствующей ячейки таблицы.

Хэш-таблица

А₂

А₁

А₃ А₃

Размещение Поиск

в хэш-таблице в хэш-таблице

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

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

В общем случае условие однозначности между ключом и адресом записи в таблице может не выполняться. Тогда хэш-функция рассматривается как функция, выполняющая преобразования множества ключей {К_i} в множество адресов [0,М-1]. При этом можно считать, что М>>N – числа ключей и для таблицы используется фиксированный объем памяти. Отказ от требования однозначности (на практике однозначность часто не выполняется) означает, что для любых различных ключей, например К_i не равного К_j, после вычисления хэш-функции может оказаться, что h(К_i)=h(K_j). Подобная ситуация называется коллизией, а ключи К_i,K_j называются ключами-синонимами.

С учетом сказанного выше для любого метода хэширования актуальными являются две задачи: 1) выбор или поиск функции хэширования h(K); 2) нахождение способов разрешения возникающих коллизий.

3.2.2.2. Выбор хэш-функций

К любой функции хэширования, отображающей множество ключей {K₁,...,K_n} в адреса таблицы aє[0,M-1], предъявляются следующие основные требования:

быстрота и простота вычислений;

минимальное число коллизий;

отсутствие явления скучивания ключей в отдельных частях таблицы (т.е. желательно равномерное распределение ключей по таблице хэширования).

Известны следующие классические методы построения хэш-функций

1). Метод деления.

В качестве значения хэш-функции здесь используется остаток от деления ключа K на некоторое целое число M. Полученное значение записывается h(K)=(K mod M) + 1. При этом h(K) будет изменяться от 1 до M.

Эффективность данного метода (и, в частности, равномерность рассеивания ключей) во многом определяется выбором числа M. Рекомендуется выбирать M как некоторое простое число (желательно нечетное), что позволяет снизить скучивание. Весьма неудачным считается выбор четных значений M, то есть M = 2^S, где S≥0. Поскольку в этом случае значениями хэш-функции будут младшие разряды цифрового кода ключа, что приводит к сильному скучиванию. Обычно в качестве значения M выбирают размер таблицы (число ячеек).

2). Метод умножения.

Ключ K представляется в виде двоичного числа, и выбирается некоторое дробное число α<1, которое умножается на K. Из полученного произведения выделяется дробная часть, которая обозначается {K*α}. В качестве значения хэш-функции используется целое число, которое образовано m старшими разрядами этой дробной части. Эффективность этого метода зависит от выбора значения α.

3). Метод середины квадрата.

В качестве значения h(K) используется m разрядов средней части в двоичном представлении квадрата ключа K. Причем при каждом вычислении ключа используются одни и те же разряды.

4). Метод деления многочленов (алгебраическое кодирование).

Достоинством метода является гарантированное отсутствие скопления ключей в одной части таблицы.

Идея этого метода аналогична методу простого деления, но вместо деления на простое число используется деление на многочлен по модулю Z, то есть находится остаток от такого деления. В этом случае должно выполняться условие M=2^m. Для реализации метода выбирается некоторый многочлен P(x)=x^m+P_mx^m-1+...+P₂x+P₁.= x^m+ P_ix^i-1. Коэффициенты p многочлена выбираются произвольно (либо 0, либо 1).

Ключ K рассматривается как двоичное n-разрядное число с цифрами (битами): K=(K₁K₂K₃…K_n-1K_n), где K₁– самый левый в двоичной записи (старший) разряд, а K_n– самый правый в записи (младший). Ключу K ставится в соответствие многочлен K(x)= K_ix^i-1 = =K_nx^n-1+...+K₂x+K₁. Для получения искомого значения хэш-функции (в диапазоне от 0 до М) находится остаток от деления K(x) на P(x) по правилам деления многочленов по модулю два:

K(x) mod P(x)=h_mx^m-1+...+h₂x+h₁ = h_ix^i-1.

В результате коэффициенты h_m,..., h₂, h₁ представляют собой цифры (h₁ – старшая, h_m – младшая) числа, которое является значением хэш-функции. В этом методе главным является выбор полинома P(x). При удачном выборе полинома полученная хэш-функция позволяет избежать коллизии между почти равными ключами.

Пример: k=1010011 (n=7), требуется получить код с m(число двоичных разрядов) =4.

K(x)= 1*x⁰+0*x¹+1*x²+0*x³+0*x⁴+1*x⁵+1*x⁶ = x⁶ + x⁵ + x² + 1,

P(x)=x⁴+x² +1.

При делении многочленов по модулю два вычитания вида k_i – p_i производятся по следующим правилам:

k_i p_i k_i-p_i

0 0 0

0 1 1

1 0 1

1 1 0

Выполним деление и получим следующий результат:

x6 + x5 +.. +.. + x2 + x1 + 1 x4 + x2 + 1

x6 + x4 + + x2 x2 + x +1

x5 + x4 + x1 + 1

x5 + x3 + x1

x4 + x3 + 1

x4 + x2 + 1

x3 + x2 = 0*x0 + 0*x1+ 1*x2 + 1*x3

Таким образом, искомый двоичный код (значение хэш-функции) равен 0011.

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

3.2.2.3. Способы разрешения коллизий

Для решения этой задачи предложено несколько методов. Чаще всего используются два: 1) метод цепочек; 2) метод открытой адресации.

Рассмотрим их по порядку.

Метод цепочек

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

Если (см. рисунок) значение функции a=h(K_j) для ключа K_j является одинаковым для ключей K_j+1,K_j+2, то есть h(K_j)=h(K_j+1)=h(K_j+2), то для того, чтобы выделить в памяти соответствующие записи, они объединяются в связный список. Новые элементы добавляются в конец этого списка. Тогда задача поиска требуемой записи сводится к вычислению значения хэш-функции и просмотру элементов списка.

Метод открытой адресации

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

Просмотр выполняется за несколько шагов, на каждом из которых выполняется следующий алгоритм:

1) значение i (номер шага) устанавливается равным 0;

2) вычисляется значение хэш-функции на шаге i;

3) если элемент по найденному адресу a свободен, то есть там нет записей с ключом K, то алгоритм поиска завершается. В случае простого поиска завершение считается неудачным – нет записи. В случае поиска со вставкой новая запись записывается в таблицу, и алгоритм завершается удачным исходом;

4) если элемент хэш-таблицы по адресу a имеет, ключ равный K, то алгоритм завершается удачным исходом. Если же выполняется вставка, то повторно она не делается;

5) если элемент таблицы по адресу a имеет ключ, не равный K, то это означает возникновение коллизии. Для её разрешения на пятом шаге выполняется i:=i+1 – увеличение номера шага и осуществляется переход к п. 2.

В результате реализации алгоритма образуется последовательность хэш-функций h_i(K). Возможности и качества алгоритма зависят от способа выбора функции h_i(K), i=1,2,...

Известны следующие варианты реализации метода открытой адресации в зависимости от вида функции h_i(k):

1. h_i(k)=h₀(k)+C_i, i=1,2,…

h₀(k) - стандартная хэш-функция, полученная методом деления или умножения (h₀(k)=k mod M);

C - некоторая подбираемая константа.

Использование подобной зависимости отвечает разновидности открытой адресации, которая называется методом линейного опробования.

2. h_i(k)=h₀(k)+C_i +d_i², i=1,2,…

C, d – подбираемые константы.

Этот вариант h_i(k) соответствует методу квадратичного опробования.

3. h_i(k)=h₀(k)+g(k), i=1,2,…

g(k) – некоторая хэш-функция, близкая к h₀(k), но не эквивалентная ей, например g(k)=1+(k mod (M-2)).

Такой способ представления h_i(k) соответствует методу двойного хэширования.