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


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


В этом случае говорят о коллизии.

Для использования метода хэширования надо справиться со следующими проблемами:

·         определения величины массива и тем самым числа z значений индексов,

·         выбор функции расстановки h,

·         определение способа разрешения коллизий.

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

Размер массива должен быть выбран таким, чтобы массив был занят не более чем на 90%.

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

Если сами ключи также заданы в виде натуральных чисел, например из интервала от 0 до s-1, где число s значительно больше числа z, то в качестве функции расстановки можно просто взять

h(i) = i mod z. 

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


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



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