Java. Сложность поиска O(1)

Недавно пробовал устроиться на работу, дали тестовое задание, сделал все кроме сложности поиска за O(1). HR сказала, что решение основывается на построении индекса в памяти. Можете обьяснить, что это значит желательно с примером. Заранее спасибо!) Ссылка на гит с проектом:(https://github.com/venoman9867/testTask)

Ответ:

Никакой индекс не дает сложность O(1). Все же ваше решение не соответствует требованиям. Вы читаете весь файл целиком, хотя это прямо запрещено заданием, вам надо ознакомиться с принципами функционирования баз данных и тем, как в них устроены индексы. Но в любом случае, не думаю, что вы много потеряли: работодатели с "домашними заданиями" на собеседовании как правило так себе.

Чуть подробнее все же опишу, в какую сторону двигаться. Посмотрите, FileChannel.map() - это способ работать с memory-mapped файлами. Общая схема такая - предварително нужно построить таблицу в памяти, где для строк в файла CSV будут записаны смещения в файле по которым они расположены. Поиск в таблице занимает O(log(N)) и не требует операций чтения с диска. После этого достаточно прочитать запись из mmap по смещению.