Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Эффективное представление множеств - часть 4


Следует также обратить внимание, что вычисление этой функции не должно быть слишком трудоемким.

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

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

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

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

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


Начало  Назад  Вперед