Cтраница 4
До сих пор мы обсуждали как последовательно расположенные, так и непоследовательно расположенные на диске файлы, но мы еще не объяснили, зачем нужны эти два типа расположения. Последовательно расположенными файлами легко управлять, но если максимальный размер файла не известен заранее, эту технологию нельзя использовать. Если файл начинается с сектора j и разрастается в последовательные сектора, он может наткнуться на другой файл в секторе k, и ему не хватит места на расширение. Если файл располагается непоследовательно, то таких проблем не возникает, поскольку следующие блоки можно поместить в другое место на диске. Если диск содержит ряд увеличивающихся файлов, конечные размеры которых неизвестны, записать их в последовательные блоки на диске практически невозможно. Иногда можно переместить существующий файл, но это очень накладно. [46]
В большинстве реализаций Снобола 4 множество цепочек литер, существующих в любой момент выполнения программы, хранится в центральной таблице цепочек. Эта таблица организована как хеш-таблица, в которой каждая позиция является указателем на связанный список группы. Чтобы проверить, принадлежит ли множеству данная цепочка X, применяется схема двойного хеширования, X хешируется дважды: для получения хеш-адреса, используемого как индекс в центральной таблице, задающий указатель на соответствующую группу, и для получения порядкового номера в группе. Каждый элемент в списке группы состоит из порядкового номера в группе и указателя на цепочку. Элементы данной группы упорядочены по порядковому номеру. Для того, чтобы определить, хранится ли X в группе, определяемой хеш-адресом X, порядковый номер X последовательно сравнивается с номерами в списке группы до тех пор, пока не произойдет совпадение или пока не будет обнаружен порядковый номер, больший чем у X В последнем случае X немедленно включается в список, в первом требуется политерное сравнение X со всеми цепочками в группе, имеющими тот же самый порядковый номер. Запрограммируйте эту схему двойного хеширования в предположении, что цепочки хранятся в последовательных блоках и имеют дескрипторы, определяющие их длину. Желательно, чтобы в запрограммированной функции в качестве входной информации использовался указатель на некоторую цепочку и чтобы функция, проверяя наличие цепочки в таблице, включала цепочку в таблицу, если ее там не оказалось, возвращала адрес прежней позиции, если цепочка уже была в таблице, или адрес новой позиции, если ее там до этого не было. [47]