[структуры данных] Хэшированный файл

а какая асимптотика у fseek кстати?

fseek осуществляет позиционирование за O(1)

> Требуется реализовать структуру данных на основе файла - словарь со словами произвольной длины, вставка, удаления и поиск должны осуществляться за O(1). Какая структура данных подходит для этого?

За O(1) (в худшем случае) для слов разной длины выполнять все приведенные операции ни одна структура не позволяет впринципе. Хеш-таблица может дать от O(1) до O(N), но здесь все зависит от грамотного подбора хэш-функции, алгоритма разрешения коллизий и размещения звезд на небе. B-дерево может дать O(logN) в худшем случае. Оптимизированные варианты могут это еще улучшить.

Насколько я понимаю, нужно как-то хранить хэш-таблицу в файле, но в интернете я нигде не нашел реализации или описания такой структуры(. Как это правильно будет по-английски? По «hashed file» гугль выдает всякий мусор...

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

Хотя я бы все-таки советовал присмотреться к B-деревьям - они решают многие проблемы хеш-таблиц, просто реализуются и являются, в отличии от хэш-таблиц, упорядоченными.

Berkeley DB умеет хеш, как и деревяшки.