ФУНКЦИЯ РАССТАНОВКИ
— целочисленная функция, играющая главную роль в методике обработки информации и исключающая сплошной перебор при занесении и поиске информации. Пусть имеется последовательность объектов, при этом каждому объекту соответствует некоторая информация. Для простоты предполагается, что объект и информация изображаются двоичными кодами, помещающимися вместе в одной ячейке памяти ЦВМ. Применение методики Ф. р. целесообразно, когда

, где n — максимум числа разных объектов в последовательности,

длина кода, изображающего объект. Задача состоит в том, чтобы создать в памяти таблицу объектов с информацией о них, вход в которую производится по коду объекта.
Для составления таблицы используется сначала пустое расстановочное поле длиной в
ячеек, заполнение которого производится с помощью произвольной Ф. р.
определенной на двоичных кодах длины l и принимающей значения от нуля до
. При рассмотрении очередного объекта а делается попытка направить его в ячейку расстановочного поля с номером
Если ячейка s пуста, она отводится для хранения объекта а и информации о нем. Если она уже оказалась занятой объектом, тождественным а, это значит, что объект встретился в последовательности повторно. Если ячейка s занята другим объектом, начинают просматриваться ячейки с адресами
и т. д. (счет ведется по
до тех пор, пока не будет найдена пустая ячейка или ячейка, уже содержащая объект а.
Обычный метод последовательного размещения объектов в таблице, приводящего к сплошному перебору таблицы при поиске, получается при
Наиболее эффективен такой выбор Ф. р., при котором ее значения равномерно распределены в диапазоне
на случайных последовательностях объектов. В этом случае число тактов, требуемое для размещения объекта, пропорционально
при
, а при
— в среднем ограничено константой, не зависящей от n. В случае двоичной кодировки объектов N обычно берется равным
и Ф. р. вычисляется по правилу: двоичный код объекта делится на куски, по длине не превышающие
, которые затем складываются друг с другом по
Метод Ф. р. реализован при создании алъфа-системы.
Лит.:
. А. П. Ершов.