Адресация с помощью ключей, преобразуемых в адрес

В некоторых приложениях адрес может быть вычислен на основе значений некоторых элементов данных записи.

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

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

Более экономичным является указание на область, в которой размещается группа записей. Эта область называется участком записей (slot, bucket).

При первоначальной загрузке файла адрес, по которому должна быть размещена запись, определяется следующим образом:

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

Из-за вероятностной природы алгоритма в этом способе не удается достичь 100%-ной плотности заполнения памяти, однако для большинства файлов может быть достигнута плотность 80 или 90 %; при этом память для индексов не требуется. Большинство записей можно найти за одно обращение, но для некоторых потребуется второе обращение (при переполнении). Для очень небольшой части записей потребуется третье или четвертое обращение к файлу.

Кроме того, в этом случае менее эффективно используется память, чем в индексных методах; записи не упорядочены для последовательной обработки.