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


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


Если же в определенных приложениях должны использоваться все элементы данных, например, обработка типа сортировки или такие операции над множествами, как объединение и пересечение, то этот метод менее удобен. Чтобы и в этих случаях можно было эффективно работать с хэш-массивами, необходима трудоемкая предварительная сортировка.

Анализ статистики показывает, что метод хэширования чрезвычайно эффективен, если нет слишком большого заполнения хэш-массива. Даже его заполнение на 90% при достаточно удачно выбранном способе зондирования для занесения или выбора нужного элемента в среднем требует 2,56 шага зондирования. Это значение существенно зависит от степени загрузки массива. Поэтому размер хэш-массива следует выбирать таким, чтобы в процессе работы он заполнялся не более чем на 90%.

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

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

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

 

 




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



Книжный магазин