Вопрос №9. Хэш-адресация с использованием метода цепочек.

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

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

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

Вопрос №10. Хэш-функции и хэш-адресация. Хэш-адресация с рехэшированием.

Хэш-функции и хэш-адресация

Хэш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r) =п, r R,n Z. Сам термин «хэш-функция» происходит от английского термина «hash function» (hash — «мешать», «смешивать», «путать»).

Множество допустимых входных элементов R называется областью опреде­ления хэш-функции. Множеством значений хэш-функции F называется под­множество М из множества целых неотрицательных чисел Z: М Z, содер­жащее все возможные значения, возвращаемые функцией F: F(r) M и m M, F(r)=m. Процесс отображения области определения хэш-функции на множество значений называется хэшированием.

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

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

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

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