Критическим параметром в такой работе является стоимость поиска отдельного диска. Поиск диска имеет врожденную задержку, потому что головки чтения / записи должны быть перемещены в правильное положение. На типичном диске вы можете рассчитывать примерно на сотню поисков в секунду. С другой стороны, диски очень хороши для последовательного чтения, поэтому при каждом поиске вы можете читать, скажем, один мегабайт данных за небольшую дополнительную плату.
Здесь я предполагаю, что текстовый файл имеет обычный формат. Например, каждое хеш-значение использует ровно 33 байта, 32 для самого результата MD5 (в шестнадцатеричном формате) и 1 дополнительный байт для символа «новой строки». Отрегулируйте, если необходимо, в зависимости от точного формата. С этими цифрами ваш текстовый файл имеет длину около 3,3 ГБ.
Поскольку MD5 действует в основном как случайная функция, 100 миллионов хешей должны равномерно распределяться в пространстве 128-битных значений. Это означает, что, учитывая хеш-значение, вы можете вычислить приблизительную позицию этого значения в файле (если оно есть в файле). Например, значение хеша 9378ec093d09863d008154f1c8f5ca8f должно быть со смещением, близким к 0,5761 * n * 33 , где n - количество хешей в большом файле, а "33" - это объяснено в пункте выше. 0,5761 является результатом 0x9378EC , деленным на 0x1000000 . Следовательно, вы можете прочитать текстовый файл на один мегабайт, центрированный на этой вычисленной позиции. Это будет содержать около 30000 хешей. Стандартное отклонение для 100 миллионов случайных значений составляет порядка 10000, поэтому высока вероятность того, что 30000 хешей будут содержать правильные значения, чтобы решить, находится ли ваш хэш в списке или нет. Если оценка была выключена, вам придется прочитать еще один мегабайт, но это случается не часто. Возможно, вы могли бы прочитать чуть больше мегабайта, чтобы сделать это вхождение редким: существует компромисс, который необходимо скорректировать с помощью реальных мер.
Если у вас есть (небольшой) блок значений хеш-функции в ОЗУ, используйте бинарный поиск. Но первоначальная стоимость поиска в любом случае полностью затмит эту часть.
Альтернативное решение использует дополнительный индексный файл. Создайте дополнительный файл, который содержит один каждые 10000 хешей в большом файле. Этот файл будет иметь длину около 330 кБ. Храните этот файл в оперативной памяти как можно больше. Используйте его (с двоичным поиском), чтобы узнать, какая последовательность из 10000 хешей подходит для вашего поиска. Затем прочитайте этот кусок из большого файла. Индексный файл должен быть перестроен всякий раз, когда список хэшей изменяется; это довольно дорого, но меньше, чем реальное изменение файла. В зависимости от системы, которая создает большой файл, возможно, вы можете интегрировать генерацию индексного файла за незначительные дополнительные расходы.