5.12. Обработка столкновений

Что делать со столкновением? Простой метод состоит в том, чтобы взглянуть на вычисленное (путем перемешивания) место в таблице. Если оно пусто, "то в него вносится соответствующая запись; если оно занято, то нужно

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

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